P1157 组合的输出

admin

题目描述
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你不用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

输入输出格式
输入格式：
一行两个自然数n、r(1<n<21，1<＝r<＝n)。

输出格式：
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

**注意哦!输出时，每个数字需要3个场宽，pascal可以这样：

write(ans:3);

输入输出样例
输入样例#1：
5 3
输出样例#1：
  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

张笑宇

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. const int nn=25,rr=25;
   
5. int a[nn];
   
6. int n,r;
   
7. void pp()
   
8. {
   
9.     int i;
   
10.     for (i=0;i<=r-1;i++) cout<<setw(3)<<a[i]+1;
    
11.     cout<<endl;
    
12. }
    
13. void dfs(int i)
    
14. {
    
15.     int k,p;
    
16.     if (i>=r) pp();
    
17.     else for (k=(i==0?0:a[i-1]+1);k<=n-1;k++)
    
18.     {
    
19.         a[i]=k;
    
20.         dfs(i+1);
    
21.     }
    
22. }
    
23. int main()
    
24. {
    
25.     cin>>n>>r;
    
26.     dfs(0);
    
27.     return 0;
    
28. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int n,m,a[25];
   
5. void cmn(int i)
   
6. {
   
7.     if(i>n){for(int j=1;j<=n;j++)cout<<setw(3)<<a[j];cout<<endl;}
   
8.     else for(int k=a[i-1]+1;k<=m;k++)
   
9.     {
   
10.         a[i]=k;
    
11.         cmn(i+1);
    
12.     }
    
13. }
    
14. int main()
    
15. {
    
16.     cin>>m>>n;
    
17.     cmn(1);
    
18.     return 0;
    
19. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. int a[21],n,r,book[21];
   
3. void dfs(int step)
   
4. {
   
5.         if(step==r+1)
   
6.         {
   
7.                 for(int i=1;i<=r;i++)
   
8.                         printf("%3d",a[i]);
   
9.                 printf("\n");
   
10.         }
    
11.         else
    
12.                 for(int i=a[step-1]+1;i<=n;i++)
    
13.                         if(book[i]==0)
    
14.                         {
    
15.                                 a[step]=i;
    
16.                                 book[i]=1;
    
17.                                 dfs(step+1);
    
18.                                 book[i]=0;
    
19.                                 a[step]=0;
    
20.                         }
    
21. }
    
22. int main()
    
23. {
    
24.         scanf("%d%d",&n,&r);
    
25.         dfs(1);
    
26.         return 0;
    
27. }

复制代码

digger点评： 这位同学 你没有必要布尔数组 book[]，因为组合，可以约定后面的数字比前面的大，那么就绝对不会重复。省掉一个变量，代码也简单多了。

wzd(temp)

说好的不用递归呢。。。。

吴语林

emmmmm，不用递归吗

admin

说了 不准用递归的呢？

lyc

模拟递归

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<vector>
   
4. #include<iomanip>
   
5. const int maxn = 100010;
   
6. using namespace std;
   
7. int stackn[maxn];
   
8. int top, address;
   
9. int n,m;
   
10. vector<int> choose;
    
11. void call(int x, int retadd){
    
12.     int last = top;
    
13.     stackn[++top] = x;///现在的
    
14.     stackn[++top] = retadd;///返回地址
    
15.     stackn[++top] = last;///上一个的栈顶
    
16. }
    
17. int ret(){
    
18.     int retadd = stackn[top - 1];///返回地址
    
19.     top = stackn[top];///还原到上一个栈顶
    
20.     return retadd;
    
21. }
    
22. int main(){
    
23.     cin>>n>>m;
    
24.     call(1, 0);///开始
    
25. 
    
26. 
    
27.     while(top){
    
28.         int x = stackn[top-2];///现选的数
    
29.         if(!address){///限制边界条件
    
30.             if(choose.size()>m ||choose.size()+(n-x+1)<m){
    
31.                 address = ret();
    
32.                 continue;
    
33.             }
    
34.             if(x == n+1){
    
35.                 for(int i=0; i<choose.size(); i++)
    
36.                     cout<<setw(3)<<choose[i];
    
37.                 cout<<endl;
    
38.                 address = ret();
    
39.                 continue;
    
40.             }
    
41.         call(x+1, 1);///选下一个
    
42.         address = 0;
    
43.         continue;
    
44.         }
    
45.         if(address == 1){
    
46.             choose.push_back(x);
    
47.             call(x+1, 2);
    
48.             address = 0;
    
49.             continue;
    
50.         }
    
51.         if(address == 2){
    
52.             choose.pop_back();///回溯
    
53.             address = ret();
    
54.         }
    
55.     }
    
56. 
    
57. 
    
58.     return 0;
    
59. }

复制代码

没必要这么复杂，你理解透彻之后再重做一下。

WWX

#include<iostream>
#include<cstdio>
using namespace std;
int a[25];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=0;i<=m;i++)
        a[i]=i;
    while(a[0]==0)
    {
        for(int i=1;i<=m;i++)
            printf ("%3d",a[i]);
        printf("\n");

        int j=m;
        while(a[j]==n-m+j)j--;
           a[j]++;
        for(int i=j+1;i<=m;i++)
            a[i]=a[i-1]+1;
    }
    return 0;
}

YTC

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int a[101],n,m,top;
   
5. int main()
   
6. {
   
7.     cin>>n>>m;
   
8.     top=1;
   
9.     while(top)
   
10.     {
    
11.         if(top>=m+1) {for(int i=1;i<=m;i++)cout<<setw(3)<<a[i];cout<<endl;top--;continue;}
    
12.         if(a[top]==0) {a[top]=a[top-1]+1;top++;continue;}
    
13.         if(a[top]+m-top<n) {a[top]++;top++;continue;}
    
14.         a[top]=0;top--;
    
15.     }
    
16.     return 0;
    
17. }

复制代码