Interpolacja Newtona.cpp

/*Filename: MN03_Newton
Author: Peter_Wegrzyn
Date: 20.03.18

Kod jest dostosowany do danych z przykladu ze strony http://galaxy.agh.edu.pl/~mhojny/repozytoria/mn/InterpolacjaN.pdf
Jeżeli chce Ci sie wpisywać swoje dane to należy jedynie odkomentować zakomentowane linie oraz zakomentowac tworzenie tabeli.
*/

#include <iostream>
using namespace std;

float firstInstance(int * tabX, int *tabY, int i){	//Iloraz pierwszego rzadu


	return (tabY[i + 1] - tabY[i]) / (tabX[i + 1] - tabX[i]);
}

//Iloraz dowolnego rzedu  k - rzad oraz i - to index pierwszego x w tych smiesznych nawiasikach. (patrz wzor)
float Newton(int *tabX, int* tabY, int k, int i){
	if (k == 0)return 1;							//zwraca 1 na potrzeby petli ponizej.
	if (k == 1)return firstInstance(tabX, tabY, i);	//jezeli dojdziemy do pierwszego rzadu to zwracamy to co widac
	return	(Newton(tabX, tabY, k - 1, i + 1) - Newton(tabX, tabY, k - 1, i)) / (tabX[i+k] - tabX[i]);
	//rekurencyjnie wywolujemy sama siebie tylko rzad nizej oraz i jest ustawiane tak jak we wzorze

}
int main(){
	
	int x=1;
//	cout << "Wpisz szukany X";
//	cin >> x;
//	cout << "Wpisz liczbe punktow";
	int pointsQuantity=5;
	//cin >> pointsQuantity;
	
//	int * tabX = new int[pointsQuantity];
//	int * tabY = new int[pointsQuantity];
	int tabX[] = { -2,-1,0,2,4 };
	int tabY[] = { -1, 0, 5, 99, -55 };
/*	for (int  i = 0; i < pointsQuantity; i++)
	{
		cout << "Podaj X";
		cin >> tabX[i];
		cout << "Podaj Y";
		cin >> tabY[i];
	}
	*/

	float result=tabY[0]; //ustawiamy najpierw wynik na y0 bo tak jest we wzorze. 
	int tmp=0;			//pomocnicza zmienna ktora bedzie wynikem mnożenia tych wyrażen w nawiwiasach okraglych. sumujemy dla kazdego N (gdzie N to liczba punktów)
	for (int i = 0; i < pointsQuantity; i++)//wykonuje sie tyle razy ile jest punktow
	{
		tmp = 0;				//resetujemy sume iloczynow w nawiasach
		for (int j = 0; j < i; j++){	//wykonujemy i razy mnozenie tych wyrazen w nawiasach. (patrz wzor)
			if (j == 0)tmp = x - tabX[0];	//za pierwszym razem trzeba ustawic tmp bo potem pomnazamy inicjalna wartosc
			else tmp *= x - tabX[j];		//jak nie pierwszy raz to poprostu pomnoz tak jak we wzorze 
		}
		result += tmp*Newton(tabX,tabY,i,0);	//dodajemy do wyniku wynik mnozenia tych wyrazen w nawiasach okraglych (x-x0)(x-x1)..(x-xi) + cokolwiek zwraca funkcja czyli iloraz o i-tym rzędzie.
	}

	cout <<"Wynik dla x="<<x<<" to: "<< result;

	system("pause");
}