[C/C++ 演算法]- 費氏搜尋法

[C/C++ 演算法]- 費氏搜尋法

剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。

拷貝來源：
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/FibonacciSearch.htm

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <stdio.h> #include <stdlib.h> #include <time.h> #define INT_MIN -9999 void createFibonacci(int[], int); // 建立費氏數列 int findY(int[], int); // 找Y值 int fibonacciSearch(int[], int, int); // 費氏搜尋 int main(void) { int number[] = {1, 2, 3, 5, 6, 8, 9, 10, 11}; int length = sizeof(number) / sizeof(int); printf("數列："); int i; for(i = 0; i < length; i++) printf("%d ", number[i]); printf("\n輸入尋找對象："); int find; scanf("%d", &find); if((i = fibonacciSearch(number, length, find)) >= 0) printf("找到數字於索引 %d ", i); else printf("\n找不到指定數"); printf("\n"); return 0; } // 建立費氏數列 void createFibonacci(int Fib[], int length) { Fib[0] = 0; Fib[1] = 1; int i; for(i = 2; i < length; i++) Fib[i] = Fib[i-1] + Fib[i-2]; } // 找 y 值 int findY(int Fib[], int n) { int i = 0; while(Fib[i] <= n) i++; i--; return i; } // 費式搜尋 int fibonacciSearch(int number[], int length, int find) { int* Fib = malloc(length * sizeof(int)); int f; for(f = 0; f < length; f++) { Fib[f] = INT_MIN; } createFibonacci(Fib, length); int y = findY(Fib, length + 1); int m = length - Fib[y]; int x = y - 1; // printf("\nx = %d, m = %d, Fib[x] = %d\n\n", x, m, Fib[x]); int i = x; if(number[i] < find) i += m; int result = -1; while(Fib[x] > 0) { if(number[i] < find) i += Fib[--x]; else if(number[i] > find) i -= Fib[--x]; else { result = i; break; } } free(Fib); return result; }