写在前面： 我是「扬帆向海」，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。
技术是开源的、知识是共享的。
这博客是对自己学习的一点点总结及记录，如果您对 Java、算法 感兴趣，可以关注我的动态，我们一起学习。
用知识改变命运，让我们的家人过上更好的生活。
相关文章
一、斐波拉契数列介绍
斐波那契数列（Fibonacci sequence），又称黄金分割数列。斐波那契数列源自于兔子繁殖问题，是数学家列昂纳多·斐波那契引入的，故又称为“兔子数列”，指的是这样一个数列：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]。
兔子繁殖问题代码实现
import java.util.Scanner;
public class RabbitQuestion {
public static void main(String[] args) {
while (true) {
System.out.print("输入你想知道兔子数量的月份：");
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//计算第n月兔子的数量
int s = computer(n);
System.out.println("第" + n + "个月兔子的数量为:" + s + "对");
}
}
/**
* 计算第n月兔子的数量
*
* @param n 月份
* @return 返回兔子的数量
*/
private static int computer(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return computer(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.利用循环的方式
public class TestFib {
public static void main(String[] args) {
// 声明三个变量
int a = 1;
int b = 1;
int c = 0;
System.out.print("斐波拉契数列的前10项为： " + a + "\t" + b + "\t");
// 从第三项开始，每个数字都都等于前面两个数字之和
for (int i = 3; i <= 10; i++) {
c = a + b;
a = b;
b = c;
System.out.print(c + "\t");
}
}
}
代码执行结果：
斐波拉契数列的前10项为： 1 1 2 3 5 8 13 21 34 55
2.利用递归的方式
public class TestFib1 {
public static void main(String[] args) {
for (int i = 1; i <= 10; i++) {
// 求斐波拉契数列第i项
int num = fib(i);
System.out.print(num + "\t");
}
}
/**
* 求斐波拉契数列第i项
*
* @param i 第几项
* @return 返回第i项的值
*/
private static int fib(int i) {
if (i == 1 || i == 2) {
return 1;
} else {
// 利用递归循环调用函数
return fib(i - 1) + fib(i - 2);
}
}
}
在此不再展示代码执行结果，执行结果和第一种循环的方式一样。
五、跳台阶问题
假设一个楼梯的台阶一共有 i 级，如果一次可以跳1级，也可以跳2级，计算总共有多少种跳法。
public class JumpStep {
public static void main(String[] args) {
System.out.print("输入台阶数：");
int i = new Scanner(System.in).nextInt();
System.out.println("总共的跳法有：" + getFib(i) + "种");
}
/**
* 计算跳台阶的种数
*
* @param i 台阶的数量
* @return 返回一共多少种
*/
private static int getFib(int i) {
if (i < 0) {
return -1;
}
if (i <= 2) {
return i;
}
// 递归
return getFib(i - 1) + getFib(i - 2);
}
}
代码执行结果：
输入台阶数：20
总共的跳法有：10946种
输入台阶数：0
总共的跳法有：0种
输入台阶数：-8
总共的跳法有：-1种
上一篇 经典算法（5）杨辉三角
下一篇 算法（7）统计一个字符串中每个字符出现的次数