帕斯卡恒等式和函数递归求组合数 .txt

c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了搜罗的,希望大家喜欢.

利用帕斯卡恒等式和函数递归求组合数 
一般常用C(n+1,k)=(n+1)!/k!/(n+1-k)!来计算组合数，但是这个方法中涉及到阶乘运算，数据n不能太大。用下面的方法则可以避免这个问题。

帕斯卡恒等式为C(n+1,k)=C(n,k-1)+C(n,k)

代码如下：

/*
   利用帕斯卡恒等式和函数递归求组合数
   作者：BugEyes
   主页：http://bugeyes.blog.edu.cn
*/
＃i nclude <stdio.h>
＃i nclude <conio.h>
void error()
{
  printf("Something is wrong,Please check it!");eixt(-1);
}

int fun(int n,int m)
{
   if(n<0)
     error();
   if(m<0)
     error();
   if(m==0||m==n)
     return 1;
   else
     return fun(n-1,m)+fun(n-1,m-1);
}

main()
{
   int n,m;
   clrscr();
   printf("Input two data:\n");
   scanf("%d%d",&n,&m);
   printf("The combo number is:\n%d\n",fun(n,m));
   getchar();
}
 
BugEyes 发表于 2005-9-9 11:01:00