数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言程序设计
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究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
更新日期：2019年7月30日
443个浏览次数
广告