华师一附中OI组

标题: P1157 组合的输出 [打印本页]
作者: admin    时间: 2018-5-10 12:04
标题: P1157 组合的输出
题目描述
排列与组合是常用的数学方法，其中组合就是从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
作者: 张笑宇    时间: 2018-5-13 17:28
  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. }
复制代码
作者: 黄煦喆    时间: 2018-5-13 20: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    时间: 2018-5-13 21:43
  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)    时间: 2018-5-13 22:05
说好的不用递归呢。。。。
作者: 吴语林    时间: 2018-5-13 22:08
emmmmm，不用递归吗
作者: admin    时间: 2018-5-13 23:05
说了 不准用递归的呢？
作者: lyc    时间: 2018-5-16 13:34
模拟递归
  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);///开始


  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.     }


  58.     return 0;
  59. }
复制代码

没必要这么复杂，你理解透彻之后再重做一下。
作者: WWX    时间: 2018-5-16 16:30
#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    时间: 2018-5-17 10:37
  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. }
复制代码

作者: admin    时间: 2018-5-17 10:41
对!YTC好样的 就是要这样的一个程序！！！
作者: liubo    时间: 2018-5-17 23:18
  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. }
复制代码
作者: 胡雨菲菲    时间: 2018-5-20 13:48
#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;
}
作者: 胡雨菲菲    时间: 2018-5-20 13:48
  1. #include <cstdio>
  2. #include <vector>
  3. const int N = 100010;

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

  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. }

  17. inline void ret() {
  18.     p = stak[top - 1];
  19.     top = stak[top];
  20.     return;
  21. }

  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. }
复制代码
作者: Scorpio    时间: 2018-6-9 15:12
  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. }
复制代码
作者: Duoluo    时间: 2018-6-16 16:40
#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;
}
作者: 吴语林    时间: 2018-6-25 19:31
  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. }
复制代码
作者: admin    时间: 2018-6-27 11:34
不要用dfs
作者: 朱品屹    时间: 2020-8-5 10:10
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2