C ++のO（Log n）時間とO（1）空間で指定された範囲のフィボナッチ数を数えます

開始番号と終了番号の範囲が与えられ、タスクは、O（Log n）時間とO（1）空間の指定された範囲の間で利用可能なフィボナッチ数の総数を計算することです。

フィボナッチ数とは

フィボナッチ数は、フィボナッチ数列と呼ばれる数列であり、新しい数はすべて、前の2つの数の合計です。

ここで、f（0）=0およびf（1）=1、つまりf（0）およびf（1）はシーケンス内の固定位置にあり、計算は3番目の数値から開始されます。

シーケンスの計算に使用される式は-です

F _n =F _n-1 + F _n-2

どこで、

F ₀ =0、F ₁ = _l

例

Input − start = 6 and last = 100
Output − Number of fibonacci Numbers in the series are 6

説明 − 6〜100のフィボナッチ数は8、13、21、34、55、89です。つまり、合計数は6です

Input − start = 0 and last = 8
Output − Number of fibonacci Numbers in the series are 7

説明 − 0から8までのフィボナッチ数は0、1、1、2、3、5、8です。つまり、合計数は7です

以下のプログラムで使用されているアプローチは次のとおりです

• 開始番号と終了番号を入力して範囲を作成します

• fib1を0に、fib2を1に、fib3を1に宣言して初期化します

• 一時変数resを宣言し、0で初期化します

• fib1がend以下である間にループを開始します

• ループ内で、fib1が開始値以上であるかどうかを確認してから、解像度を1ずつ増やします

  。

• fib1をfib2に、fib2をfib3に、fib3をfib1+fib2に設定します

• 解像度を返す

• 結果を印刷する

例

#include <bits/stdc++.h>
using namespace std;
// function to count fibonacci numbers in range
// from start to last
int count_fibonacci(int start, int last){
   // First three Fibonacci Numbers
   int fib1 = 0, fib2 = 1, fib3 = 1;
   // res to count the number of fibonacci
   int res = 0;
   while (fib1 <= last){
      if (fib1 >= start){
         res++;
      }
      fib1 = fib2;
      fib2 = fib3;
      fib3 = fib1 + fib2;
   }
   return res;
}
// main function
int main(){
   int start = 6, last = 100;
   cout << "Number of fibonacci Numbers in the series are "
   << count_fibonacci(start, last);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Number of fibonacci Numbers in the series are 6