C++で指定されたインデックスを持つNフィボナッチ数のGCDを検索します

ここでは、指定されたインデックスを持つn個のフィボナッチ項のGCDを見つける必要があります。したがって、最初に最大インデックスを取得し、フィボナッチ項を生成する必要があります。いくつかのフィボナッチ項は次のようになります：0、1、1、2、3、5、8、13、21、34、…..インデックスは開始です0から。したがって、0 ^th の要素 インデックスは0です。インデックス{2、3、4、5}でフィボナッチ項のgcdを見つける必要がある場合、項は{1、2、3、4}であるため、これらの数値のGCDは1です。

このタスクを実行するために、1つの興味深いアプローチを使用します。 GCD（Fibo（i）、Fibo（j））のようなi番目とj番目のフィボナッチ項のGCDを取得するには、Fibo（GCD（i、j））

例

#include <iostream>
#include <algorithm>
using namespace std;
int getFiboTerm(int n){
   int fibo[n + 2];
   fibo[0] = 0; fibo[1] = 1;
   for(int i = 2; i<= n; i++){
      fibo[i] = fibo[i - 1] + fibo[i - 2];
   }
   return fibo[n];
}
int getNFiboGCD(int arr[], int n){
   int gcd = 0;
   for(int i = 0; i < n; i++){
      gcd = __gcd(gcd, arr[i]);
   }
   return getFiboTerm(gcd);
}
int main() {
   int indices[] = {3, 6, 9};
   int n = sizeof(indices)/sizeof(indices[0]);
   cout << "GCD of fibo terms using indices: " <<
   getNFiboGCD(indices, n);
}

出力

GCD of fibo terms using indices: 2