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