本论文转载至：http://zhexue.sinaapp.com/?p=94，转载请注明出处。
首先看题：POJ_1398。问题：给定N组 f(Xi) = Yi,(1<=i<=N),其中f(x)是一个关于x的N-1次多项式, 即f(x)=a0 + a1*x +a2*x^2 + ...+an-1*x^(n-1)。
现在给定一个新的x值，求f(x)。即通过给定的N个等式f(Xi)=Yi，求出任意一个给定的x对应的f(x)值。这个问题可由数值计算中的拉格朗日插值或者牛顿插值解决。资料下载。
对于POJ_1398，因为给定的Xi=1,2,3,4,...,N，求解的是X=N+1,N+2,N+3,...,N+S,可以使用一个更加简单的方法求解。求解方法如下：
(1): 将f(1),f(2),....,f(N), 赋值给数组Y[N]。
(2): 将Y[N]中数相邻两两做差,得到N-1个数,
(3): 重复(2)N-1次，即只剩下一个数字。
(4): 添加S个相同的数字至(3)得到的数字末尾,重复上述做差的逆操作,最终会得到N+S个数,
而第N+1,...,N+S个数即为所求。
代码如下：
#include<stdio.h>
#include<string.h>
#define N 105
int x[N];
int f[N][N];
int main()
{
int T, m, n;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n, &m);
memset(f,0,sizeof(f));
for(int i = 0; i < n; i++){
scanf("%d", &f[0][i]);
}
for(int j = 1; j < n; j++){
for(int k = 0; k < n-j; k++){
f[j][k] = f[j-1][k+1] - f[j-1][k];
}
}
for(int i = 1; i <= m; i++)
f[n-1][i] = f[n-1][0];
for(int j = n; j > 0; j--){
for(int i = 0; i < m; i++){
f[j-1][n-j+1+i] = f[j-1][n+i-j] + f[j][n+i-j];
}
}
for(int i = n; i < n+m; i++)
printf("%d ", f[0][i]);
printf("\n");
}
return 0;
}