精华内容
下载资源
问答
  • c++斐波那契数列查找数组方法实现
    2020-06-30 23:10:42

    查找数组是为了在多次计算斐波那契数列时减少重复的计算。扩展到其他的例子,需要递推公式计算结果的,可以考虑通过多开数组浪费空间的方法节省时间。

    #include<iostream>
    using namespace std;
    
    int main() {
    	int i,j,n,maxn,a[100];
    	a[1]=a[2]=1;
    	maxn=2;
    	while(cin>>n){
    		if(n>maxn){
    			for(i=maxn;i<n;i++)
    			a[i+1]=a[i]+a[i-1];
    		}
    		cout<<a[n]<<endl;
    	}
    	return 0;
    
    }
    
    更多相关内容
  • 斐波那契数列查找

    2016-03-19 14:10:59
    斐波那契数列查找
  • 斐波那契数列查找算法 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位 数字的近似值是 0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为...

    斐波那契数列查找算法

    1. 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位 数字的近似值是 0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神
      奇的数字,会带来意向不大的效果。
    2. 斐波那契数列 {1,1,2,3,5,8,13,21,34,55} 发现斐波那契数列的两个相邻数 的比例,无限接近 黄金分割值 0.618
      8.5.2斐波那契(黄金分割法)原理: 斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid 不再是中间或插值得到,而是位 于黄金分割点附近,即 mid=low+F(k-1)-1(F 代表斐波那契数列),如下图所示
      在这里插入图片描述
      对 F(k-1)-1 的理解: 1) 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质,可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 。该式说明: 只要顺序表的长度为 F[k]-1,则可以将该表分成长度为 F[k-1]-1 和 F[k-2]-1 的两段,即如上图所示。从而中间位置为 mid=low+F(k-1)-1
    3. 类似的,每一子段也可以用相同的方式分割 3) 但顺序表长度 n 不一定刚好等于 F[k]-1,所以需要将原来的顺序表长度 n 增加至 F[k]-1。这里的 k 值只要能使 得 F[k]-1 恰好大于或等于 n 即可,由以下代码得到,顺序表长度增加后,新增的位置(从 n+1 到 F[k]-1 位置), 都赋为 n 位置的值即可。 while(n>fib(k)-1) k++;

    具体实现如下:

    public class FibonacciSearch {
        //数组的长度
        public static int  maxSize=20;
    
    
        //得到一个斐波那契数列,非递归实现
        public static int [] fib()
        {
            int [] f=new int [maxSize];
    
            f[0]=1;
            f[1]=1;
            for (int i = 2; i <maxSize ; i++) {
    
                f[i]=f[i-1]+f[i-2];
            }
    
            return f;
        }
        //斐波那契数列查找算法,非递归实现
        public static int fibSearch(int [] arr,int key) {
            int low = 0;
    
            int high = arr.length - 1;
    
            int k = 0;  //斐波那契数列的分割值下标
    
            int mid = 0; //记录mid的值
    
            int f[] = fib(); //获取到斐波那契数列
            //获取斐波那契数列分割数组的下标
            while (high > f[k] - 1) {
                k++;
    
                //因为f[k]值可能大于a的长度,因此我们需要使用Arrays,指向temp[]
                //不足的部分会使用0填充
            }
    
            int[] temp = Arrays.copyOf(arr, f[k]);
    
            for (int i = high + 1; i < temp.length; i++) {
                temp[i] = arr[high];
            }
            //使用while来循环处理,找到我们的数key
            while (low <= high) { //只要这个体条件满足,就可以找
                mid = low + f[k - 1] -1;
    
                if (key < temp[mid]) { //我们应该继续向数组前面查
                    high = mid - 1;
                    k--;
                } else if (key > temp[mid]) { //我们应该继续向数组后面查
                    low = mid + 1;
                    k -= 2;
                } else {//找到
                    if (mid <= high) {
                        return mid;
                    } else {
                        return high;
                    }
                }
            }
            return -1;
    
        }
    }
    
    

    在这里插入图片描述

    展开全文
  • 该脚本提供了不确定性的最终区间,其中单变量非线性/线性函数的最小值。 该函数在区间内应该是单峰的。 该脚本检查函数的单峰性。用户输入初始间隔和迭代次数。... 该算法基于斐波那契数列 1 1 2 3 5 8 13....
  • 2斐波那契数列 public static int fibonacci(int n){ if(n==1||n==2){ return 1; } return fibonacci(n-1)+fibonacci(n-2); } public static void main(String[] args) { int reslut=fibonacci(9); System.out...
  • //斐波那契数列查找算法 //前提:有序 //还有几处,理解的还很不到位。 //但根据记忆口诀,目前算法已经可以复写。但如果不理解,或许记忆不会深刻。 //目前惟手勤尔,真的可行 public static void main...
    public class FiboSearch3 {
    
    	//斐波那契数列查找算法
    	//前提:有序
    	//还有几处,理解的还很不到位。
    	//但根据记忆口诀,目前算法已经可以复写。但如果不理解,或许记忆不会深刻。
    	//目前惟手勤尔,真的可行
    	public static void main(String[] args) {
    		int [] arr = { 1,8,10,89,1000,1234 };
    		System.out.println( search(arr,1) );
    	}
    	//获得斐波那契数列
    	public static int[] fibo( int length ) {
    		int [] f = new int[length];
    		//头两个元素固定
    		f[0] =1;
    		f[1] =1;
    		for (int i = 2; i < f.length; i++) {
    			//元素规律
    			f[i] = f[i-1] + f[i-2];
    		}
    		return f;
    	}
    	
    	public static int search( int [] arr, int findVal ) {
    		int left = 0;
    		int right = arr.length-1;
    		int mid = 0;
    		int k = 0;
    		int [] f = fibo(10);
    		
    		//根据数列对照得到数组大小
    		while( right > f[k] -1 ) {
    			k++;
    		}
    		
    		//根据新大小生成新数组
    		int [] temp = Arrays.copyOf(arr, f[k]);
    		
    		//补充数据
    		for (int i = right+1; i < temp.length; i++) {
    			temp[i] = arr[right];
    		}
    		
    		//当左索引比右索引小时,说明数组未遍历完
    		//当判断条件为假时,说明数组遍历完毕
    		while( left <= right ) {
    			mid = left + f[k-1] -1;
    			//判断当前寻找的值是否比中间值小
    			if( findVal < temp[mid] ) {
    				right = mid - 1;
    				k--;
    			}else if( findVal > temp[mid] ) {
    				left = mid+1;
    				k-=2;
    			}else {
    				if(mid <= right) {
    					return mid;
    				}else {
    					return right;
    				}
    			}
    		}
    		//未找到搜索值,返回-1标记失败。
    		return -1;
    	}
    
    }
    
    展开全文
  • 该程序在斐波那契数列查找第 n 项。 例如,第 6 项是 8。程序还查找序列中的第 n 项。 例如,8 是序列中的第 6 项。
  • 斐波那契数列   在数学中,斐波那契数列的定义是: fn={n(n=0,1)fn−1+fn−2    (n⩾2      )f_n=\left\{\begin{array}{lc}n&(n=0,1)\\f_{n-1}+f_{n-2}\;\;&(n\geqslant2\;\;\;)\end{array}\...

    斐波那契数列

      在数学中,斐波那契数列的定义是:
    f n = { n ( n = 0 , 1 ) f n − 1 + f n − 2      ( n ⩾ 2        ) f_n=\left\{\begin{array}{lc}n&(n=0,1)\\f_{n-1}+f_{n-2}\;\;&(n\geqslant2\;\;\;)\end{array}\right. fn={nfn1+fn2(n=0,1)(n2)
      很明显,这是一个递归定义,很多数据结构书中也拿斐波那契数列来讲解递归的过程。根据这个定义可以得到一个斐波那契数列:

    n012345678……
    数列值01123581321……

      先讨论一下这个数列值如何用程序来产生,这是个递归定义,那肯定是可以用递归函数来生成这个数列了。

    unsigned __int64 Fib(int n)
    {
    	if (n <= 1)
    		return n;
    	else
    		return Fib(n - 1) + Fib(n - 2);
    }
    

      这几行代码非常简单,但是在实际过程中不可这么用。为什么?用这个函数生成长度为100的数列,跑一跑就知道了.

    void main(void)
    {
    	printf("斐波那契数列:\r\n");
    	for (int i = 0; i < 100; i++)
    	{
    		printf("%3d:%I64u \r\n", i,Fib(i));
    	}
    }
    

      这总共不超过20行的代码,用一台六年前的笔记本整整跑了一个半小时,只计算到数列的第五十一个值 ,虽然笔记本性能一般,但是这几行代码异常耗时是有内层机理的。用这个方法计算一个斐波那契数列,越到后面越耗时,时间的增加就跟数列值的增加一样,后一个值的计算用时是前两个值计算用时的总和。以数列第3、4、5个值为例:
    在这里插入图片描述

      要计算 F i b ( 5 ) Fib(5) Fib(5) 就要计算 F i b ( 4 ) Fib(4) Fib(4) F i b ( 3 ) Fib(3) Fib(3),同样,要计算 F i b ( 4 ) Fib(4) Fib(4) 就要计算 F i b ( 3 ) Fib(3) Fib(3) F i b ( 2 ) Fib(2) Fib(2),一直到叶子节点,即 F i b ( 1 ) Fib(1) Fib(1) F i b ( 0 ) Fib(0) Fib(0) 才一层层返回,也就是说 F i b ( 5 ) Fib(5) Fib(5) 的计算重复了 F i b ( 4 ) Fib(4) Fib(4) F i b ( 3 ) Fib(3) Fib(3) 的计算过程,做了大量的重复计算过程,而且这个增长接近2的指数级。
    在这里插入图片描述

      像斐波那契数列这样的递归计算不适用于实际,那就要想办法将它转化成其他形式,例如迭代运算。

    数列值01123581321……
    第一次 i i i p p p q q q
    第二次 i i i p p p q q q
    第三次 i i i p p p q q q
    第四次 i i i p p p q q q
    第五次 i i i p p p q q q
    第六次 i i i p p p q q q

      通过 i i i p p p q = i + p q=i+p q=i+p往后移就可以得到数列中任意想要的值。写成代码:

    unsigned __int64 Fib(int n)
    {
    	unsigned __int64 i = 0, p = 1, q = 1;
    	if (n <= 1) return n;
    	else if (n == 2) return 1;
    	else
    	{
    		for (int j = 2; j < n; j++)
    		{
    			i = p;
    			p = q;
    			q = i + p;
    		}
    		return q;
    	}
    }
    

    在这里插入图片描述

      程序跑完才发现,64位无符号整型仍然不够,还是产生了溢出。
      去年研究生考试结束后在南京面试,笔试里就有一道斐波那契数列的程序题,一开始写的程序是动态申请一块内存作为数组,前两个值相加的和放到后一个单元里面,然后一直迭代下去,产生一组斐波那契数列。面试官就说如果数列很长呢,还能用动态申请的方式去生成这个数列吗?于是就写了迭代版本的Fib函数,面试官看了一会,好像还是没有get到他的要求。出了公司门一个瞬间有个念头:难道他想要我写出递归版本?他招的是嵌入式软件工程师啊。。亦或者是斐波那契数列的生成有更优的方法,但是本人愚钝。。。

    斐波那契查找

      斐波那契查找又是怎么回事呢?
    在这里插入图片描述
      从这颗斐波那契树中可以大致看出来,左子树和右子树的结点数虽然不等,但是左子树的结点数永远不会超过右子树结点数的两倍,可以大致的看成是相对均匀的两部分,如果将数据以这个树形建成一颗搜索树,那么每颗子树根节点的序号就可以看成二分搜索的 m i d mid mid
      为什么要这么做?在对半查找中 m i d = ( l o w + h i g h ) / 2 mid=(low+high)/2 mid=(low+high)/2,这里 m i d mid mid的计算运用了除法,有些处理器中并没有浮点运算单元,像51单片机进行乘除运算就比较费资源。斐波那契查找正是极力想要避免查找过程中出现乘除运算,查找过程中 m i d mid mid的计算可以直接通过斐波那契数列得到,当表长为12( f 7 − 1 f_7-1 f71)时, m i d = 8 mid=8 mid=8,即 m i d mid mid值为数列的前一个值。
      既然斐波那契数列值是用来作为 m i d mid mid值,那么数列值应该是不重复的,否则会发生重复比较甚至出错,对于下列数列值中,1有重复,那么应该去掉一个,但是只去掉一个1,会导致整个数列不符合斐波那契公式,无法计算,所以去掉0和一个1,但是斐波那契的阶数保持不变。

    阶数2345678……
    数列值123581321……

      为了直观,建立一颗 1 1 1~ 12 12 12的斐波那契树
    在这里插入图片描述

      1,2,3,5,8这条路径上确实满足斐波那契数列,可每颗子树的右子树并不满足。但是是有规律的,每颗右子树结点的值减去双亲结点的值却是满足斐波那契数列的。
      为了简单,假设表长为12( f 7 − 1 f_7-1 f71),为什么表长需要定义为 f m − 1 f_m-1 fm1呢,这里跟二叉判定树是一样的,为了树形完整,便于运算分析。可以写出查找函数:

    int search(s_list lst, int k, s_eletype* x)
    {
    	int i = 1, p = 1, q = 2, t, n = lst.size;
    	while (q <= n)                       //见注释1
    	{                                    
    		i = p;
    		p = q;
    		q = i + p;
    	}
    	i = p;                               //见注释2
    	p = q - i;
    	q = i - p;
    
    	for (;;)
    	{
    		if (k == lst.element[i-1].key)
    		{
    			*x = lst.element[i-1];
    			return true;
    		}
    		else
    		{
    			if (k < lst.element[i-1].key)
    			{
    				if (q == 0) return false;
    				else
    				{
    					i = i - q;
    					t = p;
    					p = q;
    					q = t - q;
    				}
    			}
    			else
    			{
    				if (p == 1)return false;
    				else
    				{
    					i = i + q;
    					p = p - q;
    					q = q - p;
    				}
    			}
    		}
    	}
    }
    

    注释1:计算斐波那契数列的最后三个数值: i = f m − 2 i=f_{m-2} i=fm2 p = f m − 1 p=f_{m-1} p=fm1 q = f m q=f_m q=fm
    注释2:颠倒 i , p , q i,p,q i,p,q,变成 i = f m − 1 i=f_{m-1} i=fm1 p = f m − 2 p=f_{m-2} p=fm2 q = f m − 3 q=f_{m-3} q=fm3
    p , q p,q p,q的大小永远往下减,代表的是以 i i i为根节点的子树所在阶数的斐波那契数列最高两位数列值。

      因为斐波那契树不是一颗完全二叉树,所以将数据构建成的斐波那契数的高度会高于[lbn]+1,所以在最坏的情况下,斐波那契查找的时间性能不如对半查找;但是斐波那契的查找过程中没有乘除运算,所以在没有浮点运算单元的处理器中理论上平均性能会优于对半查找。
      之所以说是理论上要比对半查找性能好,那是因为我们可以将对半查找的乘除运算转换为移位运算呀,乘2运算转换为左移一位,除2运算转换为右移一位,那平均性能妥妥的比斐波那契查找好。

    本篇完 😉

    展开全文
  • import java.util.Arrays; /** * @author haoxiansheng * @data 2020/5/9 22:40 ...public class FibonacciSearch { public static int maxSize = 20; public static void main(String[] args) { int[].
  • 斐波那契(黄金分割法)查找算法

    千次阅读 2021-01-15 10:28:48
    文章目录一、斐波那契查找算法概述1.1 什么是斐波那契查找算法1.2 什么是斐波那契数列1.3 斐波那契查找算法的思想二、斐波那契查找的基本步骤三、斐波那契查找的代码实现 一、斐波那契查找算法概述 1.1 什么是...
  • 2014-01-16 回答斐波那契数列的通项公式: f(n)=0 当n=0, f(n)=1 当n=1,2 f(n)=f(n-1)+f(n-2) 当n>2 又叫“比内公式”,是用无理数表示有理数的一个范例 f(n)=1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n} 似乎你要...
  • (Java)利用递归实现斐波那契数列查找.
  • [C语言]用递归算法编写一个程序求Fibonacci数列的第n项值#includeunsignedintFibonacci(intn);intmain(void){inti;for(i=1;ivb用递归法求Fibonacci数列的第20、200项dimf()asdoublen=inputbox("in","NO.")redimf(n)...
  • 斐波那契数列的时间复杂度

    千次阅读 2021-07-07 21:49:07
    求解斐波那契数列 F(n)={1,n=0,1F(n−1)+F(n−2),n>1F(n) =\left\{ \begin{matrix} 1, \quad n=0,1 \\ F(n-1)+F(n-2),n>1 \end{matrix} \right.F(n)={1,n=0,1F(n−1)+F(n−2),n>1​ 有两种常用的算法:...
  • 4.斐波那契查找(黄金分割数列) 一、斐波那契数列介绍 被我们称为"斐波拉契"的人,真实姓名叫列昂纳多,来自比萨,这个数列出自他的书《算盘宝典》(“Liber Abaci”),这本书奠定西方世界的数学基础,其中的算法...
  • Python解决斐波那契数列问题

    千次阅读 2021-12-02 17:18:11
    斐波那契数列问题题目思路1代码1思路2代码2 题目 大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。 根据斐波那契数列的定义可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=...
  • 在定义一个函数时候,只需知道其终止的条件,无需知道其执行方法,仅需在函数中调用函数本身即可,这种魔性的写法就叫做递归函数,江湖上有一句:人能...#斐波那契#0, 1, 1, 2, 3, 5, 8, 13,def fibonacci(n):if ...
  • int Fb1(int i) { int x1, x2, an, n; x1 = 0; x2 = 1; an = 1; n = 1; while (n < i) { n++; an = x1 + x2; x1 = x2; x2 = an; } return an; } 首先是循环法。... if((n == 1)||(n =.
  • 斐波那契数列是一个众所周知的且经过研究的数字序列,经常在学校和休闲数学中使用,因为它很容易被那些受过有限的专业数学教育的人理解。序列的定义如下:第一项是零,第二项是一,任何其他项都是序列前两项的和。这...
  • 斐波那契数列解法

    2019-01-28 17:08:28
    斐波那契数列解法 1、概念 在数学上,费波那契数列是以递归的方法来定义: F0=0 F1=1 Fn=Fn-1+Fn-2(n≧2) 用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出。首几个...
  • 问题:斐波那契数列(意大利语: Successione di Fibonacci),又称黄金分割数列、费波那西数列、费波拿契数、费氏数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归...
  • 斐波那契数列: f(n)=f(n-1)+f(n-2); n>=2 f(0)=0; f(1)=1; 即有名的兔子繁衍问题。 现在我们去面试,面试官要求我们写出求解斐波那契数列指定项的函数,可能乍一听很简单,我们在大一的c语言课上就学过递归求解...
  • java斐波那契查找

    2021-09-15 22:56:09
    斐波那契查找法类似与二分查找法,但是不同的是,是以黄金分割点来进行查找的,而斐波那契数列的相邻两项之比正好与黄金分割相似,所以可以利用斐波那契数列的值来计算。 在这个算法中,必须使用顺序数组,而且在...
  • python 递归\for循环_斐波那契数列

    千次阅读 2020-11-29 12:56:57
    b): c = a + b print(c) if c > 500: return return myFibo(b, c) myFibo(0, 1) a = 0 b = 1 for i in range(1000): c = a + b print(c) a = b b = c if c > 500: break Python递归 — — 二分查找斐波那契数列、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,830
精华内容 7,132
关键字:

斐波那契数列查找