文档章节

斐波那契查找

laomd
 laomd
发布于 2017/02/24 13:40
字数 492
阅读 5
收藏 0
点赞 0
评论 0

楼主建议小伙伴们先学习折半查找 插值查找之后再来看这篇博客,因为斐波那契查找算法是从折半查找思想衍生的,如果能弄懂折半查找,斐波那契查找也就不在话下了。

       我们知道,不论是折半、插值查找,都涉及到对原有数据串的分割,折半插值是每次各一半,插值查找每次按比例分割,其实斐波那契查找也是同理。它的分割,是把一个长度为F[k](F是一个斐波那契数列)的数据串每次分割成左边的F[k-1]和右边的F[k-2],当然也可以倒过来。

        可能有些爱抬杠的小伙伴就说了,若果我的数组长度不是一个斐波那契数呢?很简单啊,一直push_back()直到长度等于第一个比原长度大的斐波那契数

        下面是代码,与折半查找类似:

//模仿STL查找的规则,在左闭右开[low,high)区间查找key
//如果找到,返回其位置(1,2,3,4,······),否则返回0
int fibsearch(const vector<int>& v, int low, int high, const int& key)
{
	int n = v.size();

    //生成一个斐波那契数列
	vector<int> F;
	F.push_back(0);
	F.push_back(1);
	int k = 1;
	while(F.back() < n) {
	    F.push_back(F[k - 1] + F[k - 2]);
	    k++;
	}

	vector<int> newvector = v;
    
    //多出来的长度用来存放v的最后一个元素
	int newsize = F.back(), i = n, e = v.back();
	while(i < newsize) {
	    newvector.push_back(e);
	    i++;
	}
    
    //此时newvector的长度为F[k],也就是F.back()
	while(low < high) {
	    int pos = low + F[k - 1];//可能有些版本写作int pos = low + F[k - 1] - 1,因为他们是[low,high]
	    if(v[pos] == key)
	    {
	    	if(pos >= n)//说明是在后来push_back()到newvector的元素中找到
	    		return n;
	    	else
	    		return pos + 1;
	    }
	    else
	    	if(v[pos] < key)//进入右端,长度为F[k-2],故k -= 2
	    	{
	    		low = pos + 1;
	    		k -= 2;
	    	}
	    	else//进入左端,长度为F[k-1],故 k -= 1;
	    	{
	    		high = pos;
	    		k--;
	    	}
	}
	return 0;
}

 

© 著作权归作者所有

共有 人打赏支持
laomd
粉丝 0
博文 31
码字总数 12000
作品 0
广州
斐波那契查找(黄金分割法查找)

什么是斐波那契查找 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n...

serenity ⋅ 2014/06/20 ⋅ 0

"二分查找(Binary Search)"与"斐波那契查找(Fibonacci Search)"

首先,我们来看一个笔者的拙作,一段二分查找代码 //返回值是key的下标,如果A中不存在key则返回-1template <class T>int BinSearch(T* A, const T &key, int lo, int hi){ int mid; while(l...

不高不富不帅的陈政_ ⋅ 2015/09/30 ⋅ 0

数据结构-堆

数据结构-堆 堆(英语:Heap),是一种拥有像树那样的特殊数据结构,或者理解为具有优先级的树。它的特点是父节点的值大于(或小于)两个子节点的值(分别称为大顶堆和小顶堆)。它常用于管理...

壶漏子 ⋅ 2015/06/24 ⋅ 0

斐波那契数

一、题目: 递归和非递归分别实现求第n个斐波那契数。 二、解题思路: 先了解下斐波拉契数列 (1 1 2 3 5 8 13 21 34 55···),第n个斐波那契数等于(n-1)个斐波那契数加上(n-2)个斐波那...

qq_38646470 ⋅ 2017/11/13 ⋅ 0

python实现斐波那契数列

斐波那契数列的发明者是意大利数学家昂纳多.斐波那契(Leonardo Fibonacci)。斐波那契数列又被称为黄金分割数列,或兔子数列。它指的是这样一个数列:0 1 1 2 3 5 8 13 21 34 ....在数学上,...

大陌 ⋅ 2017/07/09 ⋅ 0

Common Lisp循环和递归

循环: 1)do循环 语法:(do ((变量名 变量初值 (变量变化语句))) (结束条件 返回值) 循环主体) CL-USER> (defun draw-line (x) (do ((i 0 (1+ i))) ((>= i x) nil) ;;nil可以忽略 (format ...

努力喵 ⋅ 2015/12/27 ⋅ 2

python有趣的小编程

斐波那契数列的计算 描述 斐波那契数列(Fibonacci sequence),又称黄金分割数列,由意大利数学家Leonardo Fibonacci于1202年提出,并以其名字命名。该数列F(n)定义如下:F(0)=0, F(1)=1,...

巍峨大山 ⋅ 2017/01/04 ⋅ 5

重点汇总-python-gitbook-重要点学习-4-数据结构/编程题

数据结构 - 红黑树 红黑树与AVL的比较: AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多; 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低;...

时间之友 ⋅ 2017/12/21 ⋅ 0

由斐波纳契数列衍生出来的斐波纳契数列

斐波纳契(Fibonacci)数列: 0, 1, 1, 2, 3, 5, 8, 13, 21… 以0和1开始,并且后面的每个斐波纳契数是前两个斐波纳契数之和。 斐波纳契数列可以递归定义: Fibonacci(0)= 0 Fibonacci(1)...

刘学炜 ⋅ 2012/07/15 ⋅ 0

7种方式实现斐波那契数列

7种方式实现斐波那契数列 一:递归实现   在学校里学习递归的时候,老师就喜欢举斐波那契这个例子,看!多简洁清晰。其实这个例子是非常不适合作为递归举例的,   原因就是效率太慢,除了...

電泡泡 ⋅ 2012/10/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 16分钟前 ⋅ 0

linux实用操作命令

参考 http://blog.csdn.net/qwe6112071/article/details/50806734 ls [选项] [目录名 | 列出相关目录下的所有目录和文件 -a 列出包括.a开头的隐藏文件的所有文件-A 同-a,但不列出"."和"...

简心 ⋅ 32分钟前 ⋅ 0

preg_match处理中文符号 url编码方法

之前想过直接用符号来替换,但失败了,或者用其他方式,但有有些复杂,这个是一个新的思路,亲测可用 <?php$str='637朗逸·超速新风王(300)(白光)'; $str=iconv("UTF-8","GBK",$s...

大灰狼wow ⋅ 44分钟前 ⋅ 0

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 48分钟前 ⋅ 0

Cube、Cuboid 和 Cube Segment

1.Cube (或Data Cube),即数据立方体,是一种常用于数据分析与索引的技术;它可以对原始数据建立多维度索引。通过 Cube 对数据进行分析,可以大大加快数据的查询效率 2.Cuboid 在 Kylin 中特...

无精疯 ⋅ 今天 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 今天 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 今天 ⋅ 0

云计算的选择悖论如何对待?

人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云计算为...

linux-tao ⋅ 今天 ⋅ 0

Redis 注册为 Windows 服务

Redis 注册为 Windows 服务 redis 注册为 windows 服务相关命令 注册服务 redis-server.exe –service-install redis.windows.conf 删除服务 redis-server –service-uninstall 启动服务 re......

Os_yxguang ⋅ 今天 ⋅ 0

世界那么大,语言那么多,为什么选择Micropython,它的优势在哪?

最近国内MicroPython风靡程序界,是什么原因导致它这么火呢?是因为他功能强大,遵循Mit协议开源么? 错!因为使用它真的是太舒服了!!! Micropython的由来,这得益于Damien George这位伟大...

bodasisiter ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部