独立博客: 哲学与程序

哲学与程序

插值算法应用【拉格朗日插值、牛顿插值】

本论文转载至: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;
}

posted on 2011-12-26 20:43 哲学与程序 阅读(793) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序