polynom_approx.cpp

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <cmath>

using namespace std;

const double EPS = 0.01;

typedef long long int lli;
typedef unsigned long long ulli;
typedef double **matrix;
typedef vector<int> vi;
typedef vector<bool> vb;

double det(double** m, int l, vb used, int n);
double vandermond_det(double** m, int n);
double vandermond_det(double* m, int n);
void print_mat(double **mat, int m, int n);
double* pol_approx(double *m, double *b, int n);
double polynom(double *m, double x, int n);

int main(){

    vb used;
    int n;
    ifstream in_file("input.txt");
    in_file >> n;
//  double **mat = new double*[n];
//  for (int i = 0; i < n; i++)
//        mat[i] = new double[n];
//  for (int i = 0; i < n; i++)
//        for (int j = 0; j < n; j++)
//            in_file >> mat[i][j];
//  print_mat(mat, n, n);
    used.resize(n);
    for (int i = 0; i < n; i++)
        used[i] = false;
    double *x = new double[n];
    double *b = new double[n];
    for (int i = 0; i < n; i++)
        in_file >> x[i] >> b[i];

    double *coef = pol_approx(x, b, n);
    for (int i = n - 1; i >= 0; i--)
        cout << coef[i] << endl;
//    for (int i = 0; i < n; i++)
//        delete [] mat[i];
//    delete [] mat;
    in_file.close();
    return 0;
}

double det(double** m, int l, vb used, int n){
    if (l >= n)
        return 1;
    double sum = 0;
    int uneven_cnt = 0;
    for (int i = 0; i < n; i++){
        if (!used[i]){
            used[i] = true;
            sum += ((i + uneven_cnt)% 2 ? -1 : 1) * m[l][i] * det(m, l + 1, used, n);
            used[i] = false;
        }else
            uneven_cnt++;
    }
    return sum;
}

double vandermond_det(double** m, int n){
    double ans = 1;
    for (int i = n - 1; i >= 0; i--)
        for (int j = i - 1; j >= 0; j--)
            ans *= (m[i][1] - m[j][1]);
    return ans;
}

double vandermond_det(double* m, int n){
    double ans = 1;
    for (int i = n - 1; i >= 0; i--)
        for (int j = i - 1; j >= 0; j--)
            ans *= (m[i] - m[j]);
    return ans;
}

double* pol_approx(double *m, double *b, int n){
    double vand = vandermond_det(m, n), tmp;
    if (vand < EPS){
        cout << "nope" << endl;
        return NULL;
    }
    double **tmp_mat = new double*[n];
    double *ans = new double[n];
    for (int i = 0; i < n; i++)
        tmp_mat[i] = new double[n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            tmp_mat[i][j] = pow(m[i], j);
    vb used;
    used.resize(n);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            swap(tmp_mat[j][i], b[j]);
        ans[i] = det(tmp_mat, 0, used, n) / vand;
        for (int j = 0; j < n; j++)
            swap(tmp_mat[j][i], b[j]);
    }
    return ans;
}

double polynom(double *m, double x, int n){
    double ans = 0;
    for (int i = n - 1; i >= 1; i--){
        ans = (ans + m[i]) * x;
    }
    return ans + m[0];
}

void print_mat(double **mat, int m, int n){
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++)
            printf("%4.4f ", mat[i][j]);
        printf("\n");
    }
}