• 00007.斐波那契数列
  • 发布于 1个月前
  • 61 热度
    0 评论

题目描述


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

n<=39。

解题思路:

递归定义:直接或间接的调用自己本身。

思路:0 1 1 2 3 

代码:

public int Fibonacci(int n) {
        //终止条件 0 与 1
        if(n <= 1) {
            return n;
        } 
        //递归的调用自己本身
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

优点:代码简洁,思路易懂。

缺点:重复计算,当n大于某一值得时候就会发生StackOverFollow异常。因为递归本质还是栈得出入。

改进:减少重复得地方。每次计算得时候重复使用得仅仅是当前值得前一个以及当前值得前一个得前一个数字。

做法:缓存当前数字得前一个以及前前一个数组即可。

代码:

public int Fibonacci(int n) {
        if(n <= 1) {
            return n;
        }
        //运行时间:19ms   占用内存:9292k
        //0 1 1 2 3 
        //缓存结果作为输出
        int result = 0;
        //缓存前一个得前一个数字得大小
        int prePreNum = 0;
        //缓存前一个数字
        int preNum = 1;
        //第n个数字当然也要计算并且从第三个数字开始
        for(int i = 2; i <= n; i++) {
            result = prePreNum + preNum;
            prePreNum = preNum;
            preNum = result;
        }
        return result;
    }
将结果用变量缓存起来,每次只缓存需要的数字,从而减少不必要得加法运算。



用户评论