※ 引述《syxuan ()》之铭言：
: 遇到一个问题
: (x-a1)(x-a2)(x-a3)(x-a4)...(x-an)
: 要找出方程式的某个次方的系数
: 下面是只有四项要找三项的循环
: for(i[1] = 3; i[1] <= 4; i[1]++) {
: for(i[2] = 2; i[2] <= (i[1]-1); i[2]++) {
: for(i[3] = 1; i[3] <= (i[2]-1); i[3]++){
: sum = sum + a[i[1]]*a[i[2]]*a[i[3]];
: printf("i1=%d, i2=%d, i3=%d, sum=%d\n", i[1], i[2], i[3], sum);
: }
: }
: }
: 不知道要怎么用副程式的方式写成可以有n项取m次方的系数
临时想到的
不知道有没有更好的方法。
Pn(x)=(x-a1)(x-a2)(x-a3)(x-a4)...(x-an)
第m次方的系数等于
1/（2πi）∮Pn(z)/z^(m+1) dz
我开玩笑的
以下认真
基本idea是这样的
最高次数是m+n
要找出第n次项系数
如果能够有效率的穷举会乘出x的n次方的可能性
问题基本上应该算是解决了
如果只乘了n次x，表示总共选出了m个ai
考虑以下穷举的算法
(以下所有计数都从1开始)
1。
一开始有m个指标p，p[i]=&a[i]
2。
回传所有指标所指的组合的乘积
3。
如果p[m]不指向a[n+m]，则p[m]=p[m]+1
然后回(2。)
否则就检查p[m-1]
4。
如果被检查的p[j]+1 == p[j+1]而且j==1就停下来
如果j!=1但p[j]+1 == p[j+1]就检查p[j-1] 回到(4。)
否则
p[j]=p[j]+1;
for(int i=j+1;i<=m;i++)
p[i]=p[i-1]+1;
回到(2。)
5。
把2。回传的结果加总起来就是结果
观察(2。)的回传结果
第一次
a[1]…a[m-1]a[m]
第二次
a[1]…a[m-1]a[m+1]
…
第n次
a[1]…a[m-1]a[m+n]
第n+1次
a[1]…a[m-2]a[m]a[m+1]
…
第2n-1次
a[1]…a[m-2]a[m]a[n]
现在定义b[m][i]= Σa[j] ,j=i to n+m ,i= m to n+m
则前n次可以写成a[1]…a[m-1]b[m][m]
继续定义b[j-1][i] = Σa[k]b[j][k+1] , k=i to n+j-1 ,i=j-1 to n+j-1
发现a[1]…a[j-2]b[j-1][j-1]可以算完前面j-2个指标不动的情况下所有的组合
得到b[1][1]就是所要的答案
提供参考