使用Rust做斐波那契数列

用了Rust优化意识更强烈了，总想把代码优化到极致

1、递归版本

fn fb(i: i32) -> i32 {
    if i <= 0 {
        panic!("索引要大于0");
    }
    return if i <= 2 { 1 } else { fb(i - 1) + fb(i - 2) };
}

2、非递归版本

fn fb_use_loop(mut n: i32) -> i32 {
    if n <= 0 {
        panic!("索引要大于0");
    }
    let mut p1 = 1;
    let mut p2 = 0;
    let mut now = 1;
    while n > 0 {
        now = p1 + p2;
        p1 = p2;
        p2 = now;
        n -= 1;
    }
    return now;
}

编译器会自动检查传入的值，如果是负数就会报错。严格意义上代码还有一个小问题，那就是fb(0)会是1，斐波那契数列理论上是不存在0的，但是不影响其它的结果都是正确的。此外还有整数溢出错误，这个和之前的都存在，但是斐波那契增长还是挺快的，要避免这个问题似乎也没有什么意义，总有更大的数让你溢出。如果是普通的题目，u32(4294967295)应该够了。rust的这个 return if else语法糖真的很方便。

fn fb(i: u32) -> u32 {
    return if i <= 2 { 1 } else { fb(i - 1) + fb(i - 2) };
}
fn fb_use_loop(mut n: u32) -> u32 {
    let mut p1 = 1;
    let mut p2 = 0;
    let mut now = 1;
    while n > 0 {
        now = p1 + p2;
        p1 = p2;
        p2 = now;
        n -= 1;
    }
    return now;
}

4、急速体验

通过使用一个vector来对已经计算出来的斐波那契数列进行缓存。

struct Fb {
    cache: Vec<usize>,
}
impl Fb {
    fn new() -> Fb {
        return Fb {
            cache: vec![0, 1, 1],
        };
    }
    fn at(&mut self, n: usize) -> usize {
        return match self.cache.get(n) {
            Some(num) => *num,
            None => {
                // None时n总是大于2的，因为new中已经初始化了cache
                let v = self.at(n - 1) + self.at(n - 2);
                self.cache.push(v);
                v
            }
        };
    }
}

使用时只需要：

    let mut fb_cached = Fb::new();
    println!("{}", fb_cached.at(12));

版权声明

本文章由作者“衡于墨”创作，转载请注明出处，未经允许禁止用于商业用途

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

发布时间：2020年03月23日 19:57:01

评论区#

还没有评论哦，期待您的评论！

备案号：

闽ICP备19015193号-1

关闭特效

衡与墨的博客