do{goodgoodstudy();daydayup();}while(!died)
分类： C/C++
2012-07-04 16:06:36
| 01 | #include |
| 02 | void fibonacci(int *f) |
| 03 | { |
| 04 | f[0] = 1; |
| 05 | f[1] = 1; |
| 06 | for(int i = 2;i < MAXSIZE;++i) |
| 07 | f[i] = f[i - 2] + f[i - 1]; |
| 08 | } |
| 09 | int fibonacci_search(int *a,int key,int n) |
| 10 | { |
| 11 | int low = 0,high = n - 1; |
| 12 | int mid = 0; |
| 13 | int k = 0; |
| 14 | int F[MAXSIZE]; |
| 15 | fibonacci(F); |
| 16 | while(n > F[k] - 1) //计算出n在斐波那契中的数列 |
| 17 | ++k; |
| 18 | for(int i = n;i < F[k] - 1;++i) //把数组补全 |
| 19 | a[i] = a[high]; |
| 20 | while(low <= high) |
| 21 | { |
| 22 | mid = low + F[k-1] - 1; //根据斐波那契数列进行黄金分割 |
| 23 | if(a[mid] > key) |
| 24 | { |
| 25 | high = mid - 1; |
| 26 | k = k - 1; |
| 27 | } |
| 28 | else if(a[mid] < key) |
| 29 | { |
| 30 | low = mid + 1; |
| 31 | k = k - 2; |
| 32 | } |
| 33 | else{ |
| 34 | if(mid <= high) //如果为真则找到相应的位置 |
| 35 | return mid; |
| 36 | else |
| 37 | return -1; |
| 38 | } |
| 39 | } |
| 40 | return -1; |
| 41 | } |
| 42 | int main() |
| 43 | { |
| 44 |
| 45 | int a[MAXSIZE] = {5,15,19,20,25,31,38,41,45,49,52,55,57}; |
| 46 | int k; |
| 47 | printf("请输入要查找的数字:\n"); |
| 48 | scanf("%d",&k); |
| 49 | int pos = fibonacci_search(a,k,13); |
| 50 | if(pos != -1) |
| 51 | printf("在数组的第%d个位置找到元素:%d\n",pos + 1,k); |
| 52 | else |
| 53 | printf("未在数组中找到元素:%d\n",k); |
| 54 | return 0; |
| 55 | } |
