C++ প্রোগ্রাম: ম্যাট্রিক্স এক্সপোনেনশিয়েশন ব্যবহার করে ফিবোনাচ্চি নম্বর বের করা

ফিবোনাচ্চি নম্বরها, সাধারণত Fn দিয়ে চিহ্নিত, একটি সিকোয়েন্স তৈরি করে, যাকে ফিবোনাচ্চি সিকোয়েন্স বলা হয়। অর্থাৎ প্রতিটি নম্বর তার আগের দুটি নম্বরের যোগফল, ০ এবং ১ থেকে শুরু। সেটি হলো -

F0 = 0 এবং F1 = 1
And Fn = Fn-1 + Fn-2 for n > 1.

অ্যালগরিদম

শুরু
  দুটি 2-ডাইমেনশনাল অ্যারে নিন
  একটি ফাংশন তৈরি করুন এবং ম্যাট্রিক্স মাল্টিপ্লিকেশন করুন
  আরেকটি ফাংশন তৈরি করুন ম্যাট্রিক্সের পাওয়ার বের করতে
  একটি ফাংশন তৈরি করুন ফিবোনাচ্চি নম্বর বের করতে
  Multiply(arr1[2][2], arr2[2][2])
  ৪টি ভেরিয়েবল 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 নিন)
  if (n == 0 or n == 1) return;
  arr1 [2][2] = {{1,1}, {1,0}}
  power(arr1, n / 2)
  multiply(arr1, arr1)
  if (n mod 2 != 0)
    multiply(arr1, arr2)
  fibonacci_matrix(n)
  arr1[2][2] = {{1,1},{1,0}}
  if n == 0 return 0
  power(arr1, n - 1)
  return arr1[0][0]
শেষ

উদাহরণ কোড

#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