Write a function int fib(int n) that returns 
.
Method 2 ( Use Dynamic Programming )
Method 3 ( Space Otimized Method 2 )
Method 4 ( Using power of the matrix {{1,1},{1,0}} )
Method 5 ( Optimized Method 4 )
The method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the previous method.
http://www.geeksforgeeks.org/matrix-exponentiation/
What is the minimum time complexity to find n’th Fibonacci Number?
We can find n’th Fibonacci Number in O(Log n) time using Matrix Exponentiation.
Ways to represent a number as a sum of 1’s and 2’s
Read full article from Program for Fibonacci numbers | GeeksforGeeks
. Method 2 ( Use Dynamic Programming )
f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { /* Add the previous 2 numbers in the series and store it */ f[i] = f[i-1] + f[i-2]; } return f[n];int fib(int n){ int a = 0, b = 1, c, i; if( n == 0) return a; for (i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b;}
This another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.
The matrix representation gives the following closed expression for the Fibonacci numbers:
int fib(int n){ int F[2][2] = {{1,1},{1,0}}; if (n == 0) return 0; power(F, n-1); return F[0][0];}void power(int F[2][2], int n){ int i; int M[2][2] = {{1,1},{1,0}}; // n - 1 times multiply the matrix to {{1,0},{0,1}} for (i = 2; i <= n; i++) multiply(F, M);}The method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the previous method.
int fib(int n){ int F[2][2] = {{1,1},{1,0}}; if (n == 0) return 0; power(F, n-1); return F[0][0];}/* Optimized version of power() in method 4 */void power(int F[2][2], int n){ if( n == 0 || n == 1) return; int M[2][2] = {{1,1},{1,0}}; power(F, n/2); multiply(F, F); if (n%2 != 0) multiply(F, M);
}
void multiply(int F[2][2], int M[2][2]){ int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w;}What is the minimum time complexity to find n’th Fibonacci Number?
We can find n’th Fibonacci Number in O(Log n) time using Matrix Exponentiation.
F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3) for n >= 3
. . . . . Equation (1)
where a, b and c are constants.
For this recurrence relation it depends on three previous values.
Now we will try to represent Equation (1) in terms of matrix.
[First Matrix] = [Second matrix] * [Third Matrix]
| F(n) | = Matrix 'C' * | F(n-1) |
| F(n-1) | | F(n-2) |
| F(n-2) | | F(n-3) |
Dimension of the first matrix is 3 x 1 .
Dimension of third matrix is also 3 x 1.
So the dimension of the second matrix must be 3 x 3
[For multiplication rule to be satisfied.]
Now we need to fill the Matrix 'C'.
So according to our equation.
F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3)
F(n-1) = F(n-1)
F(n-2) = F(n-2)
C = [a b c
1 0 0
0 1 0]
Now the relation between matrix becomes :
[First Matrix] [Second matrix] [Third Matrix]
| F(n) | = | a b c | * | F(n-1) |
| F(n-1) | | 1 0 0 | | F(n-2) |
| F(n-2) | | 0 1 0 | | F(n-3) |
Lets assume the initial values for this case :-
F(0) = 0
F(1) = 1
F(2) = 1
So, we need to get F(n) in terms of these values.
So, for n = 3 Equation (1) changes to
| F(3) | = | a b c | * | F(2) |
| F(2) | | 1 0 0 | | F(1) |
| F(1) | | 0 1 0 | | F(0) |
void multiply(int a[3][3], int b[3][3]){ // Creating an auxiliary matrix to store elements // of the multiplication matrix int mul[3][3]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { mul[i][j] = 0; for (int k = 0; k < 3; k++) mul[i][j] += a[i][k]*b[k][j]; } } // storing the muliplication resul in a[][] for (int i=0; i<3; i++) for (int j=0; j<3; j++) a[i][j] = mul[i][j]; // Updating our matrix}// Function to compute F raise to power n-2.int power(int F[3][3], int n){ int M[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}}; // Multiply it with initial values i.e with // F(0) = 0, F(1) = 1, F(2) = 1 if (n==1) return F[0][0] + F[0][1]; power(F, n/2); multiply(F, F); if (n%2 != 0) multiply(F, M); // Multiply it with initial values i.e with // F(0) = 0, F(1) = 1, F(2) = 1 return F[0][0] + F[0][1] ;}// Return n'th term of a series defined using below// recurrence relation.// f(n) is defined as// f(n) = f(n-1) + f(n-2) + f(n-3), n>=3// Base Cases :// f(0) = 0, f(1) = 1, f(2) = 1int findNthTerm(int n){ int F[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}} ; return power(F, n-2);}Ways to represent a number as a sum of 1’s and 2’s
Given a positive integer N. The task is to find the number of ways of representing N as a sum of 1s and 2s.
For N = 1, answer is 1.
For N = 2. (1 + 1), (2), answer is 2.
For N = 3. (1 + 1 + 1), (2 + 1), (1 + 2), answer is 3.
For N = 4. (1 + 1 + 1 + 1), (2 + 1 + 1), (1 + 2 + 1), (1 + 1 + 2), (2 + 2) answer is 5.
And so on.
For N = 2. (1 + 1), (2), answer is 2.
For N = 3. (1 + 1 + 1), (2 + 1), (1 + 2), answer is 3.
For N = 4. (1 + 1 + 1 + 1), (2 + 1 + 1), (1 + 2 + 1), (1 + 1 + 2), (2 + 2) answer is 5.
And so on.
It can be observe that it form Fibonacci Series. So, the number of ways of representing N as a sum of 1s and 2s is (N + 1)th Fibonacci number.
How ?
We can easily see that the recursive function is exactly same as Fibonacci Numbers. To obtain the sum of N, we can add 1 to N – 1. Also, we can add 2 to N – 2. And only 1 and 2 are allowed to make the sum N. So, to obtain sum N using 1s and 2s, total ways are: number of ways to obtain (N – 1) + number of ways to obtain (N – 2).
How ?
We can easily see that the recursive function is exactly same as Fibonacci Numbers. To obtain the sum of N, we can add 1 to N – 1. Also, we can add 2 to N – 2. And only 1 and 2 are allowed to make the sum N. So, to obtain sum N using 1s and 2s, total ways are: number of ways to obtain (N – 1) + number of ways to obtain (N – 2).
We can find N’th Fibonacci Number in O(Log n) time
void multiply(int F[2][2], int M[2][2]){ int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w;}// Power function in log nvoid power(int F[2][2], int n){ if( n == 0 || n == 1) return; int M[2][2] = {{1,1},{1,0}}; power(F, n/2); multiply(F, F); if (n%2 != 0) multiply(F, M);}/* function that returns (n+1)th Fibonacci number Or number of ways to represent n as sum of 1's 2's */int countWays(int n){ int F[2][2] = {{1,1},{1,0}}; if (n == 0) return 0; power(F, n); return F[0][0];}
