【C++】O(log n)時間・O(1)空間で実現！指定範囲内のフィボナッチ数の個数を数える方法

開始値と終了値からなる範囲が与えられたとき、その範囲内に存在するフィボナッチ数の総個数を、O(log n)時間・O(1)空間という制約のもとで計算する方法を解説します。

フィボナッチ数とは

フィボナッチ数とは、「フィボナッチ数列」と呼ばれる数列を構成する数のことであり、各項は直前の2つの項の和として定義されます。

具体的には、f(0) = 0、f(1) = 1 と固定されており、計算は3番目の項から始まります。

数列を計算するための公式は以下の通りです。

F_n = F_n-1 + F_n-2

ここで、

F₀ = 0、F₁ = 1

たとえば、次のような入出力が考えられます。

入力 − start = 6、last = 100
出力 − 数列中のフィボナッチ数の個数は 6

解説 − 6以上100以下のフィボナッチ数は 8、13、21、34、55、89 の6つです。したがって合計個数は6となります。

入力 − start = 0、last = 8
出力 − 数列中のフィボナッチ数の個数は 7

解説 − 0以上8以下のフィボナッチ数は 0、1、1、2、3、5、8 の7つです。したがって合計個数は7となります。

プログラムで使用するアプローチ

• 範囲を作成するための開始値（start）と終了値（last）を入力として受け取ります。

• 変数 fib1 を 0、fib2 を 1、fib3 を 1 として宣言し、初期化します。

• 結果を格納する一時変数 res を宣言し、0で初期化します。

• fib1 が last 以下である間、ループを繰り返します。

• ループ内では、fib1 が start 以上であれば res を1増やします。

• fib1 ← fib2、fib2 ← fib3、fib3 ← fib1 + fib2 と更新し、数列を進めます。

• ループ終了後、res を返します。

• 結果を出力します。

この手法では、フィボナッチ数列を順番に生成しながら範囲との大小比較を行うだけなので、配列などの追加メモリを必要とせず、空間計算量 O(1) を達成できます。また、フィボナッチ数は指数的に増加するため、last まで到達するまでに必要な反復回数は log n 回程度にとどまり、時間計算量 O(log n) が実現できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// start から last の範囲にある
// フィボナッチ数を数える関数
int count_fibonacci(int start, int last){
   // 最初の3つのフィボナッチ数
   int fib1 = 0, fib2 = 1, fib3 = 1;
   // フィボナッチ数の個数を数える res
   int res = 0;
   while (fib1 <= last){
      if (fib1 >= start){
         res++;
      }
      fib1 = fib2;
      fib2 = fib3;
      fib3 = fib1 + fib2;
   }
   return res;
}
// main関数
int main(){
   int start = 6, last = 100;
   cout << "数列中のフィボナッチ数の個数は "
   << count_fibonacci(start, last);
   return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

数列中のフィボナッチ数の個数は 6