#include <conio.h>
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

double e = 2.71828182846;

double f(double x) {
    return pow(e, x);
}

double F(int n) {
    return (pow(((1 + sqrt(5)) / 2.0), n) - pow(((1 - sqrt(5)) / 2.0), n)) / sqrt(5);
}

void DichotomyMethod(double EPSILON, double a, double b) {
    ofstream fout("dichotomy.txt");
    double x1, x2;
    double d = EPSILON / 2.0;
    double q;

    for (int i = 1; b - a > EPSILON; i++) {
        x1 = (a + b - d) / 2;
        x2 = (a + b + d) / 2;

        q = b - a;

        fout << i << " " << a << " " << b << " " << b - a << " ";

        if (f(x1) < f(x2))
            b = x2;
        else a = x1;

        fout << b - a << " " << q / (b - a) << endl;
    }
 }

void GoldenSectionMethod(double EPSILON, double a, double b) {
    ofstream fout("goldenSection.txt");
    double x1, x2;
    double q;
    int flag = 0;

    x1 = a + (3 - sqrt(5)) / 2.0 * (b - a);
    x2 = a + (sqrt(5) - 1) / 2.0 * (b - a);

    double f1 = f(x1);
    double f2 = f(x2);
    q = b - a;

    for (int i = 1; b - a > EPSILON; i++) {
        fout << i << " " << a << " " << b << " " << b - a << " ";
        if (f1 < f2) {
            b = x2;
            x2 = x1;
            f2 = f1;
            flag = 1;
        }
        else {
            a = x1;
            x1 = x2;
            f1 = f2;
            flag = 0;
        }
        fout << b - a << " " << q / (b - a) << endl;
        q = b - a;

        if (flag) {
            x1 = a + (3 - sqrt(5)) / 2.0 * (b - a);
            f1 = f(x1);
        }
        else {
            x2 = a + (sqrt(5) - 1) / 2.0 * (b - a);
            f2 = f(x2);
        }
    }
}

void FibonacciMethod(double EPSILON, double a, double b) {
    ofstream fout("Fibonacci.txt");
    double x1, x2;
    double q = b - a;
    int n;

    for (n = 7; F(n) < (b - a) / EPSILON; n++);

    x1 = a + (F(n - 2) / F(n)) * (b - a);
    x2 = a + (F(n - 1) / F(n)) * (b - a);

    double f1 = f(x1);
    double f2 = f(x2);

    for (int i = 0; i < n - 3; i++) {
        if (f1 < f2) {
            b = x2;
            x2 = x1;
            f2 = f1;
            x1 = a + (F(n - i - 3) / F(n - i - 1)) * (b - a);
            f1 = f(x1);
        }
        else {
            a = x1;
            x1 = x2;
            f1 = f2;
            x2 = a + (F(n - i - 2) / F(n - i - 1)) * (b - a);
            f2 = f(x2);
        }
        fout << i + 1 << " " << a << " " << b << " " << b - a << " ";
        fout << b - a << " " << q / (b - a) << endl;
        q = b - a;
    }
    x2 = x1 + EPSILON;
    f2 = f(x2);
    if (f1 < f2)
        b = x1;
    else a = x1;

    fout << n - 2 << " " << a << " " << b << " " << b - a << " ";
    fout << b - a << " " << q / (b - a) << endl;
}

void findInterval(double h) {
    double x = 50;
    double start = x;
    int numberIteration = 0;
    ofstream out("interval.txt");

    if (f(x) > f(x + h))
        x = x + h;
    else
    {
        x = x - h;
        h = -h;
    }

    out << "Number of iteration " << setw(20) << left << "Current interval " << endl;

    while (f(x) > f(x + h)) {
        if (x < 0)
            break;
        x = x + h;
        numberIteration++;
        out << numberIteration << "\t" << "[" << x << ";" << start << "]" << "\t" << endl;
    }

}

void main() {
    double EPSILON;
    double a = 0, b = 100;
    cout << "EPSILON?" << endl;
    cin >> EPSILON;
    cout << "Dichotomy Method" << endl;
    DichotomyMethod(EPSILON, a, b);
    cout << "Golden Section Method" << endl;
    GoldenSectionMethod(EPSILON, a, b);
    cout << "Fibonacci Method" << endl;
    FibonacciMethod(EPSILON, a, b);
    cout << "Find Interval" << endl;
    findInterval(0.1);
    _getch();
}