class Interpolacja{

    double Newton(double[] X, double[] Y, double wartoscX ){

    	int n=X.length;
    	double[][] tab = new double[n][n+1];
    	double y=0;
    	double w=1;
    	int k=0;

        for(int i=0;i<Y.length;i++){
            tab[i][0]=Y[i];
        }
        for(int i=0;i<n;i++){
            try{
              for(int j=0; j<n-1;j++){
                  tab[j][i+1]=((tab[j+1][i])-(tab[j][i]))/((X[j+1+k])-(X[j]));
               }
            }
            catch(Exception e){}
              k++;
              y=y+tab[0][i]*w;
              w=w*(wartoscX-X[i]);
        }
      return y;
   }
}

public class Newton{

    public static void main(String[] args){

    	double[] x = {-4,-2,0,2,4};
        double[] y = {-116,-20,4,4,28};
        double wartosc_x = 3;

        Interpolacja interpolacja = new Interpolacja();
        System.out.println("Interpolacja Newtona wynosi: " +interpolacja.Newton(x,y,wartosc_x) + " dla x="+wartosc_x );
    }
}