polynom.cpp

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

using namespace std;

typedef vector<double> vd;

const int MAX = 10;
double LEFT_BORDER = -1e2;
double RIGHT_BORDER = 1e2;
int N = 5;

double polynom[MAX][MAX];
double e = 0.001;
vd extremum[MAX];

void getDerivative(int n);
void print();
double f(int n, double x);
bool bs(double l, double r, int n, double &ans);
void getExtrem(int n);

int main(){

    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
            polynom[i][j] = 0;

    for (int i = 1; i <= 6; i++){
        cin >> polynom[0][6 - i];
    }
    cin >> e;
    for (int i = 1; i <= 5; i++)
        getDerivative(i);
    for (int i = 4; i >= 0; i--)
        getExtrem(i);
    for (int i = 0; i < extremum[0].size(); i++)
        cout << (float)extremum[0][i] << " " << f(0, extremum[0][i]) << endl;

    return 0;
}

void getDerivative(int n){
    if (n < 1)
        return;
    for (int i = 0; i < MAX - 1; i++){
        polynom[n][i] = polynom[n - 1][i + 1] * (i + 1);
    }
}

void print(){
    for (int i = 0; i < MAX; i++){
        for (int j = 0; j < MAX; j++)
            cout << polynom[i][j] << " ";
        cout << endl;
    }
}

double f(int n, double x){
    double ans = 0;
    for (int i = 0; i < MAX; i++){
        ans += polynom[n][i] * pow(x, i);
    }
    return ans;
}

bool bs(double l, double r, int n, double &ans){
    double m;
    if (f(n, l) * f(n, r) > 0)
        return false;
    while (abs(r - l) > e){
        m = (l + r) / 2;
        if (f(n, m) * f(n, l) > 0)
            l = m;
        else
            r = m;
    }
    ans = m;
    return true;
}

void getExtrem(int n){
    extremum[n].resize(0);
    if (n == N - 1){
        extremum[n].push_back(-polynom[n][0] / polynom[n][1]);
        return;
    }
    double l, r, tmp_ans;
    if (!extremum[n + 1].size()){
        l = LEFT_BORDER;
        r = RIGHT_BORDER;
        if (bs(l, r, n, tmp_ans)){
            extremum[n].push_back(tmp_ans);
        }
        return;
    }

    for (int i = 0; i < extremum[n + 1].size(); i++){
        if (i == 0)
            l = LEFT_BORDER;
        else
            l = r;
        r = extremum[n + 1][i];
        if (bs(l, r, n, tmp_ans)){
            extremum[n].push_back(tmp_ans);
        }
    }
    l = r;
    r = RIGHT_BORDER;
    if (bs(l, r, n, tmp_ans)){
            extremum[n].push_back(tmp_ans);
        }
}

//1.0 2.5 -1.0 -3.5 -1.0 0.1
//ans : -2.377 -0.944 -0.466 0.078 1.215