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