本論文轉(zhuǎn)載至：http://zhexue.sinaapp.com/?p=94，轉(zhuǎn)載請注明出處。
首先看題：POJ_1398。問題：給定N組 f(Xi) = Yi,(1<=i<=N),其中f(x)是一個關(guān)于x的N-1次多項式, 即f(x)=a0 + a1*x +a2*x^2 + ...+an-1*x^(n-1)。
現(xiàn)在給定一個新的x值，求f(x)。即通過給定的N個等式f(Xi)=Yi，求出任意一個給定的x對應(yīng)的f(x)值。這個問題可由數(shù)值計算中的拉格朗日插值或者牛頓插值解決。資料下載。
對于POJ_1398，因為給定的Xi=1,2,3,4,...,N，求解的是X=N+1,N+2,N+3,...,N+S,可以使用一個更加簡單的方法求解。求解方法如下：
(1): 將f(1),f(2),....,f(N), 賦值給數(shù)組Y[N]。
(2): 將Y[N]中數(shù)相鄰兩兩做差,得到N-1個數(shù),
(3): 重復(fù)(2)N-1次，即只剩下一個數(shù)字。
(4): 添加S個相同的數(shù)字至(3)得到的數(shù)字末尾,重復(fù)上述做差的逆操作,最終會得到N+S個數(shù),
而第N+1,...,N+S個數(shù)即為所求。
代碼如下：
#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;
}