组合算法

前两天和梅延涛碰到一个题目,要求从从1~100里取10个数的算法。我首先想到的是递归,比较容易理解十个for循环就能搞定,但是其效率很底。

组合算法
本程序的思路是开一个数组,其下标表示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
我自己用C写了一个程序。不过我把M 改成100 N改成10的时候运行了十分钟还没运行完。这个组合算法可以实现从任意M个数(连续&非连续)里取出n个数。其实我写的程序里只需要讲1到100和任意一百个数字一一对应就行了。

#include
#define M 5
#define N 3

int k = 0;
int check_over(int a[]){
int i;
for(i=0; i<m; i++){
if(a[i] == 1)
break;
}
return M-N-i;
}
void print(int a[]){
int i;
for(i=0; i<m; i++){
if(a[i] == 1)
printf(“%d “, i+1);
//printf(“%d “, a[i]);
}
printf(“n”);
k++;
}
void fun(int a[]){
int tmp, i, j, sum=0;
for(i=0; i<m; i++){
if(a[i]==1 && a[i+1]==0){
tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
for(j=0; j<i; j++){
sum += a[j];
}
for (j=0; j<i; j++){
a[j] = ((j<sum) ? 1 : 0);
}
break;
}
}
}
int main(void){
int i, a[M];
for(i=0; i<m; i++){
a[i] = ((i<n) ? 1 : 0);
}
while (check_over(a)){
print(a);
fun(a);
}
print(a);
printf(“the kinds : %dn”, k);
return 0;
}

3 thoughts on “组合算法

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.