C++에서 주어진 인덱스를 사용하여 N 피보나치 수의 GCD 찾기

여기서 우리는 주어진 인덱스로 n개의 피보나치 항의 GCD를 찾아야 합니다. 따라서 처음에는 최대 색인을 가져와서 피보나치 항을 생성해야 합니다. 일부 피보나치 항은 다음과 같습니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …. 색인이 시작됩니다. 0부터. 따라서 0 ^번째 에 있는 요소 인덱스는 0입니다. 인덱스 {2, 3, 4, 5}에서 피보나치 항의 gcd를 찾아야 하는 경우 항은 {1, 2, 3, 4}이므로 이 숫자의 GCD는 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