柚子快报激活码778899分享：杨辉三角与二项式定理
这篇博客主要参考刘汝佳的《算法竞赛入门经典》。
下面是一个杨辉三角：
11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1
我们再把(a+b)n展开，将得到一个关于x的多项式： (a+b)0 = 1 (a+b)1 = a + b (a+b)2 = a2 + 2ab + b2 (a+b)3 = a3 + 3a2b + 3ab2 + b3 (a+b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 ……
系数正好和杨辉三角一致。一般地，我们有二项式定理：这个不难理解：(a+b)n是n个括号连乘，每个括号里任选一项乘起来都会对最后的结果又一个贡献。如果选了k个a，就一定会选n-k个b，最后的项自然是an-kbk。而n个a中选k个（同时也相当于n个b里选n-k个)有Ckn，这就是组合数的定义。
给定n，如何求出(a+b)n所有项的系数呢？一个方法是递推，根据杨辉三角中不难发现的规律，可写出以下程序：
1 memset(c, 0, sizeof(c));
2 for(i = 0; i <= n; i++)
3 {
4 c[i][0] = 1;
5 for(j = 1; j <=n; j++)
6 {
7 c[i][j] = c[i-1][j-1] + c[i-1][j];
8 }
9 }
但遗憾的是，这个算法的时间复杂度是O(n2)，尽管只用了杨辉三角的第n行的n+1个元素，但是却把全部n行的O（n2）个元素都计算了一遍。
另一个方法是利用等式
1 c[0]=1;
2 for(i = 1; i <= n; i++)
3 {
4 c[i] = c[i-1]*(n-i+1)/i;
5 }
注意，先乘后除，因为c[i-1]/i可能不是整数。但这样一来增加了溢出的可能性——即结果可能在int或long long 范围之外，乘法也可能溢出。如果担心这样的情况发生，可以先约分，不过一般来说是不必要的。
柚子快报激活码778899分享：杨辉三角与二项式定理
相关文章
发表评论