人工神经网络人工神经网络08-22 02:20

求 n 次二项式各项的系数(杨辉三角形的应用)

原文链接:http://www.cnblogs.com/yueshuqiao/archive/2011/10/18/2216406.html

题目:求 n 次二项式各项的系数,已知二项式的展开式为:

图片

解题思路: 如果直接用上面的公式去计算,计算量很大,当 n 比较大时,算法因时间效率太低。

有一个数学常识:各阶多项式的系数,成杨辉三角形的规律,具体如下所示:

( a+b )0 1

( a+b )1 1 1

( a+b )2 1 2 1

( a+b )3 1 3 3 1

( a+b )4 1 4 6 4 1

( a+b )5 ……

以这个知识为基础,求 n 次二项式的系数的数学模型就是求 n+1 阶杨辉三角形,

l算法设计
?i层有i-2个数据需要计算(a[1]=a[i]=1
?1个一维数据存放已经算出的一行数据
?如果数据每次都从a[1]~a[i]计算并储存,新数据会冲掉前面还需要的数据à从后往前计算
可以用递推方法实现,代码如下
ExpandedBlockStart.gifView Code
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int main()
5 {
6 int n,i,j,a[101];
7 while(cin>>n)
8 {
9 memset(a,0,sizeof(a));
10 for(i=1;i<=n+1;i++) //n次二项式的系数是n+1阶杨辉三角形的最低行
11 {
12 a[1]=a[i]=1;
13 for(j=i-1;j>1;j--)
14 a[j]=a[j]+a[j-1];
15 }
16 for(i=1;i<=n+1;i++)
17 cout<<a[i]<<" ";
18 cout<<endl;
19 }
20 return 0;
21 }

转载于:https://www.cnblogs.com/yueshuqiao/archive/2011/10/18/2216406.html

程序之家二维码

000
评论