#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

double f(int rzad,vector<double> C,double X)
{
    double wynik;

}

double wspolczynnik_c(vector<double> &X, vector<double> &Y, int l, int r) {
    if (r - l == 1) {
        return Y[l];
    } else if (r - l == 2) {
        return (Y[l] - Y[r]) / (X[l] - X[r]);
    } else {
        int l1 = l;
        int r1 = r - 1;
        int l2 = l + 1;
        int r2 = r;

        return (wspolczynnik_c(X, Y, l1, r1) - wspolczynnik_c(X, Y, l2, r2)) / (X[l] - X[r]);
    }
}



int main()
{
    vector<double> X;
    vector<double> Y;
    vector<double> C;
    int rzad,pkt,j,i=0,k=1;
    double a;
    cout << "Podaj ilosc punktow do interpolacji: " << endl;
    cin >> pkt;
    cout << "Podaj zakladany rzad funkcji: " << endl;
    cin >> rzad;
    for(pkt;pkt>0;pkt--)
    {
        cout << "Podaj X: "<<endl;
        cin >> a;
        X.push_back(a);
        cout << "Podaj f(" << X[i] << "): " << endl;
        cin >> a;
        Y.push_back(a);
        i++;
    }
    for(i=0;i<rzad;i++)
    {

        a=wspolczynnik_c(X,Y, 0, X.size() - 1 - i);
        cout<<a<<endl;
        C.push_back(a);
    }
    cout << "Interpolacja rzedu " << rzad << " dla podanych punktow wyglada nastepujaco: " << endl << C[C.size()-1];
    for(i=0;i<rzad;i++)
    {
        int x=0;
        cout << " + ";
        cout << C[C.size()-(i+2)];
        for(j=k;j>i;j--)
        {
            cout << "(X-" << X[x] << ")";
            x++;
        }
        k+=2;
    }
    return 0;
}