फाइबोनैचि संख्याओं को आमतौर पर Fn द्वारा दर्शाया जाता है जो एक अनुक्रम बनाते हैं, जिसे फाइबोनैचि अनुक्रम कहा जाता है, यानी प्रत्येक संख्या पिछली दो संख्याओं का योग होती है, जो 0 और 1 से शुरू होती है। वह है:
F₀ = 0 और F₁ = 1 और Fn = Fₙ₋₁ + Fₙ₋₂ n > 1 के लिए।
एल्गोरिदम
Begin
दो 2-डायमेंशनल ऐरे लें
एक फंक्शन बनाएं और मैट्रिक्स गुणा करें
मैट्रिक्स की पावर ढूंढने के लिए दूसरा फंक्शन बनाएं
फाइबोनैचि नंबर ढूंढने के लिए एक फंक्शन बनाएं
Multiply(arr1[2][2], arr2[2][2])
4 वेरिएबल a, b, c, d लें
a = arr1[0][0] * arr2[0][0] + arr1[0][1] * arr2[1][0]
b = arr1[0][0] * arr2[0][1] + arr1[0][1] * arr2[1][1]
c = arr1[1][0] * arr2[0][0] + arr1[1][1] * arr2[1][0]
d = arr1[1][0] * arr2[0][1] + arr1[1][1] * arr2[1][1]
arr1[0][0] = a
arr1[0][1] = b
arr1[1][0] = c
arr1[1][1] = d
Power(arr1[2][2], n को इंटीजर के रूप में लें)
यदि (n == 0 या n == 1) लौटाएं;
arr1[2][2] = {{1,1}, {1,0}}
power(arr1, n / 2)
multiply(arr1, arr1)
यदि (n mod 2 != 0)
multiply(arr1, arr2)
fibonacci_matrix(n)
arr1[2][2] = {{1,1}, {1,0}}
यदि n == 0 तो 0 लौटाएं
power(arr1, n - 1)
arr1[0][0] लौटाएं
End
उदाहरण कोड
#include <iostream>
using namespace std;
void multiply(int F[2][2], int M[2][2]) {
int a = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int b = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int c = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int d = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = a;
F[0][1] = b;
F[1][0] = c;
F[1][1] = d;
}
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);
}
int fibonacci_matrix(int n) {
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
int main() {
int n;
while (1) {
cout << "Enter the integer n to find nth fibonacci no. (enter 0 to exit): ";
cin >> n;
if (n == 0) break;
cout << fibonacci_matrix(n) << endl;
}
return 0;
}
आउटपुट
Enter the integer n to find nth fibonacci no. (enter 0 to exit): 2 1 Enter the integer n to find nth fibonacci no. (enter 0 to exit): 6 8 Enter the integer n to find nth fibonacci no. (enter 0 to exit): 7 13 Enter the integer n to find nth fibonacci no. (enter 0 to exit): 0