Untitled

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <chrono>

using namespace std;

int Fibo(int n){
    if (n<=1)
        return n;
    return Fibo(n-1) + Fibo(n-2);
}

int FastFibo(int n){
    if (n<=1)
        return n;
    int index=0, lastIndex=0;
    int A[3];
    A[0] = 0;
    A[1] = 1;
    index = 2;
    while (n-1){
        // cout << "index:　" << index << '\n';
        switch(index){
            case 2:
                A[index] = A[index-1] + A[index-2];
                break;
            case 0:
                A[index] = A[index+1] + A[index+2];
                break;
            case 1: 
                A[index] = A[index-1] + A[index+1];
                break;
            default:
                break;
        }
        // cout << A[0] << ' ' << A[1] << ' ' << A[2] << '\n';
        lastIndex = index;
        index = (index + 1) % 3;
        n -= 1;
    }
    return A[lastIndex];
}

int main()
{
    int res1, res2;
    
    int n = 20;
    
    auto begin = std::chrono::high_resolution_clock::now();
    res1 = Fibo(n);
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    
    begin = std::chrono::high_resolution_clock::now();
    res2 = FastFibo(n);
    end = std::chrono::high_resolution_clock::now();
    auto elapsed2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    
    cout << res1 << ' ' << '\n';
    printf("Result: %.20f\n", elapsed1);
    
    cout << res2 << ' ' << '\n';
    printf("Result: %.20f\n", elapsed2);
    return 0;
}