斐波那契数列

1. import java.util.*;
   
2. import java.io.*;
   
3. 
   
4. public class Fibonacci
   
5. {
   
6. public static void main(String[] args) throws IOException
   
7. {
   
8. Scanner in=new Scanner(System.in);
   
9. long num = Fib(in.nextInt());
   
10. System.out.println(num);
    
11. }
    
12. 
    
13. public static long Fib(int n){
    
14. if(n<3)
    
15. return 1;
    
16. else
    
17. return Fib(n-1)+Fib(n-2);
    
18. }
    
19. }
    

复制代码

上述代码，是关于斐波那契数列计算问题的，如果输入的数较大的话，计算速度会非常慢，像输入60，就会停滞在控制台不懂。该代码如何优化？

1. import java.util.Scanner;
   
2. 
   
3. 
   
4. public class test {
   
5.         public static void main(String[] args) {
   
6.                 int temp = 0;
   
7.                 int a = 0, b = 1;
   
8.                 Scanner scanner = new Scanner(System.in);
   
9.                 int num = scanner.nextInt();
   
10.                 if (num == 0) {
    
11.                         System.out.println(0);
    
12.                 }
    
13.                 for (int i = 2; i < num ; i++) {
    
14.                         temp = a;
    
15.                         a = b;
    
16.                         b += temp;
    
17.                 }
    
18.                 System.out.println(b);
    
19.         }
    
20. }
    

复制代码

递归的方法实在太消耗系统资源了。时间开销和空间开销都好大。最好的解决办法是不用递归。

可惜还在北京传智上基础班，还没有讲到这块的内容，冯佳老师今天上课的时候，也提到了这个问题，但是还没有学习，只能过段时间再提这个了。