查找算法——斐波那契查找-白红宇

查找算法——斐波那契查找

阅读量：5243 次

发布时间：2019-06-14

本文共 3383 字，大约阅读时间需要 11 分钟。

一、C 程序实现

/********************************************************************************************Description 斐波那契查找算法*Author liaoxiongxiong*Version 1.0*Time 2018-06-28*******************************************************************************************/#include 
     
      const int max_size=20;//斐波那契数组的长度//生成斐波那契数列void Fibonacci(int *f){    int i;    f[0] = 1;    f[1] = 1;    for(int i=2; i

//因为需要执行hight=mid-1、low=mid+1这样的操作所以实际数列为F[k]-1int FibonacciSearch(int a[], int value, int n){ int i; int low = 0; int high = n-1; int mid = 0; int k = 0; int F[max_size]; Fibonacci(F);//构造一个斐波那契数组F while(n > F[k] - 1)//找出数组长度n在斐波数列（减1）中的位置，将决定如何拆分 k++; //此时F[k]-1>=n int tmp[F[k]-1]; //创建一个F[k]-1大小的临时数组，因为原数组a[]太小 for(i=0; i<=high; i++)//将元素复制进临时数组tmp中 tmp[i] = a[i]; for(i=n; i

n 则把数组补全，直到长度为F[k]-1 tmp[i] = a[high]; while(low <= high) { mid = low + F[k-1] -1;//根据斐波那契数列进行黄金分割 if(tmp[mid] > value) { high = mid-1; k = k-1; } else if(tmp[mid] < value) { low = mid+1; k = k-2; } else { if(mid <= high)//如果为真则找到相应的位置 return mid; else return -1; } } return -1;}//测试用例int main(){ int a[]={0,1,2,3,4,5,6,7,8,9}; int len = sizeof(a)/sizeof(a[0]); int x = 2; // 需要查找的元素 int i = FibonacciSearch(a, x, len-1); if(i!=-1) printf("元素 %d 在第 %d 个位置\n",x,i+1); else printf("没有找到元素:%d\n",x); return 0;}

运行结果：

二、Java 程序实现

import java.util.Arrays;/** * @description: 斐波那契查找算法 * @author：liaoxiongxiong * @version : 1.0 * @date: 2018-06-29 */public class FibonacciSearch {	private static final int max_size = 20;//斐波那契数列长度		public static void fibonacci(int[] F)	{		int N = F.length;		F[0] = 1;		F[1] = 1;		for(int i=2; i
     
       F[k]-1)			k++;				int[] tmp = Arrays.copyOf(a, F[k] - 1);// 构造一个长度为F[k] - 1的新数列				for(int i=N; i
      
        value)			{				high = mid-1;				k = k-1;			}			else if(tmp[mid] < value)			{				low = mid+1;				k = k-2;			}			else			{				if(low<=high)					return mid;				else					return -1;			}		}		return -1;			}			//测试用例	public static void main(String[] args)	{	    int[] a={0,1,2,3,4,5,6,7,8,9};	    	    int x=2;   // 需要查找的元素	    int i = fibonacciSearch(a, x);	    if(i!=-1)	        System.out.printf("元素 %d 在第 %d 个位置\n",x,i+1);	    else	    	System.out.printf("没有找到元素:%d\n",x);	    	}	}

运行结果：

三、Python 程序实现

# -*- coding: utf-8 -*-"""Description: 斐波那契查找算法Author: shujuxiongVersion: 1.0Date: 2018-06-29"""import copydef fibonacciSearch(lists, value):        #生成斐波那契数列    fib = [1, 1]    for i in range(1, 20):        fib.append(fib[-1] + fib[-2])        #确定数组长度在斐波那契数列中的位置    k = 0    n = len(lists)        while(n > fib[k]-1):        k = k+1        tmp = copy.deepcopy(lists) #临时数组        #将待查找数组填充到指定的长度    for i in range(n,fib[k]):        tmp.append(lists[-1])        low, high = 0, n-1        while(low <= high):        #获取黄金分割比例位置下标        mid = low + fib[k-1]-1                if(tmp[mid] > value):            high = mid-1            k = k-1        elif(tmp[mid] < value):            low = mid+1            k = k-2        else:            if low <= high:                return mid            else:                return -1    return -1##测序用例def main():    mylist = [0,1,2,3,4,5,6,7,8,9]        x = 2 #需要查找的元素    i = fibonacciSearch(mylist, x)    if i != -1:        print("元素 %d 在第 %d 个位置\n" % (x,i+1))    else:        print("没有找到元素:%d\n" % x)     if __name__=='__main__':    main()

运行结果：

转载于:https://www.cnblogs.com/shujuxiong/p/9240493.html

你可能感兴趣的文章