leetcode/
fibonacci_number_offer.rs

1//! # 剑指 Offer 10- I. 斐波那契数列
2//!
3//! 难度 简单
4//!
5//! 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
6//!
7//! ```text
8//! F(0) = 0,   F(1) = 1
9//! F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
10//! ```
11//!
12//! 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
13//!
14//! 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
15//!
16//!
17//! ## 示例 1：
18//!
19//! ```text
20//! 输入：n = 2
21//! 输出：1
22//! ```
23//!
24//! ## 示例 2：
25//!
26//! ```text
27//! 输入：n = 5
28//! 输出：5
29//! ```
30//!
31//!
32//! ## 提示：
33//!
34//! * `0 <= n <= 100`
35//!
36//! See [leetcode](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/)
37
38pub struct Solution;
39
40impl Solution {
41    pub fn fib(n: i32) -> i32 {
42        assert!(n >= 0 && n <= 100);
43        let r = (0..n).fold((0u128, 1), |(pp, p), _| (p, pp + p)).0 % 1_000_000_007;
44        r as i32
45    }
46}
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51    const P: i32 = 1_000_000_007;
52
53    fn fib(n: i32) -> i32 {
54        match n {
55            0 | 1 => n,
56            n => (fib(n - 1) % P + fib(n - 2) % P) % P,
57        }
58    }
59
60    #[test]
61    fn test() {
62        assert_eq!(fib(0), Solution::fib(0));
63        assert_eq!(fib(1), Solution::fib(1));
64        assert_eq!(fib(2), Solution::fib(2));
65        assert_eq!(fib(3), Solution::fib(3));
66        assert_eq!(fib(21), Solution::fib(21));
67        // assert_eq!(fib(44), Solution::fib(44));
68        // assert_eq!(701408733, fib(44));
69        assert_eq!(701408733, Solution::fib(44));
70        assert_eq!(583861472, Solution::fib(55));
71        assert_eq!(687995182, Solution::fib(100));
72    }
73}
leetcode/fibonacci_number_offer.rs

leetcode/
fibonacci_number_offer.rs
