leetcode/
fibonacci_number.rs

1//! # 509. 斐波那契数
2//!
3//! 难度 简单
4//!
5//! 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
6//!
7//! ```text
8//! F(0) = 0,   F(1) = 1
9//! F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
10//! ```
11//!
12//! 给定 N，计算 F(N)。
13//!
14//!
15//! ## 示例 1：
16//!
17//! ```text
18//! 输入：2
19//! 输出：1
20//! 解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
21//! ```
22//!
23//! ## 示例 2：
24//!
25//! ```text
26//! 输入：3
27//! 输出：2
28//! 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
29//! ```
30//!
31//! ## 示例 3：
32//!
33//! ```text
34//! 输入：4
35//! 输出：3
36//! 解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
37//! ```
38//!
39//! ## 提示：
40//!
41//! * `0 ≤ N ≤ 30`
42//!
43//! See [leetcode](https://leetcode-cn.com/problems/fibonacci-number/)
44
45pub struct Solution;
46
47impl Solution {
48    pub fn fib(n: i32) -> i32 {
49        assert!(n >= 0 && n <= 30);
50        let r = (0..n).fold((0u64, 1), |(pp, p), _| (p, pp + p)).0;
51        r as i32
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    fn fib(n: i32) -> i32 {
60        match n {
61            0 | 1 => n,
62            n => fib(n - 1) + fib(n - 2),
63        }
64    }
65
66    #[test]
67    fn test() {
68        assert_eq!(fib(0), Solution::fib(0));
69        assert_eq!(fib(1), Solution::fib(1));
70        assert_eq!(fib(2), Solution::fib(2));
71        assert_eq!(fib(3), Solution::fib(3));
72        assert_eq!(fib(21), Solution::fib(21));
73    }
74}
leetcode/fibonacci_number.rs

leetcode/
fibonacci_number.rs
