斐波那契数列、走台阶问题.docx

《斐波那契数列、走台阶问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、走台阶问题如：总共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

2、)+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。代码：publicclassTest{staticfinalints=100;//

3、自定义的台阶数staticintcompute(intstair){if(stair<=0){return0;}if(stair==1){return1;}if(stair==2){return2;}returncompute(stair-1)+compute(stair-2);//return递归进行计算--->递归思想进行数据计算处理在斐波那契数列中后一项的值等于前两项的和}publicstaticvoidmain(Stringargs[]){System.out.println("共有"+compute(s)+"种走法");}}returncompute(stair-1)+co

4、mpute(stair-2);在return子句中调用调用compute函数由斐波那契数列特性得到最后的值分值拆分