এখানে আমাদের দেয়া ইন্ডেক্সের Nটি ফিবোনাচ্চি টার্মের GCD বের করতে হবে। তাই প্রথমে সর্বোচ্চ ইন্ডেক্স বের করে ফিবোনাচ্চি টার্ম জেনারেট করতে হবে। কিছু ফিবোনাচ্চি টার্ম: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … ইন্ডেক্স ০ থেকে শুরু হয়। তাই ০তম ইন্ডেক্সের উপাদান ০। যদি ইন্ডেক্স {2, 3, 4, 5}-এর ফিবোনাচ্চি টার্মের gcd বের করতে হয়, তবে টার্মগুলো {1, 2, 3, 4}, তাই GCD = ১।
এই কাজে আমরা একটি দিলচস্প পদ্ধতি ব্যবহার করব। 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
