1317：【例5.2】組合的輸出

時間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 21154 ??? 通過數(shù): 10292

【題目描述】

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

現(xiàn)要求你用遞歸的方法輸出所有組合。

例如n＝5，r＝3，所有組合為：

1 2 3 ? 1 2 4 ? 1 2 5 ? 1 3 4 ? 1 3 5 ? 1 4 5 ? 2 3 4 ? 2 3 5 ? 2 4 5 ? 3 4 5

【輸入】

一行兩個自然數(shù)n、r(1<n<21，1≤r≤n)。

【輸出】

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

【輸入樣例】

5 3

【輸出樣例】

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

【分析】

? ? ? ? 如果不考慮樣例輸入，只考慮樣例輸出，使用枚舉法，直接可以輸出結(jié)果。代碼如下：

#include <stdio.h> int main() {int a,b,c;for(a=1;a<=5;a++)for(b=1;b<=5;b++)for(c=1;c<=5;c++){if(a<b && b<c)printf("%d %d %d\n",a,b,c);}return 0; }

? ? ? ? 現(xiàn)在考慮輸入，怎么枚舉呢？實(shí)際上就是3個坑，分別用1~5的數(shù)進(jìn)行填充。第一個坑，可能填充的數(shù)自然是1、2、3、4、5開頭，由于需要按字典序，所以4和5開頭不用考慮，因?yàn)椴粔蛉齻€。現(xiàn)在只剩下1、2、3三個數(shù)開頭。遞歸解空間樹如下：

? ? ? ? 下面用深搜模板遍歷它。需要記錄哪些信息？三個坑，三個位置，用數(shù)組way[N]記錄，遞歸深度u，即當(dāng)前枚舉哪個位置（第幾個坑）？起始位置start，即當(dāng)前最小可以從哪枚舉？

【參考代碼】

#include <stdio.h> #define N 30int n, m; int way[N]; // 記錄路徑void dfs(int u, int start) // 當(dāng)前枚舉的位置u，從start處開始枚舉 {int i;if(u+n-start<m) // 后面的點(diǎn)加起來不足m個，剪枝舍去 return;if(u>m) // 枚舉到葉子結(jié)點(diǎn) {for(i=1;i<=m;i++)printf(" %d",way[i]);printf("\n") ;return;}for(i=start;i<=n;i++) // 從start開始，逐一進(jìn)行試探 {way[u]=i;dfs(u+1,i+1); // 將i放到u位置，遞歸下一層 ，從i+1開始枚舉} } int main() {scanf("%d%d",&n,&m);dfs(1,1);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1317

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1317：【例5.2】组合的输出）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。