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<bits/stdc++.h>
   
2. using namespace std;
   
3. int n,r;
   
4. int a[25];
   
5. bool b[25];
   
6. void pr()
   
7. {
   
8.         for(int i=1;i<=r;i++) cout<<setw(3)<<a[i];
   
9.         cout<<endl;
   
10. }
    
11. void dfs(int i)
    
12. {
    
13.         if(i>r) pr();
    
14.         else
    
15.         {
    
16.                 for(int k=a[i-1]+1;k<=n;k++)
    
17.                 {
    
18.                         if(b[k]==1)
    
19.                         {
    
20.                                 a[i]=k;
    
21.                                 b[k]=0;
    
22.                                 dfs(i+1);
    
23.                                 b[k]=1;
    
24.                         }
    
25.                 }
    
26.         }
    
27. }
    
28. int main()
    
29. {
    
30.         cin>>n>>r;
    
31.         for(int i=0;i<25;i++)
    
32.                 b[i]=1;
    
33.         dfs(1);
    
34.         return 0;
    
35. }

复制代码

admin

不要用dfs

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int a[30],book[30],n,m;
    
14. void dfs(int cnt,int la)
    
15. {
    
16.         if(cnt==m+1)
    
17.         {
    
18.             for(int i=1;i<=m;i++)
    
19.                  printf("%3d",a[i]);
    
20.             printf("\n");
    
21.             return;
    
22.         }
    
23.         for(int i=la+1;i<=n;i++)
    
24.             if(!book[i])
    
25.             {
    
26.                 book[i]=1,a[cnt]=i;
    
27.                 dfs(cnt+1,i);
    
28.                 book[i]=0;
    
29.                 }
    
30. }
    
31. int main()
    
32. {  
    
33.     scanf("%d%d",&n,&m);
    
34.     dfs(1,0);
    
35.     return 0;
    
36. }

复制代码

Duoluo

#include <iostream>
using namespace std;
int n,r;
bool x[10];
int a[10];
void  dfs(int i)
{
  
    if(i==r)
    {
        for(int q=0;q<r;q++) cout<<a[q]<<"   "; cout<<endl;
    }
    else
    {
        for(int j=1;j<=n;j++)   
        {
            if(x[j])
            {
                a[i]=j;
                if(i>0 && a[i-1]>a[i])
                continue;
                x[j]=false;
                dfs(i+1);
                x[j]=true;
            }
        }
    }
}
int main()
{
    cin>>n>>r;
    for(int ans=1;ans<=n;ans++)
    x[ans]=1;
    dfs(0);
    return 0;
}

Scorpio

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

复制代码

胡雨菲菲

1. #include <cstdio>
   
2. #include <vector>
   
3. const int N = 100010;
   
4. 
   
5. int stak[N], top, p; /// 模拟系统栈
   
6. std::vector<int> v;
   
7. 
   
8. inline void call(int x, int add) {
   
9.     int pre_top = top;
   
10.     stak[++top] = x;
    
11.     stak[++top] = add;
    
12.     stak[++top] = pre_top;
    
13.     p = 0;
    
14.     return;
    
15. }
    
16. 
    
17. inline void ret() {
    
18.     p = stak[top - 1];
    
19.     top = stak[top];
    
20.     return;
    
21. }
    
22. 
    
23. int main() {
    
24.     int n, m;
    
25.     scanf("%d%d", &n, &m);
    
26.     call(1, 0);
    
27.     while(top) {
    
28.         int x = stak[top - 2];
    
29.         if(p == 0) {
    
30.             if(v.size() == m) {
    
31.                 for(int i = 0; i < v.size(); i++) {
    
32.                     printf("%3d", v[i]);
    
33.                 }
    
34.                 printf("\n");
    
35.                 ret(); /// return;
    
36.                 continue;
    
37.             }
    
38.             if(x == n + 1 || v.size() + (n - x + 1) < m) {
    
39.                 ret(); /// return;
    
40.                 continue;
    
41.             }
    
42.             v.push_back(x);
    
43.             call(x + 1, 1); /// DFS(x + 1);
    
44.             continue;
    
45.         }
    
46.         else if(p == 1) {
    
47.             v.pop_back();
    
48.             call(x + 1, 2); /// DFS(x + 1);
    
49.             continue;
    
50.         }
    
51.         else {
    
52.             ret(); /// return;
    
53.             continue;
    
54.         }
    
55.     }
    
56.     return 0;
    
57. }

复制代码

胡雨菲菲

#include <cstdio>
#include <vector>
const int N = 100010;

int stak[N], top, p; /// 模拟系统栈
std::vector<int> v;

inline void call(int x, int add) {
    int pre_top = top;
    stak[++top] = x;
    stak[++top] = add;
    stak[++top] = pre_top;
    p = 0;
    return;
}

inline void ret() {
    p = stak[top - 1];
    top = stak[top];
    return;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    call(1, 0);
    while(top) {
        int x = stak[top - 2];
        if(p == 0) {
            if(v.size() == m) {
                for(int i = 0; i < v.size(); i++) {
                    printf("%3d", v[i]);
                }
                printf("\n");
                ret(); /// return;
                continue;
            }
            if(x == n + 1 || v.size() + (n - x + 1) < m) {
                ret(); /// return;
                continue;
            }
            v.push_back(x);
            call(x + 1, 1); /// DFS(x + 1);
            continue;
        }
        else if(p == 1) {
            v.pop_back();
            call(x + 1, 2); /// DFS(x + 1);
            continue;
        }
        else {
            ret(); /// return;
            continue;
        }
    }
    return 0;
}

liubo

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int a[1005],n,m,arr = 1;
   
5. int main()
   
6. {
   
7.     cin >> n >> m;
   
8.     while(arr){
   
9.         if(arr >= m + 1){
   
10.             for(int i = 1;i <= m;i++)
    
11.                 cout << setw(3) << a[i];
    
12.             cout << endl;
    
13.             arr--;
    
14.             continue;
    
15.         }
    
16.         if(!a[arr]){
    
17.             a[arr] = a[arr - 1] + 1;
    
18.             arr ++;
    
19.             continue;
    
20.         }
    
21.         if(a[arr] + m - arr < n){
    
22.             a[arr++] ++;
    
23.             continue;
    
24.         }
    
25.         a[arr--] = 0;
    
26.     }
    
27.     return 0;
    
28. }

复制代码

admin

对!YTC好样的 就是要这样的一个程序！！！