C ++程序在斐波那契数的帮助下使用分而治之搜索排序的序列
在此C++程序中，我们使用斐波那契数实现了分而治之的方法。使用斐波那契数，我们计算数据数组的中位数以搜索数据项。此方法的时间复杂度为O（log(n)）。
算法
Begin Assign the data to the array in a sorted manner. Take input of the element to be searched. Call FibonacciSearch() function. Calculate the mid value using ‘start+fib[index-2]’ expression. If the chosen item is equal to the value at mid index, print result and return to main. If it is lesser than the value at mid index, proceed with the left sub-array. If it is more than the value at mid index, proceed with the right sub-array. If the calculated mid value is equal to either start or end then the item is not found in the array. 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 item found at "<<mid<<" index.";
return;
} else if(item == a[start]) {
cout<<"\n item found at "<<start<<" index.";
return;
} else if(item == a[end]) {
cout<<"\n item found at "<<end<<" index.";
return;
} else if(mid == start || mid == end) {
cout<<"\nElement not found";
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<<"\nEnter the Element to be searched: ";
cin>>n;
FibonacciSearch(a, 0, 9, fib, i, n);
cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;
return 0;
}
}输出结果
Enter the Element to be searched: 26 item found at 6 index. Do you want to search more...enter choice(y/n)?y Enter the Element to be searched: 45 item not found Do you want to search more...enter choice(y/n)?n
热门推荐
7 带清的简短祝福语
10 少先队代表送祝福语简短
11 蛋糕祝老师祝福语简短
12 关于开车的祝福语简短
13 朋友花篮开业祝福语简短
14 简短大气的狗年祝福语
15 新年简短的祝福语爱情
16 婶婶生日贺词简短祝福语
17 离别简短的祝福语大全
18 开学新人祝福语简短英语