import java.io.*;

class SCO11C
{ 
   public static double[][]  Newton(double xi[],double yi[])
  {
	 int n=xi.length;
	 double F[][]=new double[n+1][n];
	 for(int i=0;i<n;i++)
	    F[i][0]=yi[i];	    
     for(int i=1;i<n;i++)
     { for(int j=1;j<=i;j++)
         {F[i][j]=(F[i][j-1]-F[i-1][j-1])/(xi[i]-xi[i-j]);}
     }
     for(int i=0;i<n;i++)
     {F[n][i]=xi[i];}
     //System.out.println(Matrix.toString(F));
     return F;
  }
  	
  public static double  funcNewton(double F[][],double x)
  {
	 int n=F[0].length;
     double carpim=1.0;
     double toplam=0;
     for(int i=0;i<n;i++)
       {   carpim=F[i][i];
	       for(int j=0;j<=(i-1);j++)
          {carpim*=(x-F[n][j]);}
          toplam+=carpim;
       }
     return toplam; 
  }
  
 public static double[][]  funcNewton(double xi[],double yi[],int aradegersayisi)
 {
	//aradegersayisi:  x--o--o--x--o--o--x zincirinde x deneysel noktalar ise
	// ara değer sayısı 2 dir
	int n=xi.length;
	int nn=(n-1)*(aradegersayisi+1)+1;
	double z[][]=new double[2][nn];
    double Q[][]=Newton(xi,yi);	
    double dx=0;
    int k=0;
    int i;
    for(i=0;i<(n-1);i++)
       {  z[0][k]=xi[i];z[1][k]=funcNewton(Q,z[0][k]);k++;
          for(int j=0;j<aradegersayisi;j++) 
             {dx=(xi[i+1]-xi[i])/((double)aradegersayisi+1.0);
          z[0][k]=z[0][k-1]+dx;z[1][k]=funcNewton(Q,z[0][k]);k++;}
       }
       z[0][k]=xi[i];z[1][k]=funcNewton(Q,z[0][k]);
    return z;
 }
      
  public static void main(String args[]) throws IOException
  {
  double x[]={1940,1950,1960,1970,1980,1990};
  double y[]={132165,151336,179323,203302,226542,249633};
  double z1[][]=funcNewton(x,y,9);
  System.out.println("Newton interpolasyonu\n"+Matrix.toStringT(z1)); 
  Text.print(Text.T(z1),"Newton interpolasyonu");
  Plot pp=new Plot(x,y);
  pp.setPlabel("Newton interpolasyon yöntemi eğri uydurma");
  pp.setPlotType(0,20); 
  pp.addData(z1[0],z1[1]);
  pp.plot();
  }
}