×joj 1175 The Binomial Function 递归，递归优化，非递归

 1175: The Binomial Function

---

Result TIME Limit MEMORY Limit Run Times AC Times JUDGE

	3s	8192K	2698	800	Standard

1st Jilin University ACM International Collegiate Programming Contest

In this problem, you are to write a program to make the value of the binomial function:

where n and m are integers.

Input Specification

The input consists of several pairs of n and m(0<=n, m<=30). The end of input is marked by n=m=0, which should not be processed.

Output Specification

For each pair of n and m, you should print a line like this: "Binom(n, m) = v", where n, m and v have to be replaced by the values of n, m and v.

Sample Input

5 5
7 0
5 9
0 0

Sample Output

Binom(5, 5) = 1
Binom(7, 0) = 1
Binom(5, 9) = 32

/*
	包含两个参数的递归
	三个版本的递归
	普通递归
	带有备忘录（或者剪枝）
	非递归
*/

#include <stdio.h>
int array[31][31];
/*
	超时
*/
int Binom(int n,int m)
{
	if(n == 0 || n == m || m == 0)
		return 1;
	else 
		return Binom(n-1,m) + Binom(n-1,m-1);
}
/*
	带有备忘录的递归，类似动态规划
*/
int binom(int i, int j){ 
	if(i==0||j==0||i==j)
		return 1;
	else if(array[i][j]) //加一个剪枝
		return array[i][j];
	else
		return array[i][j]=binom(i-1,j-1) + binom(i-1,j);
}
/*
	 非递归版
	 在JOJ上貌似这个版本不比那个剪枝的快
*/
int binomAd(int n,int m)
{	    
	int i;
    for ( i=0;i<=30;++i)
    {
        array[i][0]=1;
        array[i][i]=1;
        array[0][i]=1;
    }
    for ( i=1;i<=30;++i)
     for (int j=1;j<=30;++j)
     {
         if (j!=i)
		   array[i][j]=array[i-1][j]+array[i-1][j-1];
     }
	 return array[n][m];
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m),n !=0||m != 0)
	{
		int t = binomAd(n,m);
		printf("Binom(%d, %d) = %d\n",n,m,t);
	}
	return 0;
}