1

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

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中的一个问题：“一个孩子正在跑上n步的楼梯，一次可以跳 1 步、2 步或 3 步。实现一种方法来计算孩子可以用多少种可能的方式跑上楼梯。”</p>

4

4 回答 4

9

根据tribonacci 序列的定义，我发现您可以用更简洁的方式编写它，如下所示：

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.

于 2017-02-28T13:34:38.587 回答
9

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

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

相反，失败指向一系列动作。序列的表达方式有很多种：递归、迭代、...

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

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

当然，我发现@ljedrz 的解决方案在这个特定的例子中更加优雅。

于 2017-02-28T13:46:29.763 回答
3

我建议避免在 Rust 中递归。最好使用迭代器：

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));
}

操场

于 2017-03-01T06:10:04.523 回答
1

尽管@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)每次都重新计算，而是将每个值缓存在一个数组中。因此，这应该以线性时间而不是指数时间运行。我还切换到 au128以便能够返回更大输入的解决方案。

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

于 2021-06-04T19:09:23.593 回答