এই C++ প্রোগ্রামে আমরা ফিবোনাচ্চি সংখ্যা ব্যবহার করে ডিভাইড এন্ড কঙ্কর পদ্ধতি বাস্তবায়ন করি। ফিবোনাচ্চি সংখ্যা ব্যবহার করে ডাটা অ্যারের মাঝপথ (mid) গণনা করে ডাটা আইটেম সার্চ করি। এই পদ্ধতির সময় জটিলতা O(log n)।
অ্যালগরিদম
শুরু ডাটা অ্যারেতে সর্টেডভাবে বরাদ্দ করুন। সার্চ করার উপাদান ইনপুট নিন। FibonacciSearch() ফাংশন কল করুন। 'start+fib[index-2]' এক্সপ্রেশন ব্যবহার করে mid মান গণনা করুন। যদি বাছাই করা আইটেম mid ইনডেক্সের মানের সমান হয়, তবে ফলাফল প্রিন্ট করে main-এ ফেরত যান। যদি এটি mid ইনডেক্সের মানের চেয়ে কম হয়, তবে বাম সাব-অ্যারে নিয়ে এগিয়ে যান। যদি এটি mid ইনডেক্সের মানের চেয়ে বেশি হয়, তবে ডান সাব-অ্যারে নিয়ে এগিয়ে যান। যদি গণনা করা mid মান start বা end-এর সমান হয়, তবে আইটেমটি অ্যারেতে নেই। শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
void FibonacciSearch(int *a, int start, int end, int *fib, int index, int item) {
int i, mid;
mid = start + fib[index - 2];
if (item == a[mid]) {
cout << "\n আইটেম " << mid << " ইনডেক্সে পাওয়া গেছে।";
return;
} else if (item == a[start]) {
cout << "\n আইটেম " << start << " ইনডেক্সে পাওয়া গেছে।";
return;
} else if (item == a[end]) {
cout << "\n আইটেম " << end << " ইনডেক্সে পাওয়া গেছে।";
return;
} else if (mid == start || mid == end) {
cout << "\nএলিমেন্ট পাওয়া যায়নি";
return;
} else if (item > a[mid])
FibonacciSearch(a, mid, end, fib, index - 1, item);
else
FibonacciSearch(a, start, mid, fib, index - 2, item);
}
main() {
int n, i, fib[20], a[10] = {3, 7, 55, 86, 7, 15, 26, 30, 46, 95};
char ch;
fib[0] = 0;
fib[1] = 1;
i = 1;
while (fib[i] < 10) {
i++;
fib[i] = fib[i-1] + fib[i-2];
}
up:
cout << "\nসার্চ করার উপাদান লিখুন: ";
cin >> n;
FibonacciSearch(a, 0, 9, fib, i, n);
cout << "\n\n\tআরও সার্চ করতে চান...চয়েস লিখুন (y/n)? ";
cin >> ch;
if (ch == 'y' || ch == 'Y')
goto up;
return 0;
}
আউটপুট
সার্চ করার উপাদান লিখুন: 26 আইটেম 6 ইনডেক্সে পাওয়া গেছে। আরও সার্চ করতে চান...চয়েস লিখুন (y/n)? y সার্চ করার উপাদান লিখুন: 45 আইটেম পাওয়া যায়নি আরও সার্চ করতে চান...চয়েস লিখুন (y/n)? n
