首页 > 代码库 > shendusousuo

shendusousuo

例3:组合问题

 

输出m个数中取n个数的所有组合。例如m=5,n=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

 

#include<iostream>

using namespace std;

 

int m,n,a[10];  //存放每个数

void comb(int k)

{  if ( k>n )

  {  for (int i=1; i<=n;i++)printf("%5d",a[i]);

  printf("\n"); 

         }

  else

  for (int i=a[k-1]+1; i<=m-n+k; i++)

  {  a[k]=i; comb(k+1);         }

}

 

int main( ) 

{  scanf("%d%d",&m,&n);

  comb(1);  //从第1个数开始

 }

 

 

 

 

例4:子集问题

 

           给定一个有n个元素的集合,输出它所有可能的子集(共2n个)。

例如3个数1、2、3的所有子集为:

空集

1

1      2

1      3

1   2      3

2

2   3

3

 

// 子集问题   dfs代码1

#include<iostream>

using namespace std;

 

int m,n,a[10];  //存放每个数

void  DFS(int k)

{   for (int i=0; i<k; i++)     cout<<a[i]<<" ";

        cout<<endl;  

    for (int i= k>a[k-1]+1; i<=m; i++)  

    {   a[k]=i;   DFS(k+1);     }

}

int main()

{   cin>>m;   

    DFS(0);   return 0;   

}

 

 

 

******************************************************************************************************************************************

#include <iostream>
using namespace std;
int n;
int main()
{   int i,j;
    cin>>n;
    for (i=0; i<(1<<n); i++)
    {
     for (j=0;j<n;j++)
           if ( i&(1<<j)) cout<<j<<" ";
        cout<<endl;
    }
    return 0;
}

 

 

// 子集问题   二进制转换法

#include <iostream>

using namespace std;

int n;

int main()

{   int i,j;

    cin>>n;

    for (i=0; i<(1<<n); i++)

    {

      for (j=0;j<n;j++)

            if ( i&(1<<j)) cout<<j+1<<" ";

        cout<<endl;

    }

    return 0;

}