Code:
#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;
}
}
}