題目
寫一個函數(shù)氓涣，輸入 n 蛹找，求斐波那契（Fibonacci）數(shù)列的第 n 項。斐波那契數(shù)列的定義如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數(shù)列由 0 和 1 開始蚊锹，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出秒咨。
答案需要取模 1e9+7（1000000007），如計算初始結(jié)果為：1000000008计呈，請返回 1老客。
示例 1：
輸入：n = 2
輸出：1
示例 2：
輸入：n = 5
輸出：5
提示：
0 <= n <= 100
注意：本題與主站 509 題相同：https://leetcode-cn.com/problems/fibonacci-number/
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有僚饭。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處胧砰。
解法
循環(huán)實現(xiàn)斐波那契鳍鸵。
class Solution:
def fib(self, n: int) -> int:
if n == 0 :
return 0
if n == 1 :
return 1
n1 = 0
n2 = 1
while n - 2 >= 0:
# 加上的話可以在中間就限制數(shù)的大小
if n1 >= 1e9+7 and n2 >= 1e9+7 :
n1 = int(n1 % (1e9+7))
n2 = int(n2 % (1e9+7))
t = n1 + n2
n1 = n2
n2 = t
n -= 1
return int(n2 % (1e9+7))
總結(jié)
評論區(qū)對邊取余邊算做了證明：
image.png
評論區(qū)對迭代過程做了化簡：
image.png
評論區(qū)學到了一個很有意思的東西：
image.png
