牛顿基本插值法

牛顿基本插值法又叫均差法，通过算出均差表求解拟合方程的各阶系数。

c++ 代码如下:

#include<stdio.h>

using namespace std;

int main(){
	int i, k, n;
	float x[20], y[20], t, h, p;
	scanf("%d", &n);
	for (i = 0; i <= n; i++){
		scanf("%f %f", &x[i], &y[i]);  //已知点坐标
	}
	scanf("%f", &t);
	for (k = 1; k <= n; k++){
		for (i = n; i >= k; i--){   //k-1项存放k阶的系数
			y[i] = (y[i] - y[i - 1]) / (x[i] - x[i - k]);
		}
	}
	p = y[0];
	h = 1;
	for (i = 1; i <= n; i++){
		h *= (t - x[i-1]);
		p += y[i]*h;
	}
	printf("%f\n", p);
	return 0;
}