C++でN番目のフィボナッチ数の最後の2桁を検索するプログラム

この問題では、番号Nが与えられます。私たちのタスクは、C++でN番目のフィボナッチ数の最後の2桁を見つけるプログラムを作成することです。

問題の説明

N番目のフィボナッチ数の最後の2桁（つまり、2つのLSB）を見つける必要があります。問題を理解するために例を見てみましょう

入力 ：N =120

出力 ：81

ソリューションアプローチ

簡単な解決策は、直接フィボナッチ式を使用してN番目の項を見つけることです。ただし、Nが大きい場合、この方法は実行できません。したがって、これを克服するために、最後の2桁が300項後に繰り返されるフィボナッチ数列のプロパティを使用します。つまり第75項の最後の2桁は、第975項のそれと同じです。

これは、300まで作業すると、考えられるすべての組み合わせが得られ、使用する用語を見つけるために、300の数値のmodが見つかることを意味します。

例

#include <iostream>
using namespace std;
long int fibo(int N){
   long int a=0,b=1,c;
   for(int i=2; i<= N;i++) {
      c=a+b; a=b; b=c;
   }
   return c;
}
int findLastTwoDigitNterm(int N) {
   N = N % 300;
   return ( fibo(N)%100);
}
int main() {
   int N = 683;
   cout<<"The last two digits of "<<N<<"th Fibonacci term are "<<findLastTwoDigitNterm(N);
   return 0;
}

出力

The last two digits of 683th Fibonacci term are 97