九乡新闻网高端人才 创新发展:不含有重复数字的组合的求法——递归法和二进制法
来源：百度文库 编辑：九乡新闻网 时间：2024/05/05 08:32:11
不含有重复数字的组合的求法——递归法和二进制法
（一）递归法
#include
#include
int n,r;
int count = 0;
void printR(int a[])
{
count++;
for(int j = r-1;j>=0;j--)
printf(" %d",a[j]);
printf("/n");
}
void comb(int a[],int m,int k)
{
for(int i=m;i>=k;i--)
{
a[k-1] = i;
if(k>1)
comb(a,i-1,k-1);
else
printR(a);
}
}
int main()
{
printf("n(总数)、r(取数):");
scanf("%d %d",&n,&r);
int*a = (int*)malloc(sizeof(int)*n);
comb(a,n,r);
printf("Total number: %d",count);
printf("/n");
return 0;
}
（二）二进制法
思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标
代表的数被选中，为0则没选中。
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为
“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得
到了最后一个组合。
例如求5中选3的组合：
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
//按照这种求组合思想实现的算法代码如下：
#include
using namespace std;
int main() delete a;
{
int n,r;
cout<<"Input n(Total),r(Choose):"<
int *a = new int[n];
for(int i=0;i
if(i
else
a[i] = 0;
}
char c = 'y';
int count = 0;
while(c=='y')
{
c = 'n';
for(int i=0;i
if(a[i] == 1)
cout<
count++;
}
cout<
if(a[i]==1 && a[i+1]==0 && a[0] != 0)
{
a[i] = 0;
a[i+1] =1;
c = 'y';
break;
}
else if(a[i]==1 && a[i+1]==0 && a[0] == 0)
{
a[i] = 0;
a[i+1] =1;
c = 'y';
int k=0; //k用来记录在'10'串之前的1的数目
for(int j=0;j
k++;
//将找到的'10'串之前的所有的1放置到最前面去，相应的0跟在后面
for(int j=0;j
if(j
else
a[j] = 0;
}
break;
}
}
}
cout<<"Total number is:"<
a = NULL;
return 0;
}