沒沒沒沒沒沒沒錯,這是一道簡單的遞歸(其實是深搜加回溯)?
我不管,我說是遞歸就是遞歸。
上題干:
題目描述
排列與組合是常用的數學方法,其中組合就是從?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個數字
}
多么簡單的一道遞歸啊。?
?