锈锁问题数论

Question

骆家辉问题如下：

20个无聊的学生轮流走在一个大厅里，里面有一排封闭的储物柜，编号从1到20。第一个学生打开了所有的储物柜；第二个学生关闭了所有编号为2、4、6、8、10、12、14、16、18、20的储物柜；第三个学生操作编号为3、6、9、12、15、18的储物柜:如果一个储物柜被关闭，他打开它，如果一个储物柜打开，他就关闭它；等等。对于第一个学生，他工作的储物柜编号为i的倍数:如果一个储物柜被关闭，他打开它，如果一个储物柜是打开的，他关闭它。在所有的学生走完路后，仍然打开的储物柜的数目是多少？

我决定用额外的一英里来解决这个问题，让用户确定走廊里有多少学生，所以这个数字并不总是20。我可以用什么方式重构我的代码呢？

use std::io;

fn main() {
    // false = closed
    // true = opened
    let mut lockercount = String::new();
    println!("How many students?");
    io::stdin().read_line(&mut lockercount).expect("expected int");
    let lc = lockercount.trim().parse().unwrap();
    let mut lockers = vec![false; lc];

    for i in 1..(lockers.len()+1) {
        let mut j: usize = 1;
        while i*j <= lc {
            lockers[(i*j)-1] = !lockers[(i*j)-1];
            j += 1;
        }
    }
    
    let mut lockernum = 1;
    println!("Opened lockers:");
    for v in lockers {
        if v == true {
            print!("{}, ", lockernum);
        }
        lockernum += 1;
    }
}

Answer 1

你的代码看上去很好。然而，有一部分我肯定会改变:变量的范围。例如，lockercount对于更多的初始lc来说并不是必需的。我们可以缩小它的范围：

    println!("How many students?");
    let lc = {
        let mut lockercount = String::new();
        io::stdin().read_line(&mut lockercount).expect("expected int");
        lockercount.trim().parse().unwrap()
    };

类似地，我更喜欢使用enumerate而不是显式计数器。显式计数器可能不会意外地递增，但是迭代器上的enumerate总是合适的：

    println!("Opened lockers:");
    for (n, v) in lockers.iter().enumerate() {
        if *v == true {
            print!("{}, ", n + 1);
        }
    }

我们也可以通过if通过filter处理掉它，但这有点多了：

    for (n, _v) in lockers.iter().enumerate().filter(|(_, &b)| b) {
        print!("{}, ", n + 1);
    }

在代码的算法部分，我倾向于显式地使用pos，而不是i*j：

    for i in 1..(lockers.len() + 1) {
        let mut pos: usize = i;
        while pos <= lc {
            lockers[pos - 1] = !lockers[pos - 1];
            pos += i;
        }
    }

同样，与其显式更改计数器，我更希望使用不可变变量，例如通过step_by：

    for i in 1..(lockers.len() + 1) {
        for pos in (i..lc).step_by(i) {
            lockers[pos - 1] = !lockers[pos - 1];
        }
    }