2013年10月19日 星期六

[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;
}


 


沒有留言:

張貼留言