// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <time.h>
using namespace std;
//u=(x-a)/h
float u_cal(float u, int n)
{
	float temp = u;
	for (int i = 1; i < n; i++)
		temp = temp * (u - i);
	return temp;
}
int fact(int n)
{
	int f = 1;
	for (int i = 2; i <= n; i++)
		f *= i;
	return f;
}
void newt(float **a,float *x,int n,float value) {

	for (int 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]; //
	}
	float sum = a[0][0];
	float u = (value - x[0]) / (x[1] - x[0]);
	for (int i = 1; i < n; i++) {
		sum = sum + (u_cal(u, i) * a[0][i]) /
			fact(i);
	}
	cout << "\n Value at " << value << " is "
		<< sum << endl;
}

int main()
{
	srand(time(NULL));

	int rowCount = 5, colCount = 5;

	float *x = new float[rowCount];
	float** a = new float*[rowCount];

	for (int i = 0; i < rowCount; ++i)
		a[i] = new float[colCount];

	for (int i = 0,j=0; i < rowCount; ++i) {
		cout << " x" << i << ": ";
		cin >> x[i];
		cout << " y" << i << ": ";
		cin >> a[i][j];
		cout << endl;

	}
	float value;
	cout << "interpolate to value: "; cin >> value;


	newt(a, x, 5,value);

	for (int i = 0; i < rowCount; ++i) {
	delete[] a[i];
	}
	delete[] a;


    return 0;
}