Tìm GCD của N Số Fibonacci với các Chỉ số đã cho trong C ++

Ở đây chúng ta phải tìm GCD của n số hạng Fibonacci với các chỉ số đã cho. Vì vậy, lúc đầu chúng ta phải lấy chỉ mục tối đa và tạo các số hạng Fibonacci, một số số hạng Fibonacci như sau:0, 1, 1, 2, 3, 5, 8, 13, 21, 34,… .. Chỉ số được bắt đầu từ 0. Vì vậy, phần tử ở 0 ^th chỉ số là 0. Nếu chúng ta phải tìm gcd của các số hạng Fibonacci tại chỉ số {2, 3, 4, 5}, thì các số hạng là {1, 2, 3, 4}, vì vậy GCD của những số này là 1.

Chúng tôi sẽ sử dụng một cách tiếp cận thú vị để thực hiện nhiệm vụ này. Để lấy GCD của thuật ngữ Fibonacci thứ i và thứ j như GCD (Fibo (i), Fibo (j)), chúng ta có thể biểu diễn nó như Fibo (GCD (i, j))

Ví dụ

#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);
}

Đầu ra

GCD of fibo terms using indices: 2