剑指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)\odot$