Chinaunix首页 | 论坛 | 博客
  • 博客访问: 458538
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2010-10-06 19:00:00

最近在看组合数学方面的书籍,看到上面的算法就动笔实现了。

#include <iostream>

using namespace std;
/**求组合数
*(1)找出满足C[i] *i=max{j|C[j] *(2)C[i]=C[i]+1;
*(3)C[j]=C[j-1]+1;j=i+1,i+2,.....
*/

int getMax(int C[],int n,int r){
int k=-1;
for(int i=0;i<r;++i)
if(C[i]<=n-r+i)
k=i;
return k;
}

int Com(int a[],int size,int C[],int r){
int i,num=0;
while((i=getMax(C,size,r))>=0){
for(int k=0;k<r;++k)
cout<<C[k]<<" ";
cout<<endl;
num++;
C[i]=C[i]+1;
for(int j=i+1;j<r;++j)
C[j]=C[j-1]+1;
}
for(int k=0;k<r;++k)
cout<<C[k]<<" ";
cout<<endl;
num++;
return num;
}

int main(){
int a[]={1,2,3,4,5,6};
int r=5,C[r];
for(int i=0;i<r;i++) C[i]=a[i];
int num=Com(a,6,C,r);
cout<<"C(6,"<<r<<")="<<num<<endl;
return 0;
}

编译运行后结果如下:

1 2 3 4 5
1 2 3 4 6
1 2 3 5 6
1 2 4 5 6
1 3 4 5 6
2 3 4 5 6
C(6,5)=6

这个算法需要对数据进行排序。
阅读(1133) | 评论(0) | 转发(0) |
0

上一篇:求连续元素和最大

下一篇:C++常量

给主人留下些什么吧!~~