组合性质之范德蒙德恒等式的程序实现.txt

来自「c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了」· 文本 代码 · 共 65 行

组合性质之范德蒙德恒等式的程序实现[原创] 
刚在书上看到一个组合的性质------范德蒙德恒等式，于是就写了个程序来验证一下。恒等式如下：

  C(m+n,r)=∑C(m,r-k)*C(n,k),k=0,1,2...r

/*
   To prove the property of combo
   C(m+n,r)=∑C(m,r-k)*C(n,k),k=0,1,2...r

   AUTHOR:BugEyes,http://BugEyes.blog.edu.cn
*/
long jiecheng(int n)
{/* to compute n!=n*(n-1)*(n-2)...*2*1 */
  long result=1;
  int i;
  if(n<0)
  {
    printf("error to compute \"n!\" because n<0");
    exit(-1);
  }
  for(i=1;i<=n;i++)
    result*=i;
  return result;
}

long combo(int n,int r)
{   /*to compute C(n,r)*/
  return (jiecheng(n)/jiecheng(r)/jiecheng(n-r));
}

long combo1(int n,int r)
{   /*a new method to compute C(n,r)*/

  long result=1;
  int i;
  for(i=n;i>0;i--)
    if(i>r&&i>(n-r))
      result*=i;
    else if(i<=r&&i>(n-r)||i<=(n-r)&&i>r)
      ;
    else if(i<=r&&i<=(n-r))
      result/=i;
  return result;
}

void main()
{
  int m,n,r;
  int i;
  long result1=0,result2=0;
  printf("Please input three digitals m,n,r,and insure r<=m&&r<=n\n");
  scanf("%d,%d,%d",&m,&n,&r);
  result1=combo1(m+n,r);/*result1=combo(m+n,r)*/
  for(i=0;i<=r;i++)
    result2+=combo1(m,r-i)*combo1(n,i);/*result2+=combo(m,r-i)*combo(n,i)*/
  printf("%ld,%ld",result1,result2);
  if(result1==result2)
    printf("OK");
  else
    printf("ERROR");
}

写的仓促，欢迎看过的朋友进行调试，并给出宝贵意见。另外，由于算法本身的限制，m和n的值不能太大。