美文网首页
斐波那楔数列

斐波那楔数列

作者: 打工这件小事 | 来源:发表于2018-11-11 23:01 被阅读0次

《剑指offer》面试题10(题目一):求斐波那楔数列的第n项。

题目:写一个函数,输入n,求斐波那楔数列的第n项。斐波那楔数列定义如下:
f(n)= 0; (n = 0);
f(n)= 1; (n = 1);
f(n)= f(n - 1)+ f(n - 2) ; (n > 1);

思路:很容易想到使用递归函数求解。但递归的过程中出现了重复计算,例如求f(4)= f(3)+ f(2);需要计算f(3)和f(2),而求f(3)又需要计算f(2)+ f(1);这个过程中f(2)被计算了2遍。出现了重复计算。为了避免重复计算,把已经得到的数列中间项保存起来,下次要计算时,发现如果已经计算过就不用重复计算了。

代码如下:

public int fibonacci(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        int num1 = 0;
        int num2 = 1;
        int temp = 0;
        for (int i = 2;i <= n;i++) {
            temp = num1 + num2;
            num1 = num2;
            num2 = temp;
        }
        return temp;
    }
}

相关文章

网友评论

      本文标题:斐波那楔数列

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