Java面试算法（1）——斐波那契数列（含例题）

1、什么是斐波那契数列？

菲波纳契数列又称“菲波纳契神奇数列”，是由13世纪的意大利数学家菲波纳契提出的，当时是和兔子的繁殖问题有关的，它是一个很重要的数学模型。这个问题是：有小兔一对，若第二个月它们成年，第三个月生下小兔一对，以后每月生产一对小兔，而所生小兔亦在第二个月成年，第三个月生产另一对小兔，以后亦每月生产小兔一对，假定每产一对小兔必为一雌一雄，且均无死亡，试问一年后共有小兔几对？

简单来说只要一个数列满足上述公式关系，那我们就称这个数列为斐波那契数列。

整体代码实现：

package com;
 
import java.util.Arrays;
 
//1.递归方法
public class test2 {
    //1.用递归方法
    public static void main(String[] args) {
        for (int counter = 1; counter <= 10; counter++){
            System.out.printf("Fibonacci of %d is: %d\n", counter, fibonacci(counter));
        }
    }
    public static long fibonacci(long number) {
        if ((number == 0) || (number == 1))
            return number;
        else
            return fibonacci(number - 1) + fibonacci(number - 2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、斐波那契数列常见的面试题（借鉴于剑指Offer中的面试题）

（1）最常见的兔子问题：

这个问题是：有小兔一对，若第二个月它们成年，第三个月生下小兔一对，以后每月生产一对小兔，而所生小兔亦在第二个月成年，第三个月生产另一对小兔，以后亦每月生产小兔一对，假定每产一对小兔必为一雌一雄，且均无死亡，试问一年后共有小兔几对？

这个我就不做分析了！

（2）矩形覆盖问题：

（1）问题分析：

因此借助于上图的简单分析不难得出其实矩形的填充方法是符合斐波那契数列的！

补充一句：在这里其实主要是利用了反推的思想，简单来说就是满足了前面已有形式的问题我们不用再去思考了，然后加上新发现的即可解决该问题。

（2）代码分析：

public int rectCover(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int result = 0;
    for (int i = 3; i <= n; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12

（3）跳台阶问题：

（1）问题分析：

在这里我们接着利用反推的思想，我在这里我主要是以三号台阶为例。

我们可以反着想，假设现在青蛙在第三台阶，其他条件不变，但是跳的方向发生改变，他往下跳，那么它只能调到第二个台阶或者调到第一个台阶。对不对，这时候我们就知道了，因此，当青蛙想跳到第三台阶，那么他只有两种可能性，一个是在第一台阶，一个是在第二台阶。因此青蛙到达第一台阶的方法有一种，青蛙到达第二台阶的方法有2中。可得：F（3） = F（2）+F（1）。

（2）代码分析：

public int JumpFloor(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int result = 0;
    for (int i = 2; i < n; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12

（4）跳台阶问题升级版——变态跳台阶问题：

（1）问题分析
其实对于这个跳台阶的问题，如果上一个你能看懂我说的，这个其实更加简单。
当青蛙在第n阶台阶的时候，他可以反向调到第n-1阶台阶，第n-2阶台阶，…,因此我们就可以得出：

（2）代码实现：

public int JumpFloorII(int target) {
    return (int) Math.pow(2, target - 1);
}
1
2
3