下载文档原格式
走台阶问题如：总共100级台阶（任意级都行），小明每次可选择走1步、2步或者3步，问走完这100级台阶总共有多少种走法？解析：这个问题本质上是斐波那契数列，假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级,f(2)=2。
如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-1级台阶，有f(n-1)种跳法，假如第一次条2级台阶，剩下n-2级台阶，有f(n-2)种跳法。
这就表示f(n)=f(n-1)+f(n-2)。
将上面的斐波那契数列代码稍微改一下就是本题的答案f(n)=f(n-1)+f(n+2)斐波那契数列斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：F(n)=F(n-1)+F(n-2)递推数列显然这是一个线性。
数学定义：递归斐波纳契数列以如下被以的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）由兔子生殖问题引出、生物 (计算科学)特性：这个数列从第3项开始，每一项都等于前两项之和。
特别指出：第1项是0，第2项是第一个1。
代码：public class Test { static final int s = 100; //自定义的台阶数static int compute(int stair){ if ( stair <=0){ return0; } if (stair ==1){ return1; } if (stair ==2){ return2; } return compute(stair-1) + compute(stair-2);//return 递归进行计算 --->递归思想进行数据计算处理在斐波那契数列中后一项的值等于前两项的和 } public static void main(String args[]) { System.out.println("共有" + compute(s) + "种走法"); } }return compute(stair-1) + compute(stair-2);在return子句中调用调用compute函数由斐波那契数列特性得到最后的值分值拆分。
高中数学中的斐波那契数列问题小结作者简介：任所怀，男，山西省原平市原平一中数学教师。
生于1973年9月10日，主要致力于中学数学教学研究，联系邮箱：rsh73910@解：b猜想二：1232343,8a a a a a a +==+==，于是猜想：53464513,21a a a a a a =+==+=。
这两种猜想，哪一个正确？就必须从已知进行推理分析。
对于n （3)n ≥个从上而下的正方形要着黑色或白色，所有黑色正方形互不相邻的着色方案n a 种，可分为两类：第一类：最上面的正方形着白色。
此时下面的1n -个正方形的着色方案则有1n a -种；第二类：最上面的正方形着黑色。
此时与它相邻的正方形必着白色，而余下的n-2个正方形的着色方案有2n a -种。
于是由加法原理得12(3)n n n a a a n --=+≥显然是猜想二是正确的。
这一高考题的背景显然是斐波那契数列，跟这一问题类似的还有登台阶问题。
问题四：有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?解：设按规定登n 阶台阶的走法有n a 种，则11a =，22a =。
当3n ≥时，登n 阶台阶的走法可分为两类：第一类：第一步登一级台阶，则余下的1n -级台阶有1n a -种走法；第二类：第一步登两级台阶，则余下的2n -级台阶有2n a -种走法。
由加法原理得12n n n a a a --=+。
于是数列{}n a 是一个斐波那契数列，这一问题也就迎刃而解。
说到这里，我们会发现，高中数学中对于斐波那契数列问题的解决不约而同地都用到了分类计数原理。
所以对于斐波那契数列的研究只要我们找对研究的方向，并不会超出高中数学范围，相反通过这样不同于等差等比数列问题的研究，更能加强学生对基本原理的应用能力，从而增加其创新能力。
斐波那契数列-爬楼梯-⼤数问题在你⾯前有⼀个n阶的楼梯，你⼀步只能上1阶或2阶。
请问计算出你可以采⽤多少种不同的⽅式爬完这个楼梯。
这个问题乍⼀看就是简单的斐波那契数列问题，但是当楼梯数量到达⼀定数量后，例如 39，此时基本数据类型 int 或 long 都会溢出。
所以需要解决⼤数的问题。
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int target = sc.nextInt();int[] list = { 0, 1, 2 };if (target < 3) {System.out.println(list[target]);return;}String jumpNOne = "2";// 最后只跳⼀步String jumpNTwo = "1";// 最后跳两步String jumpN = "0";// 统计跳 target 个台阶的⽅案for (int i = 3; i <= target; i++) {jumpN = bigData(jumpNTwo, jumpNOne);jumpNTwo = jumpNOne;jumpNOne = jumpN;}System.out.println(jumpN);} ⼤数问题：// s2 >= s1public static String bigData(String s1, String s2) {String result = "";// 记录相加结果int flag = 0;// 记录是否有进位int i = s1.length() - 1;// 记录s1 的最后⼀位，也就是个位数int j = s2.length() - 1;// 记录s2 的最后⼀位，也就是个位数int temp = 0;while (i >= 0 || j >= 0) {// s2 ⼀定⽐ s1 ⼤，所以可能存在 s2 ⽐ s1 多⼀位if (i < 0) {//temp = s2.charAt(j) - '0' + flag;result = new Integer(temp).toString() + result;flag = 0;} else {temp = (s1.charAt(i) - '0') + (s2.charAt(j) - '0') + flag;flag = temp / 10;temp = temp % 10;result = new Integer(temp).toString() + result;}i--;j--;}if(flag == 1)result = "1" + result;return result;}。
浅谈斐波那契数列在生活中的应用摘要：数学是一门来自生活又高于生活的科学，数学研究是人类社会进步的动力。
数列知识在生活中也有着广泛的应用，例如生物种群数量的变化，银行的利息计算，人口增长，粮食增长、住房建设等，都会用到数学知识。
本文介绍斐波那契数列的简单情况，可以帮助学生提高对数列的知识。
数列是数学学习中一个非常重要的分支，并且因为数列的研究和计算与社会经济和资源生活紧密相关，加上灵活多变的计算，有趣的问题等，都使得对于数列的研究受到越来越多人的关注。
关键词：斐波那契数列应用黄金分割1 引言数列在我们的生活中具有广泛的应用，例如资源计算等问题，并且在解决诸如投资分配，汇率计算和资源利用分配等问题方面具有无可比拟的优势。
本文将简要介绍数列广泛应用，分析斐波那契数在上述几个生活领域中的应用。
斐波那契数列在现实生活中被广泛使用，研究它以使其服务于我们的生活具有很大的意义。
人类很早就看到了大自然的数学特征：蜜蜂的繁殖规律，树枝、钢琴音阶的排列以及花瓣在花托边缘的对称分布、整个花朵几乎完美无缺地呈现出辐射对称性……，所有这一切向我们展示了许多美丽的数学模式。
对自然、社会和生活中的许多现象的解释，通常可归因于斐波那契数列上来。
斐波那契数列在数学理论中有许多有趣的特性，似乎在自然界中也存在着这个性质，都被斐波那契数列支持。
2 斐波那契数列的应用（1）斐波那契数列和花瓣数花瓣数是极有特征的。
多数情况下，花瓣的数目都是3，5，8，13，21，34，55，…这些数恰好是斐波那契数列的某些项，例如，海棠2瓣花瓣，铁栏、百合花和兰花以及茉莉花都有3瓣花瓣，洋紫荆、黄蝉和蝴蝶兰是5瓣花瓣。
万寿菊的花瓣有13瓣；至良属的植物有5瓣花瓣；许多翠雀属植物有8瓣花瓣；雏菊属植物有89、55或者34个瓣花瓣。
（2）斐波那契数列和仙人掌的结构在仙人掌的结构中有这一数列的特征。
研究人员分析了仙人掌的形状、叶片的厚度以及控制仙人掌情况的其他因素，并将数据输入计算机，结果发现仙人掌的斐波那契序列结构使仙人掌能够最大限度地减少能量消耗并适应干旱沙漠中的生长环境。
走台阶问题如：总共100级台阶（任意级都行），小明每次可选择走1步、2步或者3步，问走完这100级台阶总共有多少种走法？解析：这个问题本质上是斐波那契数列，假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级,f(2)=2。
如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-1级台阶，有f(n-1)种跳法，假如第一次条2级台阶，剩下n-2级台阶，有f(n-2)种跳法。
这就表示f(n)=f(n-1)+f(n-2)。
将上面的斐波那契数列代码稍微改一下就是本题的答案f(n)=f(n-1)+f(n+2)斐波那契数列斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：F(n)=F(n-1)+F(n-2)递推数列显然这是一个线性。
数学定义：递归斐波纳契数列以如下被以的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）由兔子生殖问题引出、生物 (计算科学)特性：这个数列从第3项开始，每一项都等于前两项之和。
特别指出：第1项是0，第2项是第一个1。
代码：public class Test { static final int s = 100; //自定义的台阶数static int compute(int stair){ if ( stair <=0){ return0; } if (stair ==1){ return1; } if (stair ==2){ return2; } return compute(stair-1) + compute(stair-2);//return 递归进行计算 --->递归思想进行数据计算处理在斐波那契数列中后一项的值等于前两项的和 } public static void main(String args[]) { System.out.println("共有" + compute(s) + "种走法"); } }return compute(stair-1) + compute(stair-2);在return子句中调用调用compute函数由斐波那契数列特性得到最后的值分值拆分。
标数法与牛顿台阶问题关于“标数法”，先来看两个最简单的例子。
例1：从A到B的最短路径有多少条？楚香凝解析：从A到C有一种路径，所以在C点标记个“1”；从A到D有一种路径，所以在D点也标记一个1；到B点有两类情况，可以从C过来，也可以从D过来，所以到达B点的情况数=（到达C点的情况数）+（到达D点的情况数），所以在B点标记1+1=“2”。
例2：从A到B的最短路径有多少条？楚香凝解析：从A到C有一种路径，所以在C点标记个“1”；从A到D有一种路径，所以在D点也标记一个1；到E点有两类情况，可以从C过来，也可以从D过来，所以在E 点标记1+1=“2”；从A到F有一种路径，所以在F点标记个“1”；到B点有两类情况，可以从F过来，也可以从E过来，所以在B点标记1+2=“3”。
注意：标数法适用的前提条件为“最短路径”，更通俗来讲，即不能走“回头路”。
下面来看近几年出现过的三道真题。
例1：A、B、C三地的地图如下图所示，其中A在C正北，B在C正东，连线处为道路。
如要从A地到达B地，且途中只能向南、东和东南方向行进，有多少种不同的走法：【山东2014】A.9B.11C.13D.15楚香凝解析：标数法，共15种，选D例2：从A地到B地的道路如图所示，所有转弯均为直角，问如果要以最短距离从A地到达B地，有多少种不同的走法可以选择？【黑龙江2015】A.14B.15C.18D.21楚香凝解析：标数法，共15种，选B例3：下图为某大厦走火通道逃离路线。
某大厦集中所有的人员开展火灾逃生演习，从入口A点出发，要沿某几条线段才到出口F点。
逃离中，同一个点或同一线段只能经过1次。
假设所有逃离路线都是安全的，则不同的逃离路线最多有（）种。
【广州2015】A.8B.9C.10D.11楚香凝解析：此题与标数法的区别在于，可以往上和斜上走，所以标数法不再适用，需分类计算；A→D，之后有四种；A→B→D，之后有三种；A→B→C，之后有三种；共10种，选C牛顿台阶问题（斐波那契递推数列）例1：十阶楼梯，小张每次只能走一阶或者两阶，请问走完此楼梯共有多少种方法？A.55B.67C.74D.89楚香凝解析：解法一：列举找规律；阶梯数: 1 2 3 4 5 6 7 8 9 10方法数: 1 2 3 5 8 13 21 34 55 89走到1阶只有1种方法；走到2阶有2种（1+1或直接上2阶）；走到3阶有3种（1+1+1或1+2或2+1）…依次类推，选D解法二：到达第十阶的前一步只有两类情况：【从第九阶迈一步上来】或者【从第八阶迈两步上来】，所以到达第十阶的情况数=（到达第九阶的情况数）+（到达第八阶的情况数），以此类推，到达某阶的情况数等于前面两个数之和（前两项通过列举得到），由此可得斐波那契递推数列1、2、3、5、8、13、21、34、55、89，选D解法三：分类计算；走五次两阶、共五步，有1种；走四次两阶、共六步，选出四步来走两阶，有C（6 4）=15种；走三次两阶、共七步，选出三步来走两阶，有C（7 3）=35种；走两次两阶、共八步，选出两步来走两阶，有C（8 2）=28种；走一次两阶、共九步，选出一步来走两阶，有C（9 1）=9种；走0次两阶，有1种；共1+15+35+28+9+1=89种，选D拓展：十阶楼梯，小张每次只能走一阶或者两阶或者三阶，请问走完此楼梯共有多少种方法？A.89B.169C.230D.274楚香凝解析：到达第十阶的情况数=（到达第九阶的情况数）+（到达第八阶的情况数）+（到达第七阶的情况数），以此类推…到达某阶的情况数等于前面三个数之和（前三项通过列举得到），由此可得斐波那契递推数列如下：阶梯数: 1 2 3 4 5 6 7 8 9 10方法数: 1 2 4 7 13 24 44 81 149 274例2：小璐有8元钱，她准备从明天起，用这8元钱每天买一个冰激淋或者一包果冻吃。
2014年温州市小学数学小课题评比学校：苍南县钱库小学成员姓名：陈耀坤吴文强金旭杭指导教师：***生活中的“斐波那契数列”——台阶中的数学一、问题的提出周末爸爸妈妈带我去龙港影城看3D电影，影城的大门口有16级水泥台阶，我发现老年人大多是一级一级地往上走的，年轻的小伙子喜欢两级两级地往上走，小朋友则是一会儿走一级，一会儿又蹦两级……很快，一个念头闪入我的脑海：按照他们这样不同的走法，走完这16级台阶，一共会有多少种不同的走法呢？会不会有什么规律呢？于是，在爸爸妈妈的鼓励下，我决定开始台阶走法的研究。
二、研究过程1.从最简单的做起该怎样开展研究呢？我找了两个好朋友，做合作伙伴。
我们想起了老师曾经提到过的华罗庚说的话:“善于退，足够地退，退到最原始的而不失重要的地方是学好数学的一个诀窍。
”也就是说可以“从最简单的做起”于是我们通过画楼梯入手。
1个台阶（1种）2个台阶（2种）3个台阶（3种）4个台阶（5种）……后来我觉得用这种表示方法实在太麻烦了，有没有更简捷的表达方法呢？于是在数学老师的启发下就想到了用最简单的数字来表达：楼梯台阶数及方法楼梯上法表示一个台阶（1种）（1）二个台阶（2种）（1，1）（2）三个台阶（3种）（1，1，1）（1，2）（2，1）四个台阶（5种）（1，1，1 ，1）（1，1，2）（1，2，1）（2，1，1）（2，2）五个台阶（8种）（1，1，1，1，1）（1，1，1，2）（1，1，2，1）（1，2，1，1）（2，1，1，1）（2，1，2）（2，2，1）（1，2，2） 5个台阶有8种走法，那现在求16个台阶有几种走法，该怎么办呢？我们想用这个方法继续进行进去，我尝试着：六个台阶（13种）（1，1，1，1，1，1）（1，2，1，1，1）（1，1，2，1，1）（1，1，1，2，1）（1，1，1，1，2）（2，1，1，1，1）（1，1，2，2）（2，1，1，2）（2，1，2，1）（2，2，1，1，）（1，2，2，1）（1，2，1，2）（2，2，2）七个台阶（21种）（1，1，1，1，1，1，1）（1，1，1，1，1，2）（1，1，1，1，2，1）（1，1，1，2，1，1）（1，1，2，1，1，1）（1，2，1，1，1，1）（2，1，1，1，1，1）（1，1，1，2，2）（1，1，2，2，1）（1，2，2，1，1）（2，2，1，1，1）（1，2，1，1，2）（1，2，1，2，1）（1，2，2，1，1,）（2，1，1，1，2）（2，1，1，2，1）（2，1，2，1，1）（2，2，2，1）（2，2，1，2）（2，1，2，2）（1，2，2，2）……2.整理数据，发现规律这样写下去还是很麻烦，数字会越来越大，而且很容易出现遗漏或重复。
爬楼梯斐波那契数列通项
斐波那契数列在爬楼梯问题中应用的通项公式可以通过递归关系或矩阵快速幂等方法得到。
具体如下：
1.递归关系：在最简单的形式下，斐波那契数列由以下递推
关系定义：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)，其中n
是台阶数。
这个递归关系意味着到达当前台阶的方法数等于到达前
两个台阶的方法数之和。
2.备忘录策略优化：由于递归算法会进行大量重复计算，我们可以使
用备忘录方法来存储已计算的值，避免重复计算，从而提高效率。
3.矩阵快速幂：对于较大的n值，还可以使用矩阵快速幂来计算斐波
那契数，这在时间复杂度上比直接递归要高效得多。
4.闭合公式：斐波那契数列也有所谓的“闭合”公式（也称为Binet公
式），即F(n) = (φ^n - (-φ)^-n) / √5，其中φ = (1 + √5) / 2
是黄金分割比。
不过这个公式在数值计算时可能会遇到浮点数精度
问题。
5.动态规划：动态规划是解决此类问题的另一种高效方式。
通过自底
向上的方式逐步构建出到达每个台阶的方法数。
6.数据范围考虑：在实际编程中，还需要考虑数据范围和整型溢出的
问题。
对于大数情况，可能需要使用更大范围的数据类型或者采用
其他避免溢出的策略。
综上所述，斐波那契数列在爬楼梯问题中的应用非常广泛，其核心思想是将复杂问题分解为简单的子问题，并利用子问题的解来构建原问题的解。
这种思想在计算机科学和数学中有着广泛的应用。
关于爬楼梯问题的斐波那契数列最多只能跨3个台阶：要上15个台阶，⼀个⼜多少种⽅法？理解如下：到n台阶 ⾛法(⼀步到位，2步到位，3步到位...) 选择1 1 12 2；11 23 3；12,21；111 44 13,31,22,；112,211,121；1111 75 23,32；113,311,131,122,212,221;1112,1121,1211,2111；11111 13....所以f(n)=f(n-1)+f(n-2)+f(n-3)1// ⾮递归2 #include <iostream>3using namespace std;4int main()5 {6int f1=1,f2=2,f3=4,fn;7int n;8 cout<<"输⼊n=";9 cin>>n;10if(n <= 0) return -1;11else if(n==1) {cout<<f1; return0;} //很有必要复习下if else语句啊12else if(n==2) cout<<f2;13else if(n==3) cout<<f3;14else15 {16for(int i=4; i<=n;i++)17 {18 fn =f3+f2+f1;19 f1=f2;20 f2=f3;21 f3=fn;22 }23 cout<<fn;24 }25return0;26 }⽅法2：1// Note:Your choice is C++ IDE2 #include <iostream>3using namespace std;45long f1 = 1;6long f2 = 2;7long f3 = 4;8long fn = 0;9long fibonacci(int n)10 {11if(n<=0) return -1;12if(n==1) return1;13if(n==2) return2;14if(n==3) return4;1516for(int i = 4; i <= n; i++)17 {18 fn =f3+f2+f1;19 f1=f2;20 f2=f3;21 f3=fn;22 }23return fn;24 }25int main()26 {27int n;28 cout<<"输⼊n=";29 cin>>n;30 cout <<"f("<<n<<")="<<fibonacci(n)<<endl;31return0;32 }突然想起⼤⼀时⽼师说的兔⼦问题，f(n)=f(n-1)+f(n-2);⽼师好像也讲了⼀个爬楼梯，她说那个是最多可以跨2个台阶，所以计算和兔⼦是⼀样的表达式，只有两项相加，这个是最多3个台阶，所以3项相加；⼜想起⽼师说的那个什么梵塔问题，64个盘⼦，如果你放了63个，我放最后（最底的）⼀个就⼀步；63 有⼈放了62个，我放最后（最底的那个）⼀个也就是1步；1// Note:Your choice is C++ IDE2 #include <iostream>3using namespace std;456void hanoi(int n, char a, char b, char c)7 {8if(n==1) //⼀个盘⼦，直接从a到c9 cout<<a<<" to "<<c<<endl;10else11 {12 hanoi(n-1,a,c,b);//将n-1个盘⼦从a柱⼦(借助c)移动到b13 cout<<a<<" to "<<c<<endl;//最底的盘⼦从a到c14 hanoi(n-1,b,a,c);//n-1个盘⼦到了最终的位置15 }16 }17int main()18 {19char a='a',b='b',c='c';20int n;21 cout<<"输⼊n=";22 cin>>n;23 hanoi(n,a,b,c);24return0;25 }到这⾥，⼜想起⼈⼯智能课上的⽤宽度优先和⼴度优先解决寻路问题，现在印象中只有9宫格轮序变为给定模式那个。
在这个问题中，144>143，这个143是斐波那契数列的前n项和，我们是把144超出143的部分加到最后的一个数上去，如果加到其他数上，就有3条线段可以构成三角形了。
变式训练1 一只青蛙从宽5米的水田的一边要跳往另一边，它每次只能跳0.5米或1米，这只青蛙跳过水田共有多少种不同的方法?变式训练2 有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不同的取法?假定一对大兔子每一个月可以生一对小兔子，而小兔子出生后两个月就能有生殖能力。
问：从一对大兔子开始，如果所有兔子都不死，一年后能繁殖成多少对兔子？这就产生了斐波那契数列：如果一对兔子每月生一对兔子；一对新生兔，从第二个月起就开始生兔子；假定每对兔子都是一雌一雄，试问一对兔子，一年能繁殖成多少对兔子？先看前几个月的情况：第一个月有一对刚出生的兔子，即F(1)=1；第二个月，这对兔子长成成年兔，即F(2)=1；第三个月，这对成年兔生出一对小兔，共有两对兔子，即F(3)=2；第四个月，成年兔又生出一对小兔，原出生的兔子长成成年兔，共有三对兔子，即F(4)=3；第五个月，原成年兔又生出一对小兔，新成年兔也生出一对小兔，共有五对兔子，即F(5)=5；……以此类推，可得每个月的兔子对数，组成数列：1，1，2，3，5，8，13，21，34，55，89，144，…，这就是著名的斐波那契数列，其中的任一个数，都叫斐波那契数。
题中本质上有两类兔子：一类是能生殖的兔子，称为成年兔子；新生的兔子不能生殖；新生兔子一个月就长成成年兔子。
求的是成年兔子与新生兔子的总和。
每月新生兔对数等于上月成年兔对数。
每月成年兔对数等于上个月成年兔对数与新生兔对数之和。
最后得关系式：F(1)=F(2)=1；F(n)=F(n-1)+F(n-2)(n≥3)。
法国数学家比内(Binet)证明了通项公式为2、斐波那契数列的性质斐波那契数列有很多有趣的性质，归纳如下：性质1：相邻的斐波那契数之平方和(差)仍为斐波那契数。
【181】加法原理之上楼梯问题例1.有一楼梯共8级，如果规定每步只能跨上一级或两级，要登上8级台阶共有______种不同走法．第一级：只跨1步，有1种；第二级：（1、1），（2），有2种；第三级：（1、1、1），（1、2），（2、1），有1+2=3种；第四级：（1、1、1、1），（1、1、2），（2、1、1），（2、2），（1、2、1），有2+3=5种；第五级：…有3+5=8种；可以发现从第三次开始，后一种情况总是前两种情况的和；所以，第六级：有5+8=13种；第七级：有8+13=21种；第八级：有13+21=34种；答：要登上8级台阶共有34种不同走法．故答案为：34．列表如下：级数 1 2 3 4 5 6 7 8走法 1 2 3 5 8 13 21 34上面走法部分形成了一个有规律的数列。
这个数列叫做斐波那契数列。
如下：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...斐波那契数列的发明者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1240年，籍贯是比萨。
他被人称作“比萨的列昂纳多”。
1202年，他撰写了《珠算原理》一书。
他是第一个研究了印度和阿拉伯数学理论的欧洲人。
他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。
上面的上楼梯问题可改编为如下两个问题。
例2.有8根火柴，如果规定每步只能从中取1根或2根，最后把这8根全部取完共有______种不同的取法．这道题的答案和解法全都和例1是一样，仍然得34。
取一根火柴，相当于走了一级台阶，取2根火柴相当于走了二级台阶。
最后全部取完相当于走完了全部的8级台阶。
例3.有一楼梯共8级，如果规定每步只能跨上一级或两级或三级，要登上8级台阶共有______种不同走法．根据题意列表如下：级数 1 2 3 4 5 6 7 8走法 1 2 4 7 13 24 44 81这次加入了每次可以走三级，列举法找规律如下：如果总的级数是1，共1种走法；如果总的级数是2，共2种走法；如果总的级数是3，共4种走法；如果总的级数是4，共7种走法；（1+2+4）如果总的级数是5，共13种走法；（2+4+7）形成如下数列：1,2,4,7,13,24,44……可知从7开始每个数等于它前边三个数的和。
本文由我司收集整编，推荐下载，如有疑问，请与我司联系《剑指Offer》JavaScript实战——斐波那契数列+跳台阶问题2018/06/06 12 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n =39 解题方法方法一：普通递归，但是容易出现调用栈溢出问题，而且随着调用层数增加，速度会很慢。
最明显的就是，牛客网上递归版跑不通。
function Fibonacci(n) /* 方法一递归，但是容易出现调用栈溢出的情况*/ if(n =0) return 0; if(n===1) return 1; return Fibonacci(n-1)+Fibonacci(n-2);} 方法二：迭代，代码稍微多那么几行，但是速度快啊！ function Fibonacci(n) { /* 方法二迭代*/ let pre = 0, next = 1, fib = 0; if(n =0) return pre; if(n===1) return next; for(let i = 1;i i++){ fib = pre+next; pre = next; next = fib; return fib;} 方法三：优化普通递归版本，变成尾递归优化。
JS实现了尾调用优化。
牛客网上也能跑，但是相当于修改了接口参数，在实际开发时不建议随便修改接口参数。
function Fibonacci(n,pre =0, next =1) { //尾递归优化版本if(n =0) return pre; if(n===1) return next; return Fibonacci(n-1,next,pre+next);} 跳台阶问题牛客网练习题传送门 题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。
求该青蛙跳上一个n 级的台阶总共有多少种跳法。
理解：青蛙跳台阶问题其实就是斐波那契数列数列。
斐波那契数列的应用问题：
1．爬楼梯问题:
上楼梯的时候,如果允许每次跨一蹬或二蹬,那么对于楼梯数为1,2,3,4,…时的上楼方式数会有什么关系吗？
理论上说明:若登层阶梯有种方法,设第一步一层,则其余层的方法为种;若第一步二层,则其余层的方法为种;即登层阶梯的方法应有种.又因应登一层阶梯的方法只有一种;登两层的阶梯有两种方法(一步一层或一步两层),所以显然这是一个斐波那契数列的应用问题.
1,2,3,5,8,13,21,34,55,89……
2.座位问题:
师生集合坐一排,但老师们坐在一起总会聊些有关学校的无聊话题,因此规定老师彼此不可相邻而坐,若有不同数目的椅子,则有多少种可能的坐法(这同样是斐波那契数列的应用问题)
理论上说明:若只有一张椅子,可坐老师(T)或学生(S),共有两种坐法=>;若有二张椅子,可坐TS,ST,SS,共有三种坐法=>;若有n张椅子,可考虑n-1张椅子的情形下,最右边再加入一张椅子,如果最后坐的是学生则没有问题,有种坐法;如果最后坐的是老师,则最后两张坐的必定要是ST才符合条件,因此最后两张已经固定,相当于有种坐法,于是,斐波那契数列又再度出现.。
标数法与XXX台阶问题解法二：斐波那契数列递推公式，第十项为89，选D。
在标数法中，我们可以通过标记每个节点的情况数，来计算从起点到终点的最短路径的方案数。
这种方法适用于不能走“回头路”的情况。
举例来说，如果要从A到B，我们可以先走到C或者D，然后再从C或者D到达B，这样就可以通过标数法来计算从A到B的方案数。
最近几年的考题中，也出现了一些需要用到标数法的问题，例如从A到B的最短路径有多少种，或者在某些限制条件下，从一个点到另一个点有多少种走法等。
除了标数法，还有一种经典的问题叫做XXX台阶问题，也可以用斐波那契递推数列来解决。
例如在一个十阶楼梯上，XXX每次只能走一阶或者两阶，问走完此楼梯共有多少种方法。
我们可以通过斐波那契数列递推公式来计算，最终得到的结果为89.一年后可以繁殖的兔子总对数为斐波那契数列，选B。
假设刚出生的兔子，一个月后长成大兔子，两个月及以后的每个月可以生一对小兔子。
小兔子的来源只有一种：大兔子生出小兔子；大兔子的来源有两种：小兔子经过一个月变成大兔子、原来的大兔子依然是大兔子。
根据上述规律，可以得到每月的小兔子对数和大兔子对数，从而得到兔子总对数。
根据斐波那契数列的规律，从1号蜂房出发到达8号蜂房的不同走法数为21种，选C。
从1号出发，到达编号数分别为5、2、6、3、7、4、8的蜂房时，对应的方法数分别为1、2、3、5、8、13、21.到达7号的前一步有两类情况：从3号往右上过来或者从6号往右过来，所以到达7号的情况数等于到达3号的情况数加上到达6号的情况数。
从一个3×4的方格中的一个顶点A到顶点B的最短路线有15条。
可以使用组合数学或标数法来解决这个问题。
A。
1.2.3.5.8.13.21.34.55.89每次吃一颗或两颗，相当于每次可以走一步或两步，因此问题可以转化为在斐波那契数列中求第11项，即为89，选B。
例4：某人有7个球，其中3个红的、2个黄的、2个蓝的，他把这7个球随机地排成一行，那么红球在黄球两侧的排列方法有（。
走台阶问题
如：
总共100级台阶（任意级都行），小明每次可选择走1步、2步或者3步，问走完这100级台阶总共有多少种走法？
解析：
这个问题本质上是斐波那契数列，假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级,f(2)=2。
如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-
1级台阶，有f(n-1)种跳法，假如第一次条2级台阶，剩下n-
2级台阶，有f(n-2)种跳法。
这就表示f(n)=f(n-1)+f(n-
2)。
将上面的斐波那契数列代码稍微改一下就是本题的答案
f(n)=f(n-1)+f(n+2)
斐波那契数列
斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：F(n)=F(n-1)+F(n-2)
递推数列显然这是一个线性。
数学定义：
递归斐波纳契数列以如下被以的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）
由兔子生殖问题引出、生物 (计算科学)
特性：
这个数列从第3项开始，每一项都等于前两项之和。
特别指出：第1项是0，第2项是第一个1。
代码：
public class Test { static final int s = 100; //自定义的台阶数static int compute(int stair){ if ( stair <= 0){ return0; } if (stair == 1){ return1; } if (stair
== 2){ return2; } return compute(stair-1) + compute(stair-2);
//return 递归进行计算 --->递归思想进行数据计算处理
在斐波那契数列中后一项的值等于前两项的和 } public static void
main(String args[]) { System.out.println("共有" + compute(s) + "种走法"); } } return compute(stair-1) + compute(stair-2);
在return子句中调用调用compute函数
由斐波那契数列特性得到最后的值
分值拆分。
