洛谷P1157組合的輸出 遞歸:我他又來辣

沒沒沒沒沒沒沒錯,這是一道簡單的遞歸(其實是深搜加回溯)?

我不管,我說是遞歸就是遞歸。

上題干:

題目描述

排列與組合是常用的數學方法,其中組合就是從?n?個元素中抽出??r個元素(不分順序且 r≤n),我們可以簡單地將?n?個元素理解為自然數 1,2,…,n,從中任取?r?個數。

現要求你輸出所有組合。

例如?n=5,r=3,所有組合為:

123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。

輸入格式

一行兩個自然數n,r(1<n<21,0≤r≤n)。

輸出格式

所有的組合,每一個組合占一行且其中的元素按由小到大的順序排列,每個元素占三個字符的位置,所有的組合也按字典順序。

注意哦!輸出時,每個數字需要?3?個場寬。以 C++ 為例,你可以使用下列代碼:

cout << setw(3) << x;

輸出占?3?個場寬的數?x。注意你需要頭文件?iomanip

輸入輸出樣例

輸入 #1復制

5 3 

輸出 #1復制

  1  2  31  2  41  2  51  3  41  3  51  4  52  3  42  3  52  4  53  4  5

我現在再次重復一遍:寫遞歸,請你放空你的腦袋,然后用樣例,畫出一個草圖,然后用最簡單的(最暴力的)思路去想。不要想太細,太復雜。等你把遞歸的框架搭建完了,再去思考邊界。?

認真看題目啊喂,由于題目要求,每一組數必須是從小到大的排列,所以當第二個數是5的時候,后面沒有比5更大的,所以這種組合就不存在。

第一步,讓我們輕輕畫一個草圖:

這個就是以1為開頭的,所有排列組合

再說一遍:遞歸題,不要想太多,畫出一個例子就可以了,想太多,越想越亂。

第二步,根據圖像想一個巨巨巨巨巨樸素的思路(最暴力的)

我們從1開始往下找,一共要找3個數字.

先找下一層最左邊的,是2,此時序列就是1,2。

由于我們要字典序(不知道字典序是什么的,看一下樣例給的答案。)(也就是 1 2 3 必須要在 1 2 4 前面, 2 3 4 必須 要在 2 3 5前面,這樣的排序,不過多解釋)從小到大,

所以我們直接遞歸到下一層,從下一層的最左邊開始(最左邊最小),

此時的序列就是1,2,3。

打印序列,向逐漸增大移動,序列變為1,2,4? 繼續移動,序列變成1,2,5

當沒有數了之后,回到上一層

當 2的下一層都找完了,,繼續向2這一層數字增大的方向走,也就是1,2變成1,3。

重復此過程。

ok,思路非常簡單,我想你們應該也能想到這樣做,如果大體能看懂,那也很不錯了,相信閱讀完本欄目之后,你能不害怕遞歸。

直接上代碼就完事了:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
const int N = 30;
int t[N];
int flag[N];
int n, r;
void dfs(int x,int y) {if (y > r ) { 當前序列里面的數字個數大于r的時候,就停止for (int i = 1; i <= r; i++) { 打印答案cout << setw(3) << t[i];}cout << endl;return;}for (int i = x ; i <= n; i++)   從x開始,保證后面存進來的每一個數都大于xif (flag[i] == 0 ) {  如果i被標記過了,那么我們就不管i,如果沒有,就把i加入到序列里面flag[i] = 1;   標記it[y] = i;      把i加入到序列里面dfs(i + 1, y + 1);   遞歸下一個數flag[i] = 0;       遞歸結束之后,恢復標記}
}
int main() {cin >> n>>r;dfs(1, 1); //遞歸從1開始,第二個1代表序列里面只有1個數字
}

多么簡單的一道遞歸啊。?

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/167863.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/167863.shtml
英文地址,請注明出處:http://en.pswp.cn/news/167863.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

查swap內存使用

查詢linux的swap被什么使用了 查詢centos的swap被什么進程使用了 swap內存被什么程序占用&#xff0c;什么程序使用了swap分區&#xff0c;占用swap內存的進程 查系統使用swap內存前10個進程&#xff1a; for i in $( cd /proc;ls |grep "^[0-9]"|awk $0 >10…

大數據技術之數據安全與網絡安全——CMS靶場實訓

大數據技術之數據安全與網絡安全——CMS靶場實訓 在當今數字化時代&#xff0c;大數據技術的迅猛發展帶來了前所未有的數據增長&#xff0c;同時也催生了對數據安全和網絡安全的更為迫切的需求。本篇博客將聚焦于大數據技術背景下的數據安全與網絡安全&#xff0c;并通過CMS&a…

C語言-指針講解(3)

文章目錄 1.字符指針變量1.1 字符指針變量類型是什么1.2字符指針變量的兩種使用方法&#xff1a;1.3字符指針筆試題講解1.3.1 代碼解剖 2.數組指針變量2.1 什么是數組指針2.2 數組指針變量是什么&#xff1f;2.2.3 數組指針變量的舉例 2.3數組指針和指針數組的區別是什么&#…

npm ERR! node-sass@4.13.0 postinstall: `node scripts/build.js`

npm ERR! node-sass4.13.0 postinstall: node scripts/build.js npm config set sass_binary_sitehttps://npm.taobao.org/mirrors/node-sass npm install npm run dev Microsoft Windows [版本 10.0.19045.2965] (c) Microsoft Corporation。保留所有權利。C:\Users\Administr…

4.操作系統常見面試題(2)

3.4 虛擬內存 直接使?物理內存會產??些問題 1. 內存空間利?率的問題&#xff1a;各個進程對內存的使?會導致內存碎?化&#xff0c;當要? malloc 分配?塊很?的內存空間時&#xff0c;可能會出現雖然有?夠多的空閑物理內存&#xff0c;卻沒有?夠?的連續空閑內存這種…

手動實現 git 的 git diff 功能

這是 git diff 后的效果&#xff0c;感覺挺簡單的&#xff0c;不就是 比較新舊版本&#xff0c;新增了就用 "" 顯示新加一行&#xff0c;刪除了就用 "-" 顯示刪除一行&#xff0c;修改了一行就用 "-"、"" 顯示將舊版本中的該行干掉了并…

騰訊云AMD服務器標準型SA5實例AMD EPYC Bergamo處理器

騰訊云服務器標準型SA5實例是最新一代的標準型實例&#xff0c;CPU采用AMD EPYC? Bergamo全新處理器&#xff0c;采用最新DDR5內存&#xff0c;默認網絡優化&#xff0c;最高內網收發能力達4500萬pps。騰訊云百科txybk.com分享騰訊云標準型SA5云服務器CPU、內存、網絡、性能、…

Python 忽略warning警告錯誤 + 跳過報錯繼續執行程序

如何主動產生warning錯誤: import warnings def fxn(): warnings.warn("deprecated", DeprecationWarning) with warnings.catch_warnings(): warnings.simplefilter("ignore") fxn() 那么如何來控制警告錯誤的輸出呢? import warnings warnings.fi…

Modown主題v8.12 安裝教程和主題下載

親測」Modown主題v8.12學習版 上傳好主題選擇該主題就好了設置 設置好的首頁 內容頁&#xff1a; WordPress主題Modown和WordPress插件Erphpdown想必正在使用WordPress程序建站的站長都非常熟悉&#xff0c;因為這兩款應用在WordPress站長圈子里還是比較知名的&#xff0c;所以…

計算機畢業設計 基于SpringBoot的無人智慧超市管理系統的設計與實現 Java實戰項目 附源碼+文檔+視頻講解+答疑

博主介紹&#xff1a;?從事軟件開發10年之余&#xff0c;專注于Java技術領域、Python人工智能及數據挖掘、小程序項目開發和Android項目開發等。CSDN、掘金、華為云、InfoQ、阿里云等平臺優質作者? &#x1f345;文末獲取源碼聯系&#x1f345; &#x1f447;&#x1f3fb; 精…

GoLang Filepath.Walk遍歷優化

原生標準庫在文件量過大時效率和內存均表現不好 1400萬文件遍歷Filepath.Walk 1400萬文件重寫直接調用windows api并處理細節 結論 1400萬文件遍歷時對比 對比條目filepath.walkwindows api并觸發黑科技運行時間710秒22秒內存占用480M38M 關鍵代碼 //超級快的文件遍歷 fun…

【HuggingFace Transformer庫學習筆記】基礎組件學習:pipeline

一、Transformer基礎知識 pip install transformers datasets evaluate peft accelerate gradio optimum sentencepiece pip install jupyterlab scikit-learn pandas matplotlib tensorboard nltk rouge在host文件里添加途中信息&#xff0c;可以避免運行代碼下載模型時候報錯…

企業計算機服務器中了360勒索病毒怎么辦,360勒索病毒解密文件恢復

計算機技術的不斷發展&#xff0c;為企業的生產運營提供了極大便利&#xff0c;不僅提升了辦公效率&#xff0c;還促進了企業的發展。企業計算機在日常工作中一定加以防護&#xff0c;減少網絡威脅事件的產生&#xff0c;確保企業的生產生產運營。最近&#xff0c;網絡上的360后…

微信小程序富文本拓展rich-text

微信小程序富文本插件 功能介紹 支持解析<style>標簽中的全局樣式支持自定義默認的標簽樣式支持自動設置標題 若html中存在title標簽,將自動把title標簽的內容設置到頁面的標題上,并在回調bindparse中返回,可以用于轉發支持添加加載提示 可以在Parser標簽內添加加載提…

8:kotlin 類型檢查和轉換(Type checks and casts)

在運行時可以執行類型檢查以檢查對象的類型。類型轉換將對象強制轉換為不同的類型 is 和 !is 可以使用is或者!is來判斷實例是不是指定的類型 fun main() {var obj : Any "cast"if (obj is String) {println(obj.length) // 4}obj 123if (obj !is String) { pr…

動態規劃 之 鋼條切割

自頂向下遞歸實現(Recursive top-down implementation) 程序CUT-ROD對等式(14.2)進行了實現&#xff0c;偽代碼如下&#xff1a; CUT-ROD(p, n)if n 0return 0q -∞for i 1 to nq max{q, p[i] CUT-ROD(p, n - i)}return q上面解決中重復對一個子結構問題重復求解了&#…

Qt無邊框窗口設置陰影

//設置窗體透明this->setAttribute(Qt::WA_TranslucentBackground, true);//設置無邊框this->setWindowFlags(Qt::Window | Qt::FramelessWindowHint | Qt::WindowMinMaxButtonsHint);QVBoxLayout* pMainLay new QVBoxLayout(this);CLoginRealWidget* pRealWidget new …

VR全景展示,“超前點播”打開娛樂行業線上營銷門戶

如今&#xff0c;人們的生活水平正在逐步提高&#xff0c;這種提高不僅僅是體現在衣食住行上&#xff0c;更多方面是體現在大眾的娛樂活動上。我們可以看到&#xff0c;相比于過去娛樂種類的匱乏&#xff0c;現如今&#xff0c;各種娛樂活動可謂是百家爭鳴&#xff0c;例如溫泉…

目標檢測YOLO實戰應用案例100講-基于多光譜圖像融合的光伏組件故障 檢測

目錄 前言 國內外研究現狀 多光譜圖像配準研究現狀 光伏區域識別研究現狀

java學習part10 this

90-面向對象(進階)-關鍵字this調用屬性、方法、構造器_嗶哩嗶哩_bilibili 1.java的this java的this性質類似cpp的this&#xff0c; 但它是一種引用&#xff0c;所以用 this. xxx來調用。 this代表當前的類的實例&#xff0c;所以必須和某個對象結合起來使用&#xff0c;不能…