Rust 中 tribonacci 序列的惯用实现

Question

我是 Rust 的新手，但作为 Haskell 的粉丝，我非常欣赏 match 在 Rust 中的工作方式。现在我面临着我确实需要 fall-through 的罕见情况——从某种意义上说，我希望执行几个重叠的所有匹配情况。这有效：

fn options(stairs: i32) -> i32 {
    if stairs == 0 {
        return 1;
    }
    let mut count: i32 = 0;
    if stairs >= 1 {
        count += options(stairs - 1);
    }
    if stairs >= 2 {
        count += options(stairs - 2);
    }
    if stairs >= 3 {
        count += options(stairs - 3);
    }
    count
}

我的问题是这在 Rust 中是惯用的还是有更好的方法。

上下文是 Cracking the Coding Interview 中的一个问题：“A child 正在运行与 n 一起上楼梯 步，一次可以跳 1 步、2 步或 3 步。实现一种方法来计算 child 可以运行上楼梯的可能方式。”

Answer 1

基于definition of the tribonacci sequence我发现你可以像这样写得更简洁：

fn options(stairs: i32) -> i32 {
    match stairs {
        0 => 0,
        1 => 1,
        2 => 1,
        3 => 2,
        _ => options(stairs - 1) + options(stairs - 2) + options(stairs - 3)
    }
}

我还建议将函数定义更改为仅接受正整数，例如u32.

Answer 2

为了回答一般性问题，我认为 match 和 fallthrough 在某种程度上是对立的。

match用于根据不同的模式执行不同的动作。大多数时候，通过模式匹配提取的值与 fallthrough 提取的值非常不同，没有意义。

fallthrough 相反，指向一个序列的操作。序列的表达方式有很多种：递归、迭代、...

例如，在您的情况下，可以使用循环：

for i in 1..4 {
    if stairs >= i {
        count += options(stairs - i);
    }
}

当然，我发现@ljedrz 的解决方案在此特定实例中更为优雅。

Answer 3

我建议 avoid recursion in Rust. It is better to use iterators:

struct Trib(usize, usize, usize);

impl Default for Trib {
    fn default() -> Trib {
        Trib(1, 0, 0)
    }
}

impl Iterator for Trib {
    type Item = usize;
    fn next(&mut self) -> Option<usize> {
        let &mut Trib(a, b, c) = self;
        let d = a + b + c;
        *self = Trib(b, c, d);
        Some(d)
    }
}

fn options(stairs: usize) -> usize {
    Trib::default().take(stairs + 1).last().unwrap()
}

fn main() {
    for (i, v) in Trib::default().enumerate().take(10) {
        println!("i={}, t={}", i, v);
    }

    println!("{}", options(0));
    println!("{}", options(1));
    println!("{}", options(3));
    println!("{}", options(7));
}

Playground

Answer 4

虽然@ljedrz 建议对同一策略进行更优雅的重写，但我觉得您的代码非常地道。

由于这是一个面试问题，值得一提的是，这两种解决方案都不会被视为一个惊人的答案，因为这两种解决方案都需要花费指数级的时间。

如果我试图破解编码面试，我可能会写以下内容：

fn options(stairs: usize) -> u128 {
    let mut o = vec![1, 1, 2, 4];
    for _ in 3..stairs {
        o.push(o[o.len() - 1] + o[o.len() - 2] + o[o.len() - 3]);
    }
    o[stairs]
}

我们不是每次都重新计算 options(n)，而是将每个值缓存在一个数组中。因此，这应该运行在线性时间而不是指数时间。我还切换到 u128 以便能够 return 更大输入的解决方案。

请记住，这不是最有效的解决方案，因为它使用线性 space。您可以通过仅跟踪数组的最后三个元素来使用常量 space 。我选择它作为简洁性、可读性和效率之间的折衷。

Rust 中 tribonacci 序列的惯用实现

Idiomatic implementation of the tribonacci sequence in Rust

idioms

fibonacci

fall-through

rust