目录一、斐波拉契数列介绍二、斐波拉契数列的算法思想三、兔子繁殖问题四、斐波拉契数列代码实现1.利用循环的方式2.利用递归的方式五、跳台阶问题
一、斐波拉契数列介绍
斐波那契数列（Fibonaccisequence），又称黄金分割数列。斐波那契数列源自于兔子繁殖问题，是数学家列昂纳多·斐波那契引入的，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
1202年，他撰写了《珠算原理》一书。在这本书中，提出下面一个难题“一对兔子每个月能生出一对小兔子来，兔子在出生两个月后，就有繁殖能力，如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？”由此产生了斐波那契数列。
相关文章经典算法（5）杨辉三角
二、斐波拉契数列的算法思想
数列中的每1项称为“斐波那契数”，斐波那契数的前两项都是1，从第3项开始，每1项都等于前2项之和。
三、兔子繁殖问题
算法分析：
第一个月兔子的数量是1对第二个月兔子的数量是1对第三个月兔子的数量是2对第四个月兔子的数量是3对第五个月兔子的数量是5对第六个月兔子的数量是8对第七个月兔子的数量是13对第八个月兔子的数量是21对…每个月兔子数量的规律为数列1,1,2,3,5,8,13,21……
在本问题中，从第三个月开始，第n个月的兔子数量的对数为前面两个月之和，由此得出：a[n]=a[n-1]+a[n-2]。
兔子繁殖问题代码实现
importjava.util.Scanner;publicclassRabbitQuestion{publicstaticvoidmain(String[]args){while(true){System.out.print("输入你想知道兔子数量的月份：");Scannerscanner=newScanner(System.in);intn=scanner.nextInt();//计算第n月兔子的数量ints=computer(n);System.out.println("第"+n+"个月兔子的数量为:"+s+"对");}}/***计算第n月兔子的数量**@paramn月份*@return返回兔子的数量*/privatestaticintcomputer(intn){if(n==1||n==2){return1;}else{returncomputer(n-1)+computer(n-2);}}}
代码执行结果：
输入你想知道兔子数量的月份：1第1个月兔子的数量为:1对输入你想知道兔子数量的月份：2第2个月兔子的数量为:1对输入你想知道兔子数量的月份：3第3个月兔子的数量为:2对输入你想知道兔子数量的月份：4第4个月兔子的数量为:3对输入你想知道兔子数量的月份：5第5个月兔子的数量为:5对输入你想知道兔子数量的月份：6第6个月兔子的数量为:8对输入你想知道兔子数量的月份：7第7个月兔子的数量为:13对输入你想知道兔子数量的月份：8第8个月兔子的数量为:21对四、斐波拉契数列代码实现1.利用循环的方式publicclassTestFib{publicstaticvoidmain(String[]args){//声明三个变量inta=1;intb=1;intc=0;System.out.print("斐波拉契数列的前10项为："+a+"\t"+b+"\t");//从第三项开始，每个数字都都等于前面两个数字之和for(inti=3;i<=10;i++){c=a+b;a=b;b=c;System.out.print(c+"\t");}}}
代码执行结果：
斐波拉契数列的前10项为：112358132134552.利用递归的方式publicclassTestFib1{publicstaticvoidmain(String[]args){for(inti=1;i<=10;i++){//求斐波拉契数列第i项intnum=fib(i);System.out.print(num+"\t");}}/***求斐波拉契数列第i项**@parami第几项*@return返回第i项的值*/privatestaticintfib(inti){if(i==1||i==2){return1;}else{//利用递归循环调用函数returnfib(i-1)+fib(i-2);}}}
在此不再展示代码执行结果，执行结果和第一种循环的方式一样。
五、跳台阶问题
假设一个楼梯的台阶一共有i级，如果一次可以跳1级，也可以跳2级，计算总共有多少种跳法。
publicclassJumpStep{publicstaticvoidmain(String[]args){System.out.print("输入台阶数：");inti=newScanner(System.in).nextInt();System.out.println("总共的跳法有："+getFib(i)+"种");}/***计算跳台阶的种数**@parami台阶的数量*@return返回一共多少种*/privatestaticintgetFib(inti){if(i<0){return-1;}if(i<=2){returni;}//递归returngetFib(i-1)+getFib(i-2);}}
代码执行结果：
输入台阶数：20总共的跳法有：10946种输入台阶数：0总共的跳法有：0种输入台阶数：-8总共的跳法有：-1种
上一篇经典算法（5）杨辉三角下一篇算法（7）统计一个字符串中每个字符出现的次数
