美文网首页
剑指offer_5_斐波那契数列

剑指offer_5_斐波那契数列

作者: 韩who | 来源:发表于2020-01-20 17:53 被阅读0次

    斐波那契数列

    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
    n<=39
    

    第一种

    最容易想到的方式:

    使用递归的方式,自底向上

    public class Solution {
        public int Fibonacci(int n) {
             
            if(n == 0){
                return 0;
            }
            if(n==1){
                return 1;
            }
            
            return  Fibonacci(n-1)+Fibonacci(n-2);
            
        }
    }
    

    优化思路:

    一:使用数组存储

    优化,我们使用数组来存,但是效果不明显

    public class Solution {
        
        int[] arr = new int[40];
        public int Fibonacci(int n) {
             
            if(n == 0){
                return 0;
            }
            if(n==1){
                return 1;
            }
             
            arr[n]  =  Fibonacci(n-1)+Fibonacci(n-2);
            return arr[n];
            
        }
    }
    

    优化思路二:

    非递归,使用循环方式,每次存储n-1以及n-的值,值存储需要用到的值,那么就可以进行计算

    考虑到每一次只存储n-1以及 n-2个数,所以可以只存储前一次计算的前两个值

    public class Solution {
     
        public int Fibonacci(int n) {      
            if(n == 0){
                return 0;
            }
            if(n==1){
                return 1;
            }
            
            int a=0,b=1,c=0;
            //a 代表n-2的值,b 代表n-1的值
            for(int i = 2 ; i<=n ;i++){
                c = a+b;
                a = b;
                b = c;           
            }     
            return c;
            
        }
    }
    

    相关文章

      网友评论

          本文标题:剑指offer_5_斐波那契数列

          本文链接:https://www.haomeiwen.com/subject/gdajzctx.html