斐波那契数列公式讲解(看图轻松理解斐波那契数列)
斐波那契数列公式讲解(看图轻松理解斐波那契数列)
2024-11-08 06:13:48  作者:奥特蛋男神  网址:https://m.xinb2b.cn/know/kan372781.html

前言

推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。

斐波那契

斐波那契(Leonardo Pisano ,Fibonacci, Leonardo Bigollo,1175年-1250年),又称列奥纳多,是中世纪意大利数学家。他是西方第一个研究斐波那契数列的人,并将现代书写数和乘数的位值表示法系统引入欧洲。主要作品包括《计算之书》、《几何实践》、《平方数书》等。

斐波那契数列

斐波那契数列,又称黄金分割数列或兔子数列,该数列为0、1、1、2、3、5、8、13、21、34、…,可以看到它的性质是前两项之和等于后一项。

兔子问题

斐波那契数列可以用来描述兔子繁殖问题,一般而言,兔子在出生两个月后就有繁殖能力,一对兔子每个月能生出一对小兔子。如果所有兔子都不死,那么一年后可以繁殖多少对兔子?实际结果如下,第一个月和第二个月,兔子还没有繁殖能力,所以都只有1对。第三个月生下第一对,总共有2对。第四个月老兔子继续生下一对,另一对还没有繁殖能力,总共有3对。以此类推,第五个月到第十二个月的兔子对数对应如下。


表达式



image

递归实现

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。


image

② fib(4)=fib(3) fib(2),需要继续调用fib(3),而fib(2)先不进入执行堆栈。


image

③ fib(3)=fib(2) fib(1),需要继续调用fib(2),fib(1)先不进入执行堆栈。


image

④ fib(2)=fib(1) fib(0),需要继续调用fib(1),fib(0)先不进入执行堆栈。


image

⑤ fib(1)返回1,停止往下调用,然后上一步的fib(0)进入堆栈。


image

fib(0)返回0,则 ④ 中的fib(2)=fib(1) fib(0)=1


image


image

然后,堆栈回到③中,因为fib(3)=fib(2) fib(1),所以将fib(1)入栈。


image

fib(1)返回1,则 ③ 中的fib(3)=fib(2) fib(1)=1 1=2。


image


image

然后,堆栈回到 ② 中,因为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。


image


image


image


image


image


  • 赤壁之战主要是谁的功劳(赤壁之战最大的赢家是谁)
  • 2024-11-08赤壁之战最大的赢家是谁赤壁之战东汉末年一场以少胜多的著名战役,战役的失败打掉了曹操想要短时间内统一全国的野望,奠定了三国鼎立的局面从战斗的损失上看,曹操无疑是最大的损失者,兵力消耗严重,荆州被刘备、孙权瓜分,还没有了同意南。
  • 激光切割机与雕刻机区别(激光雕刻机激光切割机)
  • 2024-11-08激光雕刻机激光切割机一、大功率激光产品测试认证大功率的激光产品在销售过程中,例如、激光雕刻机、激光切割机、激光打标机等等,不管是正常的线下销售、出口清关还是亚马逊、阿里巴巴等电商平台线上销售,都会涉及激光测试认证问题,尤。
  • 钉钉直播可以投屏到电视上看课吗(学校用钉钉直播课程)
  • 2024-11-08学校用钉钉直播课程开学了,孩子们上课成了问题,钉钉近日下载量猛增,用钉钉可以直播、回放、通知、提问打卡……等众多实用功能,学校老师最爱工具,学生们������也最的爱工具看到抖音上有家长上传关于钉钉直播投屏电视机的教程。
  • 40秒记一副牌记忆术(32秒就能记住一副牌)
  • 2024-11-0832秒就能记住一副牌一年多之前,他还是一名平凡的中学生,闲暇之余,喜欢背古诗、记地图如今,在刚结束不久的第27届世界脑力锦标赛上,他却以十项比赛项目总分3358分的优异成绩,获得了“世界记忆大师”称号他叫张韧孜,重庆八中。
  • 全自动巴氏消毒机怎么用(土耳其推出购物袋消毒机)
  • 2024-11-08土耳其推出购物袋消毒机央视网消息:近日,土耳其一家公司研发出一款能向食品购物袋喷洒消毒液的设备,深受民众喜爱据介绍,结账之后,民众只需把购物袋从机器里过一遍即可,短短几秒钟,顾客的双手、购物袋,以及袋子里的商品就被消毒干净。
  • 全新奥迪a1官图泄露(全新奥迪A1官图泄漏)
  • 2024-11-08全新奥迪A1官图泄漏日前,有外国媒体曝光了奥迪家族最小车型A1的第二代官图,据悉新车将与全新POLO以及Ibiza采用相同的MQB平台,并且将于本月内正式发布全新奥迪A1车身长度为4.03米,相比于现款车型增长了4厘米值。
  • 看图猜成语一共十个求正确答案 看图猜成语第八波
  • 2024-11-08看图猜成语一共十个求正确答案 看图猜成语第八波小时候最爱玩的游戏之一,包括纸上五子棋、填字游戏、看图猜成语、猜谜语、脑筋急转弯……都是非常简单,但又有神奇魔力、让人上瘾的小游戏长大以后,再玩这些小游戏,依然不觉得过时,也依然上瘾,只不过那时候玩的。
  • 那些年动漫用过的bgm(盘点动漫中经典的bgm)
  • 2024-11-08盘点动漫中经典的bgm相信大家看动漫的时候,会发现很多特别好听的bgm,以至于会把歌听完再开始看正片,还有些特别好听的片尾曲,即使正片看完,也会继续听完,今天我就为大家整理一下,我看过的动漫中,觉得十分经典的bgm,欢迎大。
  • 陈翔六点半公交车搞笑(陈翔六点半之重楼别)
  • 2024-11-08陈翔六点半之重楼别人生如戏,一旦开始就注定有曲终人散的那天很好看的一部电影,很多搞笑的包袱,也包含了一点戏剧的文化其实挺嘲讽当今的,君山和晓蓝爱情故事的现状在现如今比比皆是那种无奈也可能只有经历过的人才懂或许也只有电影。
  • 玉楼春嫁人(玉楼春打脸门当户对的婚姻)
  • 2024-11-08玉楼春打脸门当户对的婚姻白鹿、王一哲等人主演的古装剧《玉楼春》,从剧名、片头曲、插曲、片尾曲,都可以看出或者听出悲情氛围,已经给大结局埋下伏笔在这貌似借鉴了经典的人物设定和情节架构中,于正编剧用轻喜剧形式给观众呈现了一个新故。
  • 实体机和网络机的差距(如何区分线下机)
  • 2024-11-08如何区分线下机什么是“线下机”和“线上机”?这当然不是说“线下机”就是在线下买、“线上机”只在线上买这么简单,它的另一层含义是,哪些手机依靠除配置之外的其他卖点,或依靠信息差不对等来收割用户,这就是“线下机”;而配。