Fibonacci

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

// нулевой элемент - 1, первый элемент - 1, второй - 2
int fibonacci_simple(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        return fibonacci_simple(n - 1) + fibonacci_simple(n - 2);
    }
}

int fibonacci_optimized(int n, vector<int>& arr)
{
    if (arr[n] == 0)
    {
        arr[n] = fibonacci_optimized(n - 1, arr) + fibonacci_optimized(n - 2, arr);
    }

    return arr[n];
}

int main()
{
    int n;

    cin >> n;

    cout << "fibonacci_simple(" << n <<  ") = ";
    int t1 = clock();
    cout << fibonacci_simple(n) << endl;
    int t2 = clock();

    cout << double(t2 - t1) / CLOCKS_PER_SEC << "sec." << endl;

    cout << "fibonacci_optimized(" << n <<  ") = ";
    t1 = clock();

    vector<int> arr(1000000, 0); // это шо то типа массива но умнее
    arr[0] = arr[1] = 1;

    cout << fibonacci_optimized(n, arr) << endl;
    t2 = clock();

    cout << double(t2 - t1) / CLOCKS_PER_SEC << "sec.";


}