Generalized Fibonacci Numbers
We all know that Fibonacci numbers (Fn) are defined by the recurrence relation
Fibonacci Numbers (Fn) = F(n-1) + F(n-2)
with seed values
F0 = 0 and F1 = 1
Similarly, we can generalize these numbers. Such a number sequence is known as Generalized Fibonacci number (G).
Generalized Fibonacci number (G) is defined by the recurrence relation
Generalized Fibonacci Numbers (Gn) = (c * G(n-1)) + (d * G(n-2))
with seed values
G0 = a and G1 = b
Finding Nth term
Given the four constant values of Generalized Fibonacci Numbers as a, b, c, and d and an integer N, the task is to find the Nth term of the Generalized Fibonacci Numbers, i.e. Gn.
Examples:
Input: N = 2, a = 0, b = 1, c = 2, d = 3
Output: 2
Explanation:
As a = 0 -> G(0) = 0
b = 1 -> G(1) = 1
So, G(2) = 2 * G(1) + 3 * G(0) = 2Input: N = 3, a = 0, b = 1, c = 2, d = 3
Output: 7
Naive Approach: Using the given values, find each term of the series till the Nth term and then print the Nth term.
Time Complexity: O(2N)
Another Approach: The idea is to use DP tabulation to find all the terms till the Nth terms and then print the Nth term.
Time Complexity: O(N)
Efficient Approach: Using matrix multiplication we can solve the given problem in log(N) time.
Below is the implementation of the above approach:
C++
// C++ program to implement the // Generalised Fibonacci numbers #include <bits/stdc++.h> using namespace std; // Helper function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] void multiply( int F[2][2], int M[2][2]); // Helper function that calculates F[][] // raised to the power N // and puts the result in F[][] void power( int F[2][2], int N, int m, int n); // Function to find the Nth term int F( int N, int a, int b, int m, int n) { // m 1 // n 0 int F[2][2] = { { m, 1 }, { n, 0 } }; if (N == 0) return a; if (N == 1) return b; if (N == 2) return m * b + n * a; int initial[2][2] = { { m * b + n * a, b }, { b, a } }; power(F, N - 2, m, n); // Discussed above multiply(initial, F); return F[0][0]; } // Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] 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; } // Function that calculates F[][] // raised to the power N // and puts the result in F[][] void power( int F[2][2], int N, int m, int n) { int i; int M[2][2] = { { m, 1 }, { n, 0 } }; for (i = 1; i <= N; i++) multiply(F, M); } // Driver code int main() { int N = 2, a = 0, b = 1, m = 2, n = 3; printf ( "%d\n" , F(N, a, b, m, n)); N = 3; printf ( "%d\n" , F(N, a, b, m, n)); N = 4; printf ( "%d\n" , F(N, a, b, m, n)); N = 5; printf ( "%d\n" , F(N, a, b, m, n)); return 0; } |
Java
// Java program to implement the // Generalised Fibonacci numbers import java.util.*; class GFG{ // Function to find the Nth term static int F( int N, int a, int b, int m, int n) { // m 1 // n 0 int [][] F = { { m, 1 }, { n, 0 } }; if (N == 0 ) return a; if (N == 1 ) return b; if (N == 2 ) return m * b + n * a; int [][] initial = { { m * b + n * a, b }, { b, a } }; power(F, N - 2 , m, n); // Discussed below multiply(initial, F); return F[ 0 ][ 0 ]; } // Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] static void multiply( int [][] F, int [][] M) { 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; } // Function that calculates F[][] // raised to the power N // and puts the result in F[][] static void power( int [][] F, int N, int m, int n) { int i; int [][] M = { { m, 1 }, { n, 0 } }; for (i = 1 ; i <= N; i++) multiply(F, M); } // Driver code public static void main(String[] args) { int N = 2 , a = 0 , b = 1 , m = 2 , n = 3 ; System.out.println(F(N, a, b, m, n)); N = 3 ; System.out.println(F(N, a, b, m, n)); N = 4 ; System.out.println(F(N, a, b, m, n)); N = 5 ; System.out.println(F(N, a, b, m, n)); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement the # Generalised Fibonacci numbers # Function to find the Nth term def F(N, a, b, m, n): # m 1 # n 0 F = [[ m, 1 ], [ n, 0 ]] if (N = = 0 ): return a if (N = = 1 ): return b if (N = = 2 ): return m * b + n * a initial = [[ m * b + n * b, b ], [ b, a ]] power(F, N - 2 , m, n) multiply(initial, F) return F[ 0 ][ 0 ] # Function that multiplies # 2 matrices F and M of size 2*2, # and puts the multiplication # result back to F[][] def multiply(F, M): x = (F[ 0 ][ 0 ] * M[ 0 ][ 0 ] + F[ 0 ][ 1 ] * M[ 1 ][ 0 ]) y = (F[ 0 ][ 0 ] * M[ 0 ][ 1 ] + F[ 0 ][ 1 ] * M[ 1 ][ 1 ]) z = (F[ 1 ][ 0 ] * M[ 0 ][ 0 ] + F[ 1 ][ 1 ] * M[ 1 ][ 0 ]) 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 # Function that calculates F[][] # raised to the power N # and puts the result in F[][] def power(F, N, m, n): M = [[ m, 1 ], [ n, 0 ]] for i in range ( 1 , N + 1 ): multiply(F, M) # Driver code if __name__ = = '__main__' : N, a, b, m, n = 2 , 0 , 1 , 2 , 3 print (F(N, a, b, m, n)) N = 3 print (F(N, a, b, m, n)) N = 4 print (F(N, a, b, m, n)) N = 5 print (F(N, a, b, m, n)) # This code is contributed by Shivam Singh |
C#
// C# program to implement the // Generalised Fibonacci numbers using System; class GFG{ // Function to find the Nth term static int F( int N, int a, int b, int m, int n) { // m 1 // n 0 int [,] F = { { m, 1 }, { n, 0 } }; if (N == 0) return a; if (N == 1) return b; if (N == 2) return m * b + n * a; int [,] initial = { { m * b + n * a, b }, { b, a } }; power(F, N - 2, m, n); // Discussed below multiply(initial, F); return F[0, 0]; } // Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[,] static void multiply( int [,] F, int [,] M) { 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; } // Function that calculates F[,] // raised to the power N // and puts the result in F[,] static void power( int [,] F, int N, int m, int n) { int i; int [,] M = { { m, 1 }, { n, 0 } }; for (i = 1; i <= N; i++) multiply(F, M); } // Driver code public static void Main(String[] args) { int N = 2, a = 0, b = 1, m = 2, n = 3; Console.WriteLine(F(N, a, b, m, n)); N = 3; Console.WriteLine(F(N, a, b, m, n)); N = 4; Console.WriteLine(F(N, a, b, m, n)); N = 5; Console.WriteLine(F(N, a, b, m, n)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement the // Generalised Fibonacci numbers // Function to find the Nth term function F(N, a, b, m, n) { var F = [ [ m, 1 ], [ n, 0 ] ] if (N == 0) return a; if (N == 1) return b; if (N == 2) return m * b + n * a; var initial = [ [ m * b + n * a, b ], [ b, a ] ] power(F, N - 2, m, n); // Discussed below multiply(initial, F); return F[0][0]; } // Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] function multiply(F, M) { var x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; var y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; var z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; var 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; } // Function that calculates F[][] // raised to the power N // and puts the result in F[][] function power(F, N, m, n) { var i; var M = [ [ m, 1 ], [ n, 0 ] ]; for (i = 1; i <= N; i++) multiply(F, M); } // Driver code var N = 2, a = 0, b = 1, m = 2, n = 3; document.write(F(N, a, b, m, n) + "</br>" ); N = 3; document.write(F(N, a, b, m, n) + "</br>" ); N = 4; document.write(F(N, a, b, m, n) + "</br>" ); N = 5; document.write(F(N, a, b, m, n)); // This code is contributed by Ankita saini </script> |
Output:
2 7 20 61