[C Programming] 二項式係數加法解

請寫一個程式，只用加法，求出n中取r個的組合係數C(n,r)；
並且盡可能地使加法數目減低。

答：
在提到二項式係數時我們就會想到帕斯卡三角形。
(From wikipedia)

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

帕斯卡三角形提醒了我們一件事：C(n, r) = C(n-1, r-1) + C(n-1, r)。
當我們計算C(n, r)的時候，比如圖中的C(7, 4) = 35，
我們就是往其上面找C(6, 3)和C(6, 4)，以此類推，
也就是說我們只要從最頂端，每次往下計算藍色斜線的部分，
總共計算3排斜線(第一排為1就直接指定即可)
也就是說我們每次要算r個數，總共算n-r行，就可以得到答案。

Code：

#define MAXSIZE 100

unsigned long cnt(int n, int r)
{
 unsinged long c[MAXSIZE];
 int i, j;
 for( i = 0; i <= r; i++ )
  c[i] = 1;
 for( i = 1; i <= n-r; i++ )    // 一共有n-r列
  for( j = 1; j <= r; j++ )  // 每次要算r個數
   c[j] += c[j+1];        // 由左上將C(i,j)逐次推到C(i+1,j)
 return c[r]; 
}