[C++] Fibonacci Algorithm

/*Simple Fibonacci function

Time Complexity: O(N)

*/

#include <iostream>

using namespace std;
int FiboLoop(int n){
    int before=0, cur=1, i, temp;

    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else{
        for (i = 1; i < n; i++){
            temp = cur;
            cur = before + cur;
            before = temp;
        }
        return cur;
    }
}



/*
Recursive Fibonacci function

Time Complexity : O(2^N)

It's not working when n is big because of 'stack overflow'. The function 'fibonacci' calls 2 functions recursively.

*/



#include <iostream>

using namespace std;
int fibonacci(int n){
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);  //making double recursive calls
}
}

int main() {
int n;
cin >> n;
cout << fibonacci(n) << '\n';
return 0;
}




/* Tail Recursion
Time Complexity: O(N)
*/

int FiboTail (int n){
return FiboTailRec(n, 0, 1);
}

int FiboTailRec(int n, int before, int next){
if (n==0)
return before;
else
return FiboTailRec(n-1, next, before + next);
}



/*
Added Memoization Fibonacci

Time Complexity: O(N)

Time complexity is O(2^N) initially.

*/

#include <iostream>

using namespace std;
int memo[50];

int fibonacci (int n) {
if (n <=1 ){
return n;
} else if (memo[n] != 0) {
return memo[n];
} else {
return memo[n] = fibonacci(n-1) + fibonacci(n-2);
}
}

int main() {
int n;
cin >> n;
cout << fibonacci(n) << '\n';
return 0;
}


/*
Another way using memoization

*/

#include <iostream>

using namespace std;
long long fibo[100] = {0,1};

int main() {
int n;
cin >> n;
for (int i=2; i<=n; i++) {
fibo[i] = fibo[i-1] + fibo[i-2];
}
cout << fibo[n] << '\n';
return 0;
}




/*
Using matrix & Divide and Conquer

Time Complexity :O(log2(N))


Fibonacci matrix

we can make O(log2(n)) with this, but we can make even faster. See below.






(n is even)

(n is odd) (*because it lost 1 when it's                    devided n by 2)






*/


#include <iostream>

using namespace std;

struct Matrix_2x2
{
unsigned long f[2][2];
};

Matrix_2x2 multiply(Matrix_2x2 A, Matrix_2x2 B)  // matrix multiply function.
{
Matrix_2x2 C;
C.f[0][0] = A.f[0][0] * B.f[0][0] + A.f[0][1] * B.f[1][0];
C.f[0][1] = A.f[0][0] * B.f[0][1] + A.f[0][1] * B.f[1][1];
C.f[1][0] = A.f[1][0] * B.f[0][0] + A.f[1][1] * B.f[1][0];
C.f[1][1] = A.f[1][0] * B.f[0][1] + A.f[1][1] * B.f[1][1];

return C;
}

Matrix_2x2 Matrix_Power(Matrix_2x2 A, int n)
{
if (n > 1)
{
A = Matrix_Power(A, n/2);
A = multiply(A, A);          //A^n = A^(n/2) * A^(n/2)

if (n & 1)     // n is odd
{
Matrix_2x2 F1 = {1,1,1,0};
A = multiply(A, F1);
}
}

return A;
}

int main()
{
int n;
cin >> n;
Matrix_2x2 F1 = {1,1,1,0};
F1 = Matrix_Power(F1, n);
cout << n << "th Fibonacci" << F1.f[0][1] << endl;

return 0;
}



//
Reference

될성부른떡잎의 음주프로그래밍
http://ledgku.tistory.com/38

피보나치 수를 구하는 여러가지 방법
https://www.acmicpc.net/blog/view/28

행렬과 분할정복 기반의 피보나치 수 알고리즘
http://nukestorm.tistory.com/149