程序员社区

剑指Offer系列(java版,详细解析)10.斐波那契数列

题目一

题目描述

剑指 Offer 10- I. 斐波那契数列

难度简单108

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

提示:

  • 0 <= n <= 100

测试用例

  • 功能测试(如输入3、5、10等)
  • 边界值测试(如输入0、1、2)
  • 性能测试(输入较大的数值,如40、50、100等)

题目考点

  • 考察应聘者对递归、循环的理解及编码能力
  • 考察队时间复杂度的分析能力
  • 如果结合实际问题,可能还考察数学建模能力

解题思路

循环求余法:

大数越界: 随着 n 增大, f(n) 会超过 Int32 甚至 Int64 的取值范围,导致最终的返回值错误。

  • 求余运算规则: 设正整数 x, y, p ,求余符号为 ⊙ \odot ,则有 ( x + y ) ⊙ p = ( x ⊙ p + y ⊙ p ) ⊙ p (x + y) \odot p = (x \odot p + y \odot p) \odot p (x+y)p=(xp+yp)p
  • 解析: 根据以上规则,可推出 f ( n ) ⊙ p = [ f ( n − 1 ) ⊙ p + f ( n − 2 ) ⊙ p ] ⊙ p f(n) \odot p = [f(n-1) \odot p + f(n-2) \odot p] \odot p f(n)p=[f(n1)p+f(n2)p]p ,从而可以在循环过程中每次计算 s u m = ( a + b ) ⊙ 1000000007 sum = (a + b) \odot 1000000007 sum=(a+b)1000000007,此操作与最终返回前取余等价。

参考解题


public class Solution1 {
   
    public int Fibonacci(int n) {
   
        if (n < 2) {
   
            return n;
        }
        int pre1 = 0;
        int pre2 = 1;
        int fib = 0;
        for (int i = 2; i <=n; i++) {
   
            fib = pre1 + pre2;
            pre1 = pre2;
            pre2 = fib;
        }
        return fib;
    }

}

题目二

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

题目考点

考察数学建模能力,发现实质是斐波那契数列。

解题思路

与斐波那契数列相同,但是还是需要分析一下:

先分析最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳法,分为每次跳1级,和一次跳两级。

再讨论一般情况,我们把n级台阶时的跳法看成n的函数,记为f(n)。当 n>2 时,第一次跳的时候就有两种不同的选择:一是第一次跳1级,此时跳法数目等于后面剩下的 n-1 级台阶的跳法数目,即为 f(n-1) ,二是第一次跳2级,此时跳法数目等于后面剩下的 n-2 级台阶的跳法数目,即为 f(n-2) 。因此,n级台阶的不同跳法的总数f(n) = f(n-1) + f(n-2)。

我们马上就可以看出这就是斐波那契数列了。

自己解题

/** * 青蛙台阶问题 */
public class FrogSolution {
   

    /** * 采用斐波那契解法 * @param target * @return */
    public int JumpFloor(int target) {
   
        if (target < 3) {
   
            return target;
        }
        int pre1 = 1;
        int pre2 = 2;
        int fib = 0;
        for (int i = 3; i <= target; i++) {
   
            fib = pre1 + pre2;
            pre1 = pre2;
            pre2 = fib;
        }
        return fib;
    }
}

补充

通常基于递归实现的代码比基于循环实现的代码要简洁很多,更加容易实现。如果面试官没有特殊要求,则应聘者可以采用递归的方法编程,但是我们还是应该以时间复杂度为首要考虑。

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 剑指Offer系列(java版,详细解析)10.斐波那契数列

一个分享Java & Python知识的社区