Rust 中的欧拉项目#2

Question

我正在学习 Rust，所以我正在做 Project Euler 问题，因为恕我直言，它们是很好的练习。 但我已经陷入了第二个问题。这个想法是找到斐波那契数列中所有小于 4000000 的偶数之和。 所以我尝试用函数式的方式来做，并使用自定义迭代器：

use std::mem;
static LIMIT: uint = 4000000u;
struct Fibonacci {
    current: uint,
    next: uint,
    limit: uint,
}
fn fibo(lim: uint) -> Fibonacci {
    Fibonacci {
        current: 1u, next: 1u, limit: lim
    }
}

impl Iterator<uint> for Fibonacci {
    fn next(&mut self) -> Option<uint> {
        let nex = self.current + self.next;
        let cur = mem::replace(&mut self.next, nex);
        if cur >= self.limit { return None; }
        Some(mem::replace(&mut self.current, cur))
    }
}

fn main() {
    let sum = fibo(LIMIT).filter(|&x| x%2 == 0).fold(0, |sum, x| sum + x);
    println!("Sum of fibs : {}", sum);
}

它看起来不错，并且给出了正确的斐波那契数列（我用

println!

s 进行了验证）。 问题是它没有给出正确的总和：它输出

1089154

，而它应该输出

4613732

。对我来说，折叠似乎错过了最后一个数字，但我不明白为什么！

我是 Rust 的初学者，因此我们将不胜感激，谢谢！

Answer 1

您应该在退出分支中测试的是

self.current

的值；相反，您正在测试

self.next

的值。 换句话说，您无法输出序列中的最后一个数字（正如 Matthieu 建议的那样）。

我验证了如果迭代器正确实现，它应该产生正确的结果（使用

grabbag_macros = "0.0.1"

作为 Cargo 依赖项）：

#![feature(phase)]
#[phase(plugin, link)] extern crate grabbag_macros;

static LIMIT: u64 = 4000000;

fn main() {
    let sum = recurrence![f[n]: u64 = 1, 1... f[n-1] + f[n-2]]
        .take_while(|&n| n <= LIMIT)
        .filter(|&n| n % 2 == 0)
        .fold(0, |a, b| a + b);
    println!("Sum of fibs: {}", sum);
}

其他一些随机注释：我会避免使用

uint

，因为它依赖于平台。 除非您需要具体说明类型，否则不需要

u

后缀。 您可以使用

take_while

或普通的旧式

take

而不是将限制硬编码到迭代器中。

Answer 2

struct EvenFibonacci {
    a: u64,
    b: u64,
}

impl EvenFibonacci {
    fn new() -> Self {
        EvenFibonacci { a: 2, b: 8 }
    }
}

impl Iterator for EvenFibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let next = 4 * self.b + self.a;

        self.a = self.b;
        self.b = next;
    
        Some(next)
    }
}

fn calculate_sum_of_even_fibo(limit: u64) -> u64 {
    let even_fibonacci = EvenFibonacci::new();

    even_fibonacci.take_while(|&x| x < limit).sum()
}

fn main() {
    const UPPER_LIMIT: u64 = 4_000_000;
    let answer = calculate_sum_of_even_fibo(UPPER_LIMIT);
    
    println!("\nProject Euler #2\nAnswer: {}", answer);
}