内容简介:推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。斐波那契(Leonardo Pisano ,Fibonacci, Leonardo Bigollo,1175年-1250年),又称列奥纳多,是中世纪意大利数学家。他是西方第一个研究斐波那契数列的人,并将现代书写数和乘数的位值表示法系统引入欧洲。主要作品包括《计算之书》、《几何实践》、《平方数书》等。斐波那契数列,又称黄金分
推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种 排序 等等几十篇的样子。
斐波那契
斐波那契(Leonardo Pisano ,Fibonacci, Leonardo Bigollo,1175年-1250年),又称列奥纳多,是中世纪意大利数学家。他是西方第一个研究斐波那契数列的人,并将现代书写数和乘数的位值表示法系统引入欧洲。主要作品包括《计算之书》、《几何实践》、《平方数书》等。
斐波那契数列
斐波那契数列,又称黄金分割数列或兔子数列,该数列为0、1、1、2、3、5、8、13、21、34、...,可以看到它的性质是前两项之和等于后一项。
兔子问题
斐波那契数列可以用来描述兔子繁殖问题,一般而言,兔子在出生两个月后就有繁殖能力,一对兔子每个月能生出一对小兔子。如果所有兔子都不死,那么一年后可以繁殖多少对兔子?实际结果如下,第一个月和第二个月,兔子还没有繁殖能力,所以都只有1对。第三个月生下第一对,总共有2对。第四个月老兔子继续生下一对,另一对还没有繁殖能力,总共有3对。以此类推,第五个月到第十二个月的兔子对数对应如下。
月数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
对数 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
表达式
递归实现
int fib(int n){ if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); } 复制代码
假如n=4时,看看递归过程的堆栈情况。
① 调用fib函数,传入参数值4。
② fib(4)=fib(3)+fib(2),需要继续调用fib(3),而fib(2)先不进入执行堆栈。
③ fib(3)=fib(2)+fib(1),需要继续调用fib(2),fib(1)先不进入执行堆栈。
④ fib(2)=fib(1)+fib(0),需要继续调用fib(1),fib(0)先不进入执行堆栈。
⑤ fib(1)返回1,停止往下调用,然后上一步的fib(0)进入堆栈。
fib(0)返回0,则 ④ 中的fib(2)=fib(1)+fib(0)=1
然后,堆栈回到③中,因为fib(3)=fib(2)+fib(1),所以将fib(1)入栈。
fib(1)返回1,则 ③ 中的fib(3)=fib(2)+fib(1)=1+1=2。
然后,堆栈回到 ② 中,因为fib(4)=fib(3)+fib(2),所以将fib(2)入栈。而fib(2)=fib(1)+fib(0),于是将fib(1)入栈。此时fib(1)直接返回1,然后继续将fib(0)入栈。则fib(2)=fib(1)+fib(0)=1,最后fib(4)=fib(3)+fib(2)=3。
-------------推荐阅读------------
我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、 mysql 协议、chatbot)
跟我交流,向我提问:
欢迎关注:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 算法记录 >> 斐波那契数列
- 蓝桥杯 ALGO-45 算法训练 调和数列问题
- numpy中linspace用法 (等差数列创建函数)
- 算法 - 打印1000以内的斐波那契数列
- FreeCodeCamp 中级算法题 - 斐波那契数列奇数项求和
- 几个经典算法(九九乘法表,斐波那契数列)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
无处安放的互联网隐私
【美】茱莉亚·霍维兹 【美】杰拉米·斯科 / 中国人民大学出版社有限公司 / 2017-7-1 / CNY 55.00
在当今互联网时代,我们的隐私权已经受到了威胁,政府或企业可以追踪我们的电话,搜索引擎可以记录我们的在线浏览记录以及恒温器的设置以及更多信息。在当代,保卫隐私权不只是简单地描述出存在的问题或者警告人们隐私权已经丧失,隐私权的护卫者们提出了解决策略。他们密切关注商业实践、公共政策和技术设计以及人物,应该继续下去吗?条件就是:有问题,让我们找到解决之道。一起来看看 《无处安放的互联网隐私》 这本书的介绍吧!
XML、JSON 在线转换
在线XML、JSON转换工具
UNIX 时间戳转换
UNIX 时间戳转换