Cài đặt phương pháp Newton tiến với khoảng cách điều


Mã:
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define max 20

typedef struct Diem{
	float x,y;
};

void GiaoDien(){
	clrscr();
	cout<<"**************** DA THUC NOI SUY ****************\n";
	cout<<"\t1. PP Noi Suy Lagrang.\n";
	cout<<"\t2. PP Noi Suy Tien Voi Cac Nut Khong Cach Dieu.\n";
	cout<<"\t3. PP Noi Suy Lui Voi Cac Nut Khong Cach Dieu.\n";
	cout<<"\t4. PP Noi Suy Tien Voi Cac Nut Cach Dieu.\n";
	cout<<"\t5. PP Noi Suy Lui Voi Cac Nut Cach Dieu.\n";
	cout<<"\t6.Thoat\n";
}

void NhapDiem(Diem*P,int n){
	for(int i=0;i<=n;i++){
		cout<<"P["<<i<<"].x= ";
		cin>>P[i].x;
		cout<<"P["<<i<<"].y= ";
		cin>>P[i].y;
	}
}

void XuatDiem(Diem*P,int n){
	cout<<"\n****************** "<<n+1<<" Diem Vua Nhap *****************\n";
	for(int i=0;i<=n;i++){
		cout<<"P"<<i<<" = ("<<P[i].x<<","<<P[i].y<<")\n";
	}
}
void NhapDT(float A[],int*n){
	printf("\nNhap vao so bac cua da thuc:");
	scanf("%d",&*n);
	for(int i=0;i<=*n;i++){
		printf("Hs[%d] = ",i);
		scanf("%f",&A[i]);
	}
}
void XuatDT(float A[],int n,char*s){
	printf(s); printf("=");
	cout<<A[0];
	for(int i=1;i<=n;i++){
		if(A[i]>0)
			cout<<" +"<<A[i]<<"x^"<<i;
		if(A[i]<0)
			cout<<" "<<A[i]<<"x^"<<i;

	}
}

void CongDT(float A[],int n,float B[],int m,float C[],int*h){
	if(n>m){
		*h=n;
		for(int i=0;i<=m;i++)	C[i]=A[i]+B[i];
		for(i=m+1;i<=n;i++)	C[i]=A[i];
	}else{
		*h=m;
		for(int i=0;i<=n;i++)	C[i]=A[i]+B[i];
		for(i=n+1;i<=m;i++)	C[i]=B[i];
	}
}
void NhanHS(float A[],int n,float B[],float x){
	for(int i=0;i<=n;i++)
		B[i]=x*A[i];
}
void DichPhai(float A[], int n){
	for(int i=n;i>=0;i--)
		A[i+1]=A[i];
	A[0]=0;
}

void NhanDT(float A[],int n,float a,float b,float B[],int*h){
	if(a==0){
		*h = n;
		NhanHS(A,n,B,b);
	}else{
		float*D = new float[n+1];
		*h = n+1;
		NhanHS(A,n,B,a);
		DichPhai(B,n);
		NhanHS(A,n,D,b);
		CongDT(B,n+1,D,n,B,h);
		delete D;
	}
}
/***************************** Noi Suy Lagrang ******************/
float*Yi_Pi_x(Diem*P,int n,int i){
	float*DT=new float[n+1];
	float*DT1=new float[n+1];
	float MS=1;
	int h=0;
	DT[0]=1;
	for(int k=0;k<=n;k++)
	if (k!=i) {
		NhanDT(DT,h,1,-P[k].x,DT1,&h);
		for(int j=0;j<=h;j++)
			DT[j]=DT1[j];
		MS=MS*(P[i].x-P[k].x);
	}
	NhanHS(DT1,n,DT1,P[i].y/MS);
	delete DT;
	return DT1;
}

float* NoiSuy(Diem*P,int n){
	float*A,*B;
	int h;
	A = new float[n+1];
	B = new float[n+1];
	printf("\n\n********** Cac Da Thuc Yi*Pi(x) Tuong Ung **********\n");
	B = Yi_Pi_x(P,n,0);
	XuatDT(B,n,"P0(x)");
	for(int i=1;i<=n;i++){
		A= Yi_Pi_x(P,n,i);
		printf("\nP%d(x)",i);
		XuatDT(A,n,"");
		CongDT(B,n,A,n,B,&h);
	}
	delete A;
	return B;
}
/***************************** Noi Suy NewTon ******************/
void TyHieu_KCD(float A[max][max],Diem*P,int n){
	for(int i=0;i<=n;i++)
		A[i][0]=P[i].y;
	for(i=1;i<=n;i++)
	for(int j=0;j<=n-i;j++)
		A[j][i]=(A[j+1][i-1]-A[j][i-1])/(P[j+i].x-P[j].x);
}

void TyHieu_CD(float A[max][max],Diem*P,int n){
	for(int i=0;i<=n;i++)
		A[i][0]=P[i].y;
	for(i=1;i<=n;i++)
	for(int j=0;j<=n-i;j++)
		A[j][i]=(A[j+1][i-1]-A[j][i-1]);
}

void Xuat_TyHieu(float A[max][max],Diem*P,int n){
	printf("\n\n*** Ty Hieu Cua Cac Nut Noi Suy Khong Cach Dieu ****\n");
	printf("\nx\ty");
	for(int i=1;i<=n;i++)
		printf("\tTHC %d",i);
	for(i=0;i<=n;i++) {
		printf("\n%.3f",P[i].x);
	for(int j=0;j<=n-i;j++)
		printf("\t%.3f",A[i][j]);
	}
}

float*Pi_x(Diem*P,int i){
	float*DT=new float[i+2];
	float*DT1=new float[i+2];
	int h=0;
	DT[0]=1;
	for(int k=0;k<i;k++) {
		NhanDT(DT,h,1,-P[k].x,DT1,&h);
		for(int j=0;j<=h;j++)
			DT[j]=DT1[j];
	}
	delete DT;
	return DT1;
}

void Newton_KCD_Tien(Diem*P, int n){
	float*A,*B;
	int h;
	A = new float[n+1];
	B = new float[n+1];
	float TyHieu[max][max];

	TyHieu_KCD(TyHieu,P,n);
	Xuat_TyHieu(TyHieu,P,n);
	printf("\n\n******* Cac Da Thuc Ty Hieu Cap i Nhan Pi(x) Tuong Ung *******\n");
	printf("\nP0(x)=%f\n",TyHieu[0][0]);
	B = Pi_x(P,1);
	NhanHS(B,1,B,TyHieu[0][0]);
	XuatDT(B,1,"\nP1(x)");
	for(int i=2;i<=n;i++){
		A= Pi_x(P,i);
		NhanHS(A,i,A,TyHieu[0][i]);
		printf("\n\nP%d(x)",i);
		XuatDT(A,n,"");
		CongDT(B,i-1,A,i,B,&h);
	}
	B[0]+=TyHieu[0][0];
	printf("\n\n\t\t Da Thuc Noi Suy Newton Tuong Ung");
	XuatDT(B,n,"\n\nP(x) ");
	delete A;
	delete B;
}

/***************************************************************/

void main(){
	Diem*P;
	int n;
	float A[max][max];
	char Thoat = 1,ch;
	GiaoDien();
	while (Thoat==1){
		gotoxy(4,8);
		printf("Ban Chon Chuc Nang:");
		ch = getch();
		if (ch>'0'&& ch <='6') {
			printf("%c",ch);
			getch();
		}
		switch (ch){
			case '1':
				clrscr();
				printf("****************** Noi Suy Lagrang ****************\n");
				printf("Nhap vao so diem n=");
				scanf("%d",&n);
				n--;
				P = new Diem[n+1];
				NhapDiem(P,n);
				XuatDiem(P,n);
				XuatDT(NoiSuy(P,n),n,"\n\n************ Da Thuc Noi Suy Tuong Ung *************\nP(x) ");
				delete P;
				getch();
				GiaoDien();
				break;

			case '2':
				clrscr();
				printf("***** Noi Suy Newton Tien Voi Cac Nut Noi Suy Khong Cach Dieu *****\n");
				printf("Nhap vao n=");
				scanf("%d",&n);
				P = new Diem[n+1];
				NhapDiem(P,n);
				XuatDiem(P,n);
				Newton_KCD_Tien(P,n);
				delete P;
				getch();
				GiaoDien();
				break;

			case '3':
				clrscr();
				printf("***** Noi Suy Newton Lui Voi Cac Nut Noi Suy Khong Cach Dieu *****\n");
				printf("Nhap vao n=");
				scanf("%d",&n);
				P = new Diem[n+1];
				NhapDiem(P,n);
				XuatDiem(P,n);
				TyHieu_KCD(A,P,n);
				Xuat_TyHieu(A,P,n);
				delete P;
				getch();
				GiaoDien();
				break;

			case '4':
				clrscr();
				printf("***** Noi Suy Newton Lui Voi Cac Nut Noi Suy Cach Dieu *****\n");
				printf("Nhap vao n=");
				scanf("%d",&n);
				P = new Diem[n+1];
				NhapDiem(P,n);
				XuatDiem(P,n);
				TyHieu_CD(A,P,n);
				Xuat_TyHieu(A,P,n);

				getch();
				GiaoDien();
				break;

			case '5':
				clrscr();
				printf("***** Noi Suy Newton Lui Voi Cac Nut Noi Suy Cach Dieu *****\n");
				printf("Nhap vao n=");
				scanf("%d",&n);
				P = new Diem[n+1];
				NhapDiem(P,n);
				XuatDiem(P,n);
				TyHieu_CD(A,P,n);
				Xuat_TyHieu(A,P,n);
				getch();
				GiaoDien();
				break;

			case '6': Thoat=0; break;
		}
	 }
}