1.计算组合数： 一般常用C(n+1,k)=(n+1)!/k!/(n+1-k)!来计算组合数，但是这个方法中涉及到阶乘运算，数据n不能太大。用下面的方法则可以避免这个问题。
帕斯卡恒等式为C(n+1,k)=C(n,k-1)+C(n,k)
#include <stdio.h> #include <stdlib.h> void error() { printf("Something is wrong,Please check it!"); exit(1); }
int fun(int n,int m) { if(n<0||m<0) error(); if(n<m) return 0; if(m==0||m==n) return 1; else return fun(n-1,m)+fun(n-1,m-1); }
int main() { int n,m; printf("Input two data:\n"); scanf("%d%d",&n,&m); printf("The combo number is:\n%d\n",fun(n,m)); return 0; }
前面的代码还是有点麻烦，递归次数太多而影响效率，例如要计算C(5,1)，按照帕斯卡公式应该拆分如下：
C(5,1) =C(4,1)+C(4,0)=C(3,1)+C(3,0)+C(4,0)=C(2,1)+C(2,0)+C(3,0)+C(4,0)=C(1,1)+C(1,0)+C(2,0)+C(3,0)+C(4,0)=5
可以想象，如果把其中的代码写成下面的样子应该会好一些：
long fun(long n,long r) { if(r<0||n<0)//异常处理 { printf("\nError.Exit!"); exit(-1); } if(r>n)//数学定义 return 0; if(r==1||r==n-1)//根据组合定义，我们有C(n,1)=C(n,n-1)=n return n; if(r==0||r==n)//根据组合定义，我们有C(n,0)=C(n,n)=1 return 1; return fun(n-1,r)+fun(n-1,r-1);//帕斯卡组合公式 }
如果按照这个思路延续下去，我们完全可以在代码中写出if(r==2||r==n-2)、if(r==3||r==n-3)甚至更高，但这样的话，就变成数学问题了，就不是程序设计了。最后我们再看看组合数的定义公式C(n,r)=n!/r!/(n-r)!，改写一下：
C(n,r)=n×(n-1)×(n-2)×...×2×1/[r×(r-1)×(r-2)×...×2×1]/[(n-r)×(n-r-1)×(n-r-2)×...×2×1]
可以看出，有些数如n到max(r,n-r)只有分子上有，有些数如max(r,n-r)到min(r,n-r)分子分母都有，而另一些数如min(r,n-r)到1分子上出现一次而分母上出现两次。因而，我把代码写成下面的样子：
long max(long m,long n) { if(m>n) return m; return n; }
long min(long m,long n) { if(m<n) return m; return n; }
long newfun(long n,long r) { long i; long result=1; for(i=n;i>0;i--) { if(i>max(r,n-r)) result*=i; else if(i<=min(r,n-r)) result/=i; } return result; } 写成这样是否就完美了呢?我认为还没有。仔细看一下，就会发现，在最后一个程序中多次调用max函数和min函数，很明显会影响程序效率。考虑了一下，利用“空间”来换取“时间”，我又修改成了下面的样子：
long max(long m,long n) { if(m>n) return m; return n; }
long min(long m,long n) { if(m<n) return m; return n; }
long newfun(long n,long r) { long i; long maxvalue,minvalue; long result=1; maxvalue=max(r,n-r); minvalue=min(r,n-r); for(i=n;i>0;i--) { if(i>maxvalue) result*=i; else if(i<=minvalue) result/=i; } return result; }
2. 计算组合：利用二进制数计算无重复组合
#define N 5
＃i nclude <conio.h>
void init(int arr[]) { /* to initiate the array*/ int i; for(i=0;i<N;i++) arr[i]=i+1; }
void next(int arr[]) { /* to compute the next possible combination*/ int i; for(i=N-1;i>=0&&arr[i]==1;i--) arr[i]=0; if(i>=0) arr[i]=1; }
int ZeroAtPos(int arr[]) { /* return the position of 0 at the 'binary' array,if not,return -1*/ int i; for(i=0;i<N;i++) if(arr[i]==0) return i; return -1; }
void output(int arr[],int binary[]) { /* print the current combination according to 'binary' array*/ int i; for(i=0;i<N;i++) if(binary[i]==1) printf("%4d",arr[i]); printf("\n"); }
main() { int array[N]; int binary[N]={0}; clrscr(); init(array); while(ZeroAtPos(binary)!=-1) { next(binary); output(array,binary); } }
3. 计算组合：利用函数递归计算无重复组合
int n,r; int a[10];
void fun(int m,int k) { int i,j; for(i=m;i>=k;i--) { a[k-1]=i; if(k>1) fun(i-1,k-1); else { for(j=r-1;j>=0;j--) printf("%5d",a[j]); printf("\n"); } } }
void main() { n=5; for(r=1;r<=n;r++) fun(n,r); }
4. 计算组合：利用函数递归计算有重复组合
int r; int result[20]={0}; zuhe(int m,int k) { int i,j; for(i=m;i>=0;i--) { result[k-1]=i; if(k>1) zuhe(i,k-1); else { for(j=0;j<r;j++) printf("%4d",result[j]); printf("\n"); } } }
main() { r=3; zuhe(7,r); }
5. 计算组合：常规算法计算无重复组合
从n个数中取r个数的组合，假设c1c2c3...cr是其中一个组合，则计算其下一个组合的算法如下：
Step 1:求满足不等式cj<n-r+j的最大坐标，并设为i。即i=max{j | cj<n-r+j}
Step 2:设置ci=ci+1
Step 3:设置cj=cj-1+1，对于j=i+1,i+2,i+3,...,r
＃i nclude <conio.h>
int fun(int choice[],int r,int n) {//利用了上面的算法，计算下一个组合 int i,j; for(i=r-1;i>=0;i--) if(choice[i]<n-r+i) break; if(i<0)//已经是最后一个了 return 0; choice[i]+=1; for(j=i+1;j<r;j++) choice[j]=choice[j-1]+1; return 1;//还有后续组合 }
void comb(char source[],int total,int count) { int choice[5]; int i; for(i=0;i<count;i++)//人工设置第一个组合 choice[i]=i; do { printf("\n"); for(i=0;i<count;i++) {//输出当前组合 int t=choice[i]; printf("%c ",source[t]); } }while(fun(choice,count,total)); }
void main() { char array[5]={'a','b','c','d','e'}; clrscr(); comb(array,5,2); }
6. 组合应用：利用组合求解背包问题
求n个元素的所有组合，有很多方法，有一个方式是这样的：定义一个参考数组并设初值为全0，然后处理参考数组（从后向前扫描，若当前元素值为1则变为0，继续扫描；若当前元素值为0则变为1，然后退出扫描）。接下来根据参考数组输出n个元素（若对应的参考数组中元素值为1，则选择此元素，即输出）。
可以利用这个求组合的方法计算背包问题，其实背包问题本来就可以看作n个元素的r组合。代码如下：
#define K 10 #define N 10
＃ i nclude <stdlib.h> ＃i nclude <conio.h>
void create(long array[],int n,int k) { int i,j; array[0]=1; for(i=1;i<n;i++) { long t=0; for(j=0;j<i;j++) t=t+array[j]; array[i]=t+random(k)+1; } } void output(long array[],int n) { int i; for(i=0;i<n;i++) { if(i%5==0) printf("\n"); printf("%14ld",array[i]); } }
void beibao(long array[],int cankao[],long value,int n) { int i; int j; int cankao1[N]={0}; long value1=0,value2=0; do { value2=0; for(j=n-1;j>=0;j--)/*处理参考数组*/ if(cankao1[j]==0) { cankao1[j]=1; break; } else if(cankao1[j]==1) cankao1[j]=0; for(i=0;i<n;i++)/*计算当前选择方案*/ if(cankao1[i]==1) value2+=array[i]; if(value2<=value&&value2>value1)/*若当前选择方案可取*/ { value1=value2; for(i=0;i<n;i++)/*记录选择方案*/ cankao[i]=cankao1[i]; } }while(j>=0); }
void main() { long array[N]; int cankao[N]={0}; int i; long value; clrscr(); create(array,N,K); output(array,N); printf("\nInput the value of beibao:\n"); scanf("%ld",&value); beibao(array,cankao,value,N); printf("\nThe answer is:\n"); for(i=0;i<N;i++) if(cankao[i]==1) printf("%8ld",array[i]); }
7. 组合应用：利用组合求解整数拆分
所谓整数的拆分，就是把一个整数拆成多个整数之和，如
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
5=5
其实，整数拆分问题可以用过组合来求解，也就是在C(n,0),C(n,1),...,C(n,n)所有的组合中查找组合中所有数之和为n的组合。代码如下：
＃i nclude <conio.h>
#define N 9 int r; int result[20]={0}; zuhe(int m,int k) { int i,j; for(i=m;i>=1;i--) { result[k-1]=i; if(k>1) zuhe(i,k-1); else { int temp=0; for(j=0;j<r;j++) temp+=result[j]; if(temp==N)//当前组合是整数N的一个拆分 { for(j=0;j<r;j++) printf("%4d",result[j]); printf("\n"); } } } }
main() { clrscr(); printf("\nN=%d\n",N); for(r=N;r>0;r--) zuhe(N,r); }
运行结果：
N=7 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 3 1 1 1 2 2 1 1 1 4 1 1 2 3 1 2 2 2 1 1 5 1 2 4 1 3 3 2 2 3 1 6 2 5 3 4 7 N=6 1 1 1 1 1 1 1 1 1 1 2 1 1 1 3 1 1 2 2 1 1 4 1 2 3 2 2 2 1 5 2 4 3 3 6N=5 1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 1 4 2 3 5 N=8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 2 2 1 1 1 1 4 1 1 1 2 3 1 1 2 2 2 1 1 1 5 1 1 2 4 1 1 3 3 1 2 2 3 2 2 2 2 1 1 6 1 2 5 1 3 4 2 2 4 2 3 3 1 7 2 6 3 5 4 4 8
N=3 1 1 1 1 2 3