এখানে আমাদের প্রদত্ত সূচকগুলির সাথে n ফিবোনাচি পদগুলির GCD খুঁজে বের করতে হবে। তাই প্রথমে আমাদের সর্বোচ্চ সূচক পেতে হবে, এবং ফিবোনাচি পদ তৈরি করতে হবে, কিছু ফিবোনাচি পদ এই রকম:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ….. সূচকটি শুরু হয় 0 থেকে। তাই 0 th এ উপাদান সূচক হল ০। যদি আমাদের সূচকগুলি {2, 3, 4, 5}-এ ফিবোনাচি পদগুলির gcd খুঁজে পেতে হয়, তাহলে পদগুলি হল {1, 2, 3, 4}, তাই এই সংখ্যাগুলির GCD হল 1।
এই কাজটি করার জন্য আমরা একটি আকর্ষণীয় পদ্ধতি ব্যবহার করব। ith এবং jth Fibonacci শব্দের 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
