行列累乗法を使ってフィボナッチ数を求めるC++プログラム

フィボナッチ数は通常 F_n と表記され、フィボナッチ数列と呼ばれる数列を構成します。これは「各項が直前の2つの項の和になる」という性質を持つ数列で、0 と 1 から始まります。すなわち −

F0 = 0、F1 = 1
そして
Fn = Fn-1 + Fn-2(n > 1 のとき)

行列累乗法によるアプローチ

単純な再帰や反復処理でもフィボナッチ数は求められますが、行列の累乗計算を利用すると O(log n) の時間計算量で n 番目のフィボナッチ数を高速に求めることができます。これは、次の恒等式に基づいています。

{{1,1},{1,0}}n = {{Fn+1, Fn}, {Fn, Fn-1}}

アルゴリズム

Begin
   2×2 の二次元配列を2つ用意する
   行列の乗算を行う関数を作成する
   行列のべき乗を計算する別の関数を作成する
   フィボナッチ数を求める関数を作成する
   multiply(arr1[2][2], arr2[2][2])
   変数 a, b, c, d を4つ宣言する
   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 または n == 1)
      return;
   arr1[2][2] = {{1,1}, {1,0}}
   power(arr1, n / 2)
   multiply(arr1, arr1)
   if (n を 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]
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<<"n番目のフィボナッチ数を求める整数nを入力してください(0で終了):";
      cin>>n;
      if (n == 0)
         break;
      cout<<fibonacci_matrix(n)<<endl;
   }
   return 0;
}

実行結果

n番目のフィボナッチ数を求める整数nを入力してください(0で終了): 2
1
n番目のフィボナッチ数を求める整数nを入力してください(0で終了): 6
8
n番目のフィボナッチ数を求める整数nを入力してください(0で終了): 7
13
n番目のフィボナッチ数を求める整数nを入力してください(0で終了): 0

コードの解説

• multiply 関数: 2×2 行列同士の積を計算し、結果を最初の行列 F に格納します。
• power 関数: 繰り返し二乗法(バイナリ法)を用いて行列の n 乗を効率的に計算します。再帰的に n/2 乗を求めてから自乗し、n が奇数の場合は基底行列をさらに掛けます。
• fibonacci_matrix 関数: 基底行列 {{1,1},{1,0}} の (n−1) 乗を計算し、左上の要素 F[0][0] を返すことで n 番目のフィボナッチ数を得ます。

この方法により、大きな n に対しても従来の O(n) の線形探索よりも大幅に高速な計算が可能になります。