本文共 14151 字,大约阅读时间需要 47 分钟。
斐波那契 编辑 讨论 上传视频
斐波那契(Leonardo Pisano ,Fibonacci, Leonardo Bigollo,1175年-1250年),中世纪意大利数学家,是西方第一个研究斐波那契数的人,并将现代书写数和乘数的位值表示法系统引入欧洲。其写于1202年的著作《计算之书》中包涵了许多希腊、埃及、阿拉伯、印度、甚至是中国数学相关内容。 人物背景编辑 家庭 列奥纳多的父亲名为Guilielmo(威廉),外号Bonacci(意即「好、自然」或「简单」)。威廉是商人,在北非一带工作(今阿尔及利亚Bejaia),当时年轻的列奥纳多已经开始协助父亲工作,他学会了阿拉伯数字。 学习 有感使用阿拉伯数字比罗马数字更有效,列奥纳多前往地中海一带向当时著名的阿拉伯数学家学习,约于1200年回国。1202年,27岁的他将其所学写进《计算之书》(Liber Abaci)。这本书通过在记账、重量计算、利息、汇率和其他的应用,显示了新的数字系统的实用价值。这本书大大影响了欧洲人的思想,可是在三世纪后印制术发明之前,十进制数字并不流行。(例子:1482年,Ptolemaeus世界地图 ,Lienhart Holle在Ulm印制) 成就 列奥纳多曾成为热爱数学和科学的腓特烈二世 (神圣罗马帝国的皇帝)的坐上客。 欧洲数学在希腊文明衰落之后长期处于停滞状态,直到12世纪才有复苏的迹象。这种复苏开始是受了翻译、传播希腊、阿拉伯著作的刺激。对希腊与东方古典数学成就的发掘、探讨,最终导致了文艺复兴时期(15~16世纪)欧洲数学的高涨。文艺复兴的前哨意大利,由于其特殊地理位置与贸易联系而成为东西方文化的熔炉。意大利学者早在12~13世纪就开始翻译、介绍希腊与阿拉伯的数学文献。欧洲,黑暗时代以后第一位有影响的数学家斐波那契(约1175~1240),其拉丁文代表著作《计算之书》(Liber Abaci)和《几何实践》(Practica Geometriae)也是根据阿拉伯文与希腊文材料编译而成的,斐波那契,即比萨的列昂纳多(Leonardo of Pisa),早年随父在北非从师阿拉伯人习算,后又游历地中海沿岸诸国,回意大利后即写成《计算之书》(Liber Abaci,1202,亦译作《算盘全书》、《算经》)。《计算之书》最大的功绩是系统介绍印度记数法,影响并改变了欧洲数学的面貌。现传《算经》是1228年的修订版,其中还引进了著名的“斐波那契数列”。《几何实践》(Practica Geometriae, 1220)则着重叙述希腊几何与三角术。斐波那契其他数学著作还有《平方数书》(Liber Quadratorum, 1225)、《花朵》(Flos, 1225)等,前者专论二次丢番图方程,后者内容多为腓特烈二世(Frederick II)宫廷数学竞赛问题,其中包含一个三次方程/十2x2十10x~-20求解,斐波那契论证其根不能用尺规作出(即不可能是欧几里得的无理量),他还未加说明地给出了该方程的近似解(J一1. 36880810785)。微积分的创立与解析几何的发明一起,标志着文艺复兴后欧洲近代数学的兴起。微积分的思想根源部分(尤其是积分学)可以追溯到古代希腊、中国和印度人的著作。在牛顿和莱布尼茨最终制定微积分以前,又经过了近一个世纪的酝酿。在这个酝酿时期对微积分有直接贡献的先驱者包括开普勒、卡瓦列里、费马、笛卡)U、沃利斯和巴罗(1.Barrow,1630~1677)等一大批数学家。 人物轶事编辑 数列 斐波那契在《计算之书》中提出了一个有趣的兔子问题: 一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有的兔子都不死,那么一年以后可以繁殖多少对兔子? 我们不妨拿新出生的一对小兔子分析一下: 第一个月小兔子没有繁殖能力,所以还是一对; 两个月后,生下一对小兔总数共有两对; 三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对; …… 依次类推可以列出下表: 经过月数总体对数
0 1 1 2 3 5 8 13 21 34 55 89 144 表中数字1,1,2,3,5,8---构成了一个序列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。这个数列是意大利中世纪数学家斐波那契在《计算之书》中提出的,这个级数的通项公式,除了具有an+2=an+an+1的性质外,还可以证明通项公式为:an=1/√5 [(1/2+√5/2)^ n-(1/2-√5/2)^n](n=1,2,3…)(√5表示根号 5)。 这个通项公式中虽然所有的an都是正整数,可是它们却是由一些无理数表示出来的。 即在较高的序列,两个连续的“斐波纳契数”的序列相互分割将接近黄金比例(1.618:1或1:0.618)。 例如:233/144,987/610…… 斐波那契数列还有两个有趣的性质 兔子问题 兔子问题 ⒈斐波那契数列中任一项的平方数都等于跟它相邻的前后两项的乘积加1或减1; ⒉任取相邻的四个斐波那契数,中间两数之积(内积)与两边两数之积(外积)相差1。 质数 斐波那契质数由斐波那契序列中的质数组成,是整数质数序列。 第一组质数序列是:2,3,5,13,89,233,1597,28657,514229,433494437,2971215073…… C计算代码#include <stdio.h>
int fib(int x) { if(x1 || x2) { return 1; } else { return fib(x-1)+fib(x-2); } } int main() { int n=0; scanf("%d",&n); printf("%d",fib(n)); } 2. #include <stdio.h> int fib[1000001]={0,1,1}; int main() { int n=0; scanf("%d",&n); for(int i=3;i<=n;i++) { fib[i]=fib[i-1]+fib[i-2]; } printf("%d",fib[n]); return 0; } 重要作品编辑 Liber Abaci(计算之书,1202年)。 Practica Geometriae(几何实践,1220年)。 Flos(花朵,1225年),Johannes of Palermo提出的问题的答案。 Liber quadratorum(平方数书)关于丢番图方程的问题on Diophantine problems,that is,problems involving Diophantine equations. Di minor guisa(关于商业运算;己佚) 《几何原本》第十卷的注释(已佚) 拉丁文代表著作《珠算原理》 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。 斐波那契数列指的是这样一个数列: 自然中的斐波那契数列 自然中的斐波那契数列 这个数列从第3项开始,每一项都等于前两项之和。 斐波那契数列的定义者,是意大利数学家莱昂纳多·斐波那契(Leonardo Fibonacci),生于公元1170年,卒于1250年,籍贯是比萨。他被人称作“比萨的莱昂纳多”。1202年,他撰写了《算盘全书》(Liber Abacci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事,派驻地点于阿尔及利亚地区,莱昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。另外斐波纳契还在计算机C语言程序题中应用广泛 通项公式编辑 递推公式 斐波那契数列: 如果设an为该数列的第n项(),那么这句话可以写成如下形式: 显然这是一个线性递推数列。 通项公式 ⑴ (如上,又称为“比内公式”,是用无理数表示有理数的一个范例。) 注:此时 ⑵ an=[(2/√5+1)-1/(√5+1/2)ⁿ]/√5 通项公式推导 方法一:利用特征方程(线性代数解法) 线性递推数列的特征方程为:解得
则解得
方法二:待定系数法构造等比数列1(初等代数解法)
设常数, 使得 则 时,有:联立以上个式子,得:
上式可化简得:
那么:
(这是一个以为首项、以为末项、为公比的等比数列的各项的和)。
, 的解为, 则 方法三:待定系数法构造等比数列(初等代数解法) 设 得 构造方程 解得 所以:由(1)、(2)式得:
令:
化简可得:方法四:母函数法。
对于斐波那契数列,有() 令 那么有:因此.
不难证明:因此
再利用展开式 于是就可以得 其中 因此可以得到:与黄金分割的关系
有趣的是,这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618(或者说后一项与前一项的比值小数部分越来越逼近 0.618)。越到后面,的比值越接近黄金比。
证明两边同时除以得到:
若的极限存在,设其极限为,
则 所以 由于 解得: 所以极限是黄金分割比。 特性编辑 平方与前后项 从第二项开始,每个偶数项的平方都比前后两项之积多1,每个奇数项的平方都比前后两项之积少1。 如:第二项 1 的平方比它的前一项 1 和它的后一项 2 的积 2 少 1,第三项 2 的平方比它的前一项 1 和它的后一项 3 的积 3 多 1。 (注:奇数项和偶数项是指项数的奇偶,而并不是指数列的数字本身的奇偶,比如从数列第二项 1 开始数,第 4 项 5 是奇数,但它是偶数项,如果认为 5 是奇数项,那就误解题意,怎么都说不通) 证明经计算可得: 与集合子集 斐波那契数列的第n+2项同时也代表了集合中所有不包含相邻正整数的子集个数。 奇数项求和偶数项求和
平方求和
隔项关系
两倍项关系
其他公式
应用编辑
生活斐波那契 合并图册 合并图册(2张) 斐波那契数列中的斐波那契数会经常出现在我们的眼前——比如松果、凤梨、树叶的排列、某些花朵的花瓣数(典型的有向日葵花瓣),蜂巢,蜻蜓翅膀,超越数e(可以推出更多),黄金矩形、黄金分割、等角螺线等。 斐波那契数与植物花瓣 3……………………… 百合和蝴蝶花 5…………………… 蓝花耧斗菜、金凤花、飞燕草、毛茛花 8……………………… 翠雀花 13……………………… 金盏和玫瑰 21…………………… 紫宛 34、55、89……………雏菊 斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如,在树木的枝干上选一片叶子,记其为数0,然后依序点数叶子(假定没有折损),直到到达与那些叶子正对的位置,则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为叶序(源自希腊词,意即叶子的排列)比。多数的叶序比呈现为斐波那契数的比。 黄金分割 随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值 0.6180339887…… 杨辉三角 将杨辉三角左对齐,成图1所示排列,将同一斜行的数加起来,即得一数列 1、1、2、3、5、8、…… 图1 图1 公式表示如下:矩形面积
斐波那契数列与矩形面积的生成相关,由此可以导出一个斐波那契数列的一个性质。 斐波那契数列前几项的平方和可以看做不同大小的正方形,由于斐波那契的递推公式,它们可以拼成一个大的矩形。这样所有小正方形的面积之和等于大矩形的面积。则可以得到如下的恒等式:质数数量
斐波那契数列的整除性与质数生成性 每3个连续的数中有且只有一个被 2 整除, 每4个连续的数中有且只有一个被 3 整除, 每5个连续的数中有且只有一个被 5 整除, 每6个连续的数中有且只有一个被 8 整除, 每7个连续的数中有且只有一个被 13 整除, 每8个连续的数中有且只有一个被 21 整除, 每9个连续的数中有且只有一个被 34 整除, … 我们看到第5、7、11、13、17、23位分别是质数:5,13,89,233,1597,28657(第19位不是) 斐波那契数列的质数无限多吗? 尾数循环 斐波那契数列的个位数:一个60步的循环 11235,83145,94370,77415,61785,38190, 99875,27965,16730,33695,49325,72910… 进一步,斐波那契数列的最后两位数是一个300步的循环,最后三位数是一个1500步的循环,最后四位数是一个15000步的循环,最后五位数是一个150000步的循环。 自然界中“巧合” 斐波那契数列在自然科学的其他分支,有许多应用。例如,树木的生长,由于新生的枝条,往往需要一段“休息”时间,供自身生长,而后才能萌发新枝。所以,一株树苗在一段间隔,例如一年,以后长出一条新枝;第二年新枝“休息”,老枝依旧萌发;此后,老枝与“休息”过一年的枝同时萌发,当年生的新枝则次年“休息”。这样,一株树木各个年份的枝桠数,便构成斐波那契数列。这个规律,就是生物学上著名的“鲁德维格定律”。 另外,观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣,可以发现它们花瓣数目具有斐波那契数:3、5、8、13、21…… 其中百合花花瓣数目为 3,梅花 5 瓣,飞燕草 8 瓣,万寿菊 13 瓣,向日葵 21 或 34 瓣,雏菊有 34、55 和 89 三个数目的花瓣。 斐波那契螺旋:具有 13 条顺时针旋转和 21 条逆时针旋转的螺旋的蓟的头部 这些植物懂得斐波那契数列吗?应该并非如此,它们只是按照自然的规律才进化成这样。这似乎是植物排列种子的“优化方式”,它能使所有种子具有差不多的大小却又疏密得当,不至于在圆心处挤了太多的种子而在圆周处却又稀稀拉拉。叶子的生长方式也是如此,对于许多植物来说,每片叶子从中轴附近生长出来,为了在生长的过程中一直都能最佳地利用空间(要考虑到叶子是一片一片逐渐地生长出来,而不是一下子同时出现的),每片叶子和前一片叶子之间的角度应该是 222.5°,这个角度称为“黄金角度”,因为它和整个圆周 360° 之比是黄金分割数0.618033989……的倒数,而这种生长方式就决定了斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到 89,甚至 144 条。1992 年,两位法国科学家通过对花瓣形成过程的计算机仿真实验,证实了在系统保持最低能量的状态下,花朵会以斐波那契数列长出花瓣。 数字谜题 三角形的三边关系定理和斐波那契数列的一个联系: 现有长为 144 cm 的铁丝,要截成n小段(n>2),每段的长度不小于 1 cm,如果其中任意三小段都不能拼成三角形,则n的最大值为多少? 分析:由于形成三角形的充要条件是任何两边之和大于第三边,因此不构成三角形的条件就是存在两边之和不超过另一边。截成的铁丝最小为 1,因此可以放 2 个 1,第三条线段就是 2(为了使得n最大,因此要使剩下来的铁丝尽可能长,因此每一条线段总是前面的相邻2段之和),依次为:1、1、2、3、5、8、13、21、34、55,以上各数之和为 143,与 144 相差 1,因此可以取最后一段为 56,这时 n 达到最大为 10。 我们看到,“每段的长度不小于 1”这个条件起了控制全局的作用,正是这个最小数1 产生了斐波那契数列,如果把 1 换成其他数,递推关系保留了,但这个数列消失了。这里,三角形的三边关系定理和斐波那契数列发生了一个联系。 在这个问题中,144>143,这个143是斐波那契数列的前项和,我们是把144超出143的部分加到最后的一个数上去,如果加到其他数上,就有3条线段可以构成三角形了。 影视作品中的斐波那契数列 斐波那契数列在欧美可谓是尽人皆知,于是在电影这种通俗艺术中也时常出现,比如在风靡一时的《达芬奇密码》里它就作为一个重要的符号和情节线索出现,在《魔法玩具城》里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。可是虽说叫得上名,多数人也就背过前几个数,并没有深入理解研究。在电视剧中也出现斐波那契数列,比如:日剧《考试之神》第五回,义嗣做全国模拟考试题中的最后一道数学题~在FOX 热播美剧《Fringe》中更是无数次引用,甚至作为全剧宣传海报的设计元素之一。 推广编辑 斐波那契—卢卡斯数列 卢卡斯数列 1、3、4、7、11、18…,也具有斐波那契数列同样的性质。(我们可称之为斐波那契—卢卡斯递推:从第三项开始,每一项都等于前两项之和 卢卡斯数列的通项公式为 这两个数列还有一种特殊的联系(如下表所示),,及1
2 3 4 5 6 7 8 9 10 … 斐波那契数列F(n) 1 1 2 3 5 8 13 21 34 55 … 卢卡斯数列L(n) 1 3 4 7 11 18 29 47 76 123 …1
3 8 21 55 144 377 987 2584 6765 … 类似的数列还有无限多个,我们称之为斐波那契—卢卡斯数列。 如1,4,5,9,14,23…,因为1,4开头,可记作F[1,4],斐波那契数列就是F[1,1],卢卡斯数列就是F[1,3],斐波那契—卢卡斯数列就是F[a,b]。 斐波那契—卢卡斯数列之间的广泛联系 ①任意两个或两个以上斐波那契—卢卡斯数列之和或差仍然是斐波那契—卢卡斯数列。 如:F[1,4]n+F[1,3]n=F[2,7]n,F[1,4]n-F[1,3]n=F[0,1]n=F[1,1](n-1), n 1 2 3 4 5 6 7 8 9 10 … F[1,4]n 1 4 5 9 14 23 37 60 97 157 … F[1,3]n 1 3 4 7 11 18 29 47 76 123 … F[1,4]n-F[1,3]n 0 1 1 2 3 5 8 13 21 34 … F[1,4]n+F[1,3]n 2 7 9 16 25 41 66 107 173 280 … ②任何一个斐波那契—卢卡斯数列都可以由斐波那契数列的有限项之和获得,如 n 1 2 3 4 5 6 7 8 9 10 … F 1 1 2 3 5 8 13 21 34 55 … F 0 1 1 2 3 5 8 13 21 34 … F 0 1 1 2 3 5 8 13 21 34 … F[1,3]n 1 3 4 7 11 18 29 47 76 123 … 黄金特征与孪生斐波那契—卢卡斯数列 斐波那契—卢卡斯数列的另一个共同性质:中间项的平方数与前后两项之积的差的绝对值是一个恒值, 斐波那契数列: 卢卡斯数列:|33-14|=|44-37|=…=5 F[1,4]数列:|44-15|=11 F[2,5]数列:|55-27|=11 F[2,7]数列:|77-29|=31 斐波那契数列这个值是1最小,也就是前后项之比接近黄金比例最快,我们称为黄金特征,黄金特征1的数列只有斐波那契数列,是独生数列。卢卡斯数列的黄金特征是5,也是独生数列。前两项互质的独生数列只有斐波那契数列和卢卡斯数列这两个数列。 而F[1,4]与F[2,5]的黄金特征都是11,是孪生数列。F[2,7]也有孪生数列:F[3,8]。其他前两项互质的斐波那契—卢卡斯数列都是孪生数列,称为孪生斐波那契—卢卡斯数列。 广义斐波那契数列 斐波那契数列的黄金特征1,还让我们联想到佩尔数列:1,2,5,12,29,…,也有|22-15|=|55-212|=…=1(该类数列的这种特征值称为勾股特征)。 佩尔数列Pn的递推规则: 据此类推到所有根据前两项导出第三项的通用规则:,称为广义斐波那契数列。 当时,我们得到斐波那契—卢卡斯数列。 当时,我们得到佩尔—勾股弦数(跟边长为整数的直角三角形有关的数列集合)。 当时,我们得到等差数列。其中时,我们得到自然数列1,2,3,4,5…自然数列的特征就是每个数的平方与前后两数之积的差为 1(等差数列的这种差值称为自然特征)。 具有类似黄金特征、勾股特征、自然特征的广义——斐波那契数列 。 当,时,我们得到等比数列1,2,4,8,16… 相关数学编辑 排列组合 有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第 10 级台阶有几种不同的走法? 这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种登法…… 1,2,3,5,8,13…… 所以,登上十级,有 89 种走法。 类似的,一枚均匀的硬币掷10次,问不连续出现正面的可能情形有多少种? 答案是种。 求递推数列的通项公式 由数学归纳法可以得到:,将斐波那契数列的通项式代入,化简就得结果。 兔子繁殖问题 斐波那契数列又因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。 一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子? 我们不妨拿新出生的一对小兔子分析一下: 第一个月小兔子没有繁殖能力,所以还是一对 两个月后,生下一对小兔对数共有两对 三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对 ------ 依次类推可以列出下表: 经过月数 0 1 2 3 4 5 6 7 8 9 10 11 … 幼仔对数 1 0 1 1 2 3 5 8 13 21 34 55 … 成兔对数 0 1 1 2 3 5 8 13 21 34 55 89 总体对数 1 1 2 3 5 8 13 21 34 55 89 144 幼仔对数=前月成兔对数 成兔对数=前月成兔对数+前月幼仔对数 总体对数=本月成兔对数+本月幼仔对数 可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。 这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有a(n+2)=an+a(n+1)的性质外,还可以证明通项公式为:an=(1/√5){[(1+√5)/2]n-[(1-√5)/2]n}(n=1,2,3,…) 数列与矩阵 对于斐波那契数列1、1、2、3、5、8、13、……。有如下定义 F(n)=F(n-1)+F(n-2) F(1)=1 F(2)=1 对于以下矩阵乘法 F(n+1) = (1,1 ) (F(n),F(n-1))T F(n) =(1,0 ) (F(n),F(n-1))T 它的运算就是右边的矩阵 (1,1)乘以矩阵(F(n),F(n-1)),右边的矩阵(1,0 ) 乘以矩阵(F(n),F(n-1)),得到: F(n+1)=F(n)+F(n-1) F(n)=F(n) 可见该矩阵的乘法完全符合斐波那契数列的定义 设矩阵A=第一行(1,1)第二行(1,0) 迭代n次可以得到:F(n+1) =A^(n) ( F(2),F(1))T= A^(n)(1,1)T 这就是斐波那契数列的矩阵乘法定义。 另矩阵乘法的一个运算法则A^n(n为偶数) = A^(n/2) A^(n/2),这样我们通过二分的思想,可以实现对数复杂度的矩阵相乘。 因此可以用递归的方法求得答案。 数列值的另一种求法:其中[x]表示取距离x最近的整数。
斐波那契弧线编辑 斐波那契弧线,也称为斐波那契扇形线。第一,此趋势线以二个端点为准而画出,例如,最低点反向到最高点线上的两个点。然后通过第二点画出一条“无形的(看不见的)”垂直线。然后,从第一个点画出第三条趋势线:38.2%, 50%和61.8%的无形垂直线交叉。 斐波纳契弧线,是潜在的支持点和阻力点水平价格。斐波纳契弧线和斐波纳契扇形线常常在图表里同时绘画出。支持点和阻力点就是由这些线的交汇点得出。 要注意的是弧线的交叉点和价格曲线会根据图表数值范围而改变,因为弧线是圆周的一部分,它的形成总是一样的。 C#代码实现编辑 public static int GetiNum(int i) { if (i == 0) return 0; else if (i == 1 || i == 2) return 1; return GetiNum(i - 1) + GetiNum(i - 2);}
Java代码实现编辑
//①==================================
/**- 平推方法实现 */ public static long fibLoop(int num) { if(num < 1 || num > 92) return 0; long a = 1; long b = 1; long temp; for(int i = 3; i <= num; i++) { temp = a; a = b; b += temp; } return b; }
//②==================================
/**- 递归方法实现
- f(n) = f(n - 1) + f(n - 2)
- 最高支持 n = 92 ,否则超出 Long.MAX_VALUE
- @param num n
- @return f(n) */ public static long fibRec(int num) { if(num < 1) return 0; if(num < 3) return 1; return fibRec(num - 1) + fibRec(num - 2); }
//③==================================
static long[] l = new long[93]; static { l[1] = 1; } /**- 带有缓存的方法,比fibRec方法性能好很多 */ public static long fibBuffRec(int num) { if(num < 1 || num > 92) return 0; if(l[num] == 0) l[num] = fibBuffRec(num - 1) + fibBuffRec(num - 2); return l[num]; }
//④==================================
static List list = new ArrayList(93); static { list.add(BigDecimal.ZERO); list.add(BigDecimal.ONE); } /**- 1,2,3,4,5,6, 7 ,8
- 1,1,2,3,5,8,13,21
- 支持num超过92的超大型数字,使用了ArrayList进行缓存以提高性能 */ public static BigDecimal fibBig(int num) { if(num < 0) return list.get(0); if (list.size() <= num) list.add(fibBig(num - 1).add(fibBig(num - 2))); return list.get(num); } Javascript代码实现编辑 function f(n, a1 = 1, a2 = 1) { if (n <= 1) {return a1}; return f(n-1, a2, a1 + a2); } console.log(f(1450)); // 可以计算到1450位,不溢出 C++代码实现编辑 基本循环算法 #include<bits/stdc++.h> using namespace std; int main() { int a=0,b=1,c=1,n; cin>>n;//输入n for(int i=1;i<=n;i++) { a=b; b=c; c=a+b; } cout<<c;//输出最终结果 return 0; } 数组算法实现 #include using namespace std; int main() { int a[30],i,n; cin>>n; a[1]=a[0]=1; for(i=2;i<n;i++) { a[i]=a[i-2]+a[i-1]; } cout<<a[n-1]; return 0; } 递归算法实现 1 2 3 4 5 6 7 8 9 10 11 12 13 #include using namespace std; int f(int n) { return (n<3)? 1 : f(n-1)+f(n-2);//如果是前两项,则输出1 } int main() { int n; cin>>n; cout<<f(n); return 0; } 递归算法优化(记忆化搜索)
include <bits/stdc++.h>
const int MAX=101;
using namespace std; int a[MAX]; int f(int n) { if(a[n]!=-1) return a[n]; else { a[n]=f(n-1)+f(n-2); return a[n]; } } int main() { int n; cin>>n; for(int i=0;i<=MAX-1;i++) {//初始化 a[i]=-1; } a[0]=0;a[1]=1; cout<<f(n); return 0; } 高精度计算#include <bits/stdc++.h>
using namespace std; char sum[1200]; int s=0,m=0,n; int main() { cin>>n; string s1,s2; int a[1200],b[1200]; int he,i; s1=“0”; s2=“1”; for(m=2;m<n+1;m++) { memset(a,0,sizeof a); memset(b,0,sizeof b); a[0]=s1.length(); for(i=1;i<=a[0];i++) { a[i]=s1[a[0]-i]-‘0’; } b[0]=s2.length(); for(i=1;i<=b[0];i++) { b[i]=s2[b[0]-i]-‘0’; } he=(a[0]>b[0]?a[0]:b[0]); for(i=1;i<=he;i++) { a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; } he++; while((a[he]==0)&&(he>1)) he–; for(i=he,s=0;i>=1;i–,s++) { sum[s]=a[i]+‘0’; } s1=s2; s2=sum; } cout<<s2<<endl; return 0; } Python3代码实现编辑#输出在3000以内的斐波那契数列
一、从最大值考虑
numMax = int(input('please input a maxnumber : '))
def flibsOne(numMax):
c = [] a, b = 0, 1 while a < numMax: a, b = b, a + b c.append(a) c.remove(c[-1]) print(c)
二、从位数考虑
num = int(input('please input a number : '))
def flibsTwo(num):
list1 = [] for i in range(num): if i <=1: list1.append(1) else: list1.append(list1[-2] + list1[-1])return list1
print(flibsTwo(num)) #输出num位数列
第三种,根据f(n)= f(n-1)+f(n-2)实现
Fbs = [1,1]#斐波那契数列前两位 n = 3 s = input("Maxmun “)#输入最大次数 while n != (int(s)+1) :#因为差一原则所以要再加一 a = Fbs[-1] b = Fbs[-2] fb = a+b print(str(n)+” "+str(fb)) n = n +1 Fbs.append(fb) php代码实现编辑 n = 输 入 值 ; i f ( n = 输入值; if ( n=输入值;if(n >= 3) { x = 1 ; x = 1; x=1;y = 1;$n = $n - 2; do { $fs = $x + $y; $x = $y; $y = $fs; echo $fs.’,’; KaTeX parse error: Expected 'EOF', got '}' at position 14: n--; }̲ while (n > 0); } Rust代码实现编辑 // Rust代码实现fn main() {
println!("{} {} {} {} {}", fib(0), fib(1), fib(2), fib(3), fib(4)); }fn fib(d: i32) -> i32 {
if d == 0 || d == 1 { d } else { ficc(d - 2) + ficc(d - 1) } } 百度搜索:斐波那契----百度百科:斐波那契数列和斐波那契本人简介转载地址:https://blog.csdn.net/m0_38127487/article/details/113768085 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!