509. 斐波那契数

Posted on | In
Words count in article: 290 | Reading time ≈ 1

题目

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0,   F(1) = 1
F(N) = F(N - 1)+ F(N - 2), 其中 N > 1.

给定 n ，请计算 F(n) 。

示例 1:

1
2
3
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例2：

1
2
3
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例3：

1
2
3
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示：

  • 0 ≤ N ≤ 30

解法

解法一：

迭代法

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int fib(int N) {
		if (0 == N || 1 == N) {
			return N;
		}
		
		int f0 = 0;
		int f1 = 1;
		
		int result = 0;
		while (N > 1) {
			result = f0 + f1;
			f0 = f1;
			f1 = result;
			N--;
		}
		return result;
    }

解法二：

递归

Java

1
2
3
4
5
6
public int fib(int N) {
        if (N <= 1) {
            return N;
        }
        return fib(N-1) + fib(N-2);
    }

解法三：

公式法

使用黄金分割比：φ=1+52≈1.6180339887….\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887….φ=21+5
≈1.6180339887….，Binet 公式 ：

Java

1
2
3
4
public int fib(int N) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int)Math.round(Math.pow(goldenRatio, N)/ Math.sqrt(5));
    }
0%