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;
      }
    }
}