C++ में दिए गए सूचकांकों के साथ N फाइबोनैचि संख्याओं की GCD ज्ञात कीजिए

यहाँ हमें दिए गए सूचकांकों के साथ n फाइबोनैचि पदों की GCD ज्ञात करनी है। तो सबसे पहले हमें अधिकतम सूचकांक प्राप्त करना होगा, और फाइबोनैचि शब्द उत्पन्न करना होगा, कुछ फाइबोनैचि शब्द इस प्रकार हैं:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ….. सूचकांक शुरू होता है 0 से। तो तत्व 0 ^th . पर सूचकांक 0 है। यदि हमें सूचकांक {2, 3, 4, 5} पर फाइबोनैचि शब्दों का जीसीडी खोजना है, तो शब्द {1, 2, 3, 4} हैं, इसलिए इन संख्याओं की जीसीडी 1 है।

हम इस कार्य को करने के लिए एक दिलचस्प दृष्टिकोण का उपयोग करेंगे। GCD(Fibo(i), Fibo(j)) जैसे ith और jth फाइबोनैचि शब्द का 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