Fibonacci(斐波那契)序列的递归算法大家都已经很熟悉了:
//Fibonacci序列第n项的值
//递归算法
unsigned intFib1(unsigned intn)
{
if(n==1||n==2)
return1;
else
returnFib(n-1)+Fib(n-2);
}
而且递归算法的缺点是效率太低,下面是非递归算法:
//Fibonacci序列第n项的值
//非递归算法
unsignedintFib2(unsignedintn)
{
unsignedintnRet, nP, nPp;
nRet = nP = nPp = 1;
if((n==1)||(n==2))
returnnRet;
for(unsignedinti=3;i<=n;i++)
{
nRet=nP+nPp;
nPp=nP;
nP=nRet;
}
returnnRet;
}
Fibonacci(斐波那契)序列:
Fib(n) = Fib(n - 1) + Fib(n - 2), n>1, Fib(1) = Fib(2) = 1
即:序列的第一和第二项是1,从第三项开始,后一项是前两项的和。
序列的前8项是:
1, 1, 2, 3, 5, 8, 13, 21
分享到:
相关推荐
关于斐波那契序列的3个算法时间复杂度比较:递归ds1_17 O(k^m), ds1_17_1 O(m*k),ds1_17_2 O(m).
斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*) c语言 循环队列的算法
例如,考虑斐波那契数列:0,1,1,2,3,5,8,13,…第一个和第二个Fibonacci数被定义为0和1,分别。第n个Fibonacci数定义为前两个Fibonacci数的总和。因此,您可以使用递归函数计算第n个斐波那契数 同源性是一个...
6.中序遍历的非递归算法 7.先序遍历的非递归算法 8.后序遍历的非递归算法 9.层次的非递归算法 10.求二叉树的深度(后序遍历) 11.求树的深度 12.编写DFS算法的非递归函数。 13.用普里姆(Prim)算法构造最小生成树 14....
暴力、递归与分治、动态规划、贪心算法和回溯是算法设计中常见的几种思路和方法,经典习题是帮助我们更好掌握这些算法思想的重要途径。以下是对这些经典习题的详细说明: 1. 暴力解法习题 暴力解法往往是最直观、最...
在数学领域,斐波那契数列被用于解决数列求和问题以及递归算法的问题。在自然科学领域,斐波那契数列则可以用来描述生物繁殖的过程以及数学模型的发展。 此外,斐波那契数列还与美学和艺术有着紧密的联系。例如,在...
斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……想必看到这个数列大家很容易的就推算出来后面好几项的值,那么到底有什么规律,简单说,就是前两项的和是第三项的值,用递归...
23.2 Kruskal算法和Prim算法 思考题 本章注记 第24章 单源最短路径 24.1 Bellman?Ford算法 24.2 有向无环图中的单源最短路径问题 24.3 Dijkstra算法 24.4 差分约束和最短路径 24.5 最短路径...
雅各布斯塔尔序列是一个与斐波那契序列类似的加法序列,由递归关系Jn=Jn-1+2Jn-2定义,初始项J0=0,J1=1。序列中的一个数字称为雅可布沙尔数。它们是卢卡斯序列Un(P,Q)的一种特殊类型,其中P=1,Q=-2。 第一个...
左侧图示窗口包含棋盘和递归工作栈两部分,栈中记录含3个数据项,其中 adr 指示调用语句行号,k 指示列号,i 指示行号。此算法演示可求得所有可行结果,在求得每一种排布的结果之后,均会弹出一个窗口显示“找到第 ...
程序猿可能都知道 数据结构 + 算法 = 程序 ,慧眼识金的人懂得下下载这本算法导论的想必也知道它的经典,这是本清晰度还不错的pdf版本,外面好多资源,但都有内容不全的问题,这本是难得的全书,不用费力下载part ...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
0.1Booksandalgorithms(书和算法) 0.2EnterFibonacci(斐波那契数列) 0.3Big-Onotation(大O记号) Exercises(习题) 1Algorithmswithnumbers(数的算法) 1.1Basicarithmetic(基本算术) 1.2...
第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 5.4 概率分析和指示器随机变量的进一步使用 5.4.1 生日悖论 5.4.2 球与盒子 5.4.3 序列 …… 第二部分 排序和统计学 引言 第6章 堆排序 第7...
Fibonacci 是我创建的一个相对较小的项目,用于无限输出 fibonacci 序列,如 UITableView 中所示。 该项目的核心目标是提供一种高效且高性能的方法,可以在 64 位系统架构强加的整数精度限制范围之外无限生成...
引论1.1 本书讨论的内容1.2 数学知识复习1.2.1 指数1.2.2 对数1.2.3 级数1.2.4 模运算1.2.5 证明方法1.3 递归简论总结练习第2章 算法分析2.1 数学基础2.2 模型2.3 要分析的问题2.4 运行时间计算2.4.1 一个简单的例子...
组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理) 概率论(简单概率,条件概率,Bayes定理,期望值) 矩阵(矩阵的概念和运算...
@13.用普里姆(Prim)算法构造最小生成...层次的非递归算法 @10.求二叉树的深度(后序遍历) @11.求树的深度 @1.八皇后问题 @2.k阶斐波那契序列,要求满足fn ≤max而fn+1 >max 。(循环队列的容量仅为k或k+1) @3.约瑟夫环