10:斐波那契数列

发表于 | 分类于

题目10：斐波那契数列

斐波那契数，亦称之为斐波那契数列（意大利语： Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*），用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加

思路

一. 基于递归

当追求代码的简洁性，且递归的次数没有足够大时，使用递归

斐波那契数列

二. 基于循环

当追求代码的时间效率，那么使用循环会更好。基于递归的斐波那契数列在每次计算的时候都存在重复的计算，其时间复杂度会随着n的增加以指数的方式递增。并且，使用递归可能会引起调用栈溢出的问题。

重复计算

用有限变量避免递归的重复计算

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class _10 {
    public static long fibonacci1(int n) {
        if(n <= 0)
            return 0;
        if(n == 1)
            return 1;
        return fibonacci1(n - 1) + fibonacci1(n - 2);
    }
    
    public static long fibonacci2(int n) {
        if (n <= 0) {
            return 0;
        }     
        if (n == 1 ) {// 输入1的时候返回1
            return 1;
        }
        long prePre = 0;//初始化为第一个fibonacci的值，记录第n-2个的Fibonacci数的值      
        long pre = 1;//初始化为第二个fibonacci的值， 记录第n-1个的Fibonacci数的值
        long current = 0; // 记录第n个的Fibonacci数的值      
        for (int i = 2; i <= n ; i++) {    
            current = prePre + pre;
            // 更新记录的结果，prePre原先记录第i-2个Fibonacci数的值
            // 现在记录第i-1个Fibonacci数的值
            prePre = pre;
            // 更新记录的结果，pre原先记录第i-1个Fibonacci数的值
            // 现在记录第i个Fibonacci数的值
            pre = current;
        }
        return current;
    }
    
    public static void main(String[] args) {
    	System.out.println("基于递归： ");
        System.out.println("fibonacci(0)="+fibonacci1(0));
        System.out.println("fibonacci(1)="+fibonacci1(1));
        System.out.println("fibonacci(2)="+fibonacci1(2));
        System.out.println("fibonacci(3)="+fibonacci1(3));
        System.out.println("fibonacci(4)="+fibonacci1(4));
        System.out.println("fibonacci(5)="+fibonacci1(5));
        System.out.println("fibonacci(6)="+fibonacci1(6));
        System.out.println("fibonacci(7)="+fibonacci1(7));
        System.out.println("基于循环： ");
        System.out.println("fibonacci(0)="+fibonacci2(0));
        System.out.println("fibonacci(1)="+fibonacci2(1));
        System.out.println("fibonacci(2)="+fibonacci2(2));
        System.out.println("fibonacci(3)="+fibonacci2(3));
        System.out.println("fibonacci(4)="+fibonacci2(4));
        System.out.println("fibonacci(5)="+fibonacci2(5));
        System.out.println("fibonacci(6)="+fibonacci2(6));
        System.out.println("fibonacci(7)="+fibonacci2(7));
    }
}

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
基于递归： 
fibonacci(0)=0
fibonacci(1)=1
fibonacci(2)=1
fibonacci(3)=2
fibonacci(4)=3
fibonacci(5)=5
fibonacci(6)=8
fibonacci(7)=13
基于循环： 
fibonacci(0)=0
fibonacci(1)=1
fibonacci(2)=1
fibonacci(3)=2
fibonacci(4)=3
fibonacci(5)=5
fibonacci(6)=8
fibonacci(7)=13
> >