牛顿及拉格朗日插值法.cpp

数值分析的实验报告

//牛顿插值法和拉格朗日插值法
#include<stdio.h>
#include<stdlib.h>
#include <iomanip.h>
#include<iostream.h>
typedef struct data
{
	 double x;
	 double y;
}Data;//变量x和函数值y的结构
Data d[20];//最多二十组数据
double f(int b,int a)//牛顿插值法，用以返回插商
{
	 if(a==b+1)
		 return (d[a].y-d[b].y)/(d[a].x-d[b].x);
	 else
		 return (f(b+1,a)-f(b,a-1))/(d[a].x-d[b].x);  
}
double Newton(double x,int count)
{
	 int n;
	 while(1)
	 {
		 cout<<"Please input the number--n, that is the time of the method):";//获得插值次数
		 cin>>n;
		 if(n<=count-1)// 插值次数不得大于count－1次
			 break;
		 else
		     system("cls");
	 }
//初始化t，y，yt。
 double t=1.0;
 double y=d[0].y;
 double yt=0.0;
//计算y值
	 for(int j=1;j<=n;j++)
	 {
		  t=(x-d[j-1].x)*t;
		  yt=f(0,j)*t;
		  //cout<<f(0,j)<<endl;
		  y=y+yt;
	 }
	 return y;
}
double lagrange(double x,int count)
{
	 double y=0.0;
	 for(int k=0;k<count;k++)//这儿默认为count－1次插值
	 {
		  double p=1.0;//初始化p
		  for(int j=0;j<count;j++)//计算p的值
		  {
			   if(k==j)continue;//判断是否为同一个数
			   p=p*(x-d[j].x)/(d[k].x-d[j].x);
		  }
		  y=y+p*d[k].y;//求和
	 }
	 return y;//返回y的值
}
int main()
{
	 double x,y;
	 char a;
	 int count;
	 while(1)
	 {
		  cout<<"Please input times of the x[i] & y[i] and not beyond 20:";//要求用户输入数据组数
		  cin>>count;
		  if(count<=20)
		   break;//检查输入的是否合法
		  system("cls");
	 }
	//获得各组数据
	 for(int i=0;i<count;i++)
	 {
		  cout<<"Please input the number x group of" <<i+1<<endl;
		  cin>>d[i].x;
		  cout<<"Please input the number y group of" <<i+1<<endl;
		  cin>>d[i].y;
		  system("cls");
	 }
	 for( ; ; )
	 {
		 cout<<"Please input the number of x:";//获得变量x的值
		 cin>>x;
		 system("cls");
		 while(1)
		 {
			  int choice=3;
			  cout<<"Please choose the method of which you want to use"<<endl;
			  cout<<"              (0):Exit"<<endl;
			  cout<<"              (1):Lagrange"<<endl;
			  cout<<"              (2):Newton"<<endl;
			  cout<<"input it now";
			  cin>>choice;//取得用户的选择项
			  if(choice==2)
			  {
				   cout<<"You choose the Newton,and the result is ";
				   y=Newton(x,count);
				   break;//调用相应的处理函数
			  }
			  if(choice==1)
			  {
				   cout<<"You choose the Lagrange,and the result is ";
				   y=lagrange(x,count);
				   break;//调用相应的处理函数
			  }
			  if(choice==0)
				   break;
			  system("cls");
			  cout<<"Wrong!"<<endl;
		 }
		 cout<<setiosflags(ios::fixed)<<setprecision(10)<<x<<"    ,        "<<setiosflags(ios::fixed)<<setprecision(10)<<y<<endl;//输出最终结果
		 cout<<"Continue or not?"<<endl;
		 cout<<"Please input 'y' or 'n' "<<endl;
		 cin>>a;
		 if (a!='y')
			 break;
	 }
	 return 0;
}