这是我昨天在这个视频中发现的兔子搜索算法的Rust实现。问题陈述如下。
一条线上有100个洞。一只兔子在其中一个洞里。你得抓住兔子。然而,你一次只能看一个洞。如果兔子在你看过的洞里,你就抓住兔子。如果兔子不在洞里,兔子就会移动到邻近的洞里。
该算法的工作原理是预期的。你得搜两遍。首先,进行一次完整的传递,然后执行另一次传递,但从索引1开始。然而,我还不熟悉Rust,所以在我的实现中有一些令人尴尬的代码片段。如何根据Rust的最佳实践改进代码?谢谢。
use rand::Rng;
const N: i32 = 100;
fn main() {
let mut rabbit_pos: i32 = rand::thread_rng().gen_range(0..N);
println!("Rabbit is at {}", rabbit_pos);
let searched = search(&mut rabbit_pos);
println!("Rabbit is at {}", rabbit_pos);
}
fn search(rabbit_pos: &mut i32) -> i32 {
let mut found = false;
let mut found_pos = 0;
for i in 0..N {
if lookup(i, rabbit_pos) {
println!("Found {}", i);
found = true;
found_pos = i;
break;
}
}
if found {
return found_pos;
}
for i in 1..N {
if lookup(i, rabbit_pos) {
println!("Found {}", i);
found = true;
found_pos = i;
break;
}
}
found_pos
}
fn lookup(n: i32, rabbit_pos: &mut i32) -> bool {
println!("Searching for {}", n);
if *rabbit_pos == n {
return true;
} else {
move_rabbit(rabbit_pos);
return false;
}
}
fn move_rabbit(prev: &mut i32) {
let new_pos = match *prev {
0 => 1,
i if i == (N-1) => N-2,
_ => *prev + (rand::thread_rng().gen_range(0..2) * 2 - 1),
};
println!("Rabbit moved from {} to {}", *prev, new_pos);
*prev = new_pos;
}发布于 2021-12-08 21:02:09
在搜索函数中,我建议删除变量found和foundpos。
如果查找成功,只需返回i。
否则,在我看来很好,尽管我只是简单地扫描了代码。
如果算法意外失败(在两个搜索循环之后没有找到兔子),也许您可以在调用中惊慌!(“未找到兔子”)。当算法失败时,简单地返回found_pos将是一个小错误!
发布于 2021-12-09 16:55:35
可能的bug:
您的代码只适用于偶数行的孔。如果你把N设为99,兔子从一个奇怪的洞开始,你就找不到它了。
N=3例,兔子从1号洞开始,在#1和#0之间交替:
[_] r _
r [_] _
_ r [_]
r [_] _
_ r [_]
"Rabbit not found" 您可能认为这是一个bug,也可能不是。这个问题要求100,它适用于100。但是您已经通过在顶部设置N来参数化它,所以它适用于任何偶数值。但是,没有什么要求N是偶数的。要么您应该添加一个检查,或者至少添加一个注释,或者在算法中添加一个微小的修改,以便它也能与奇数长度一起工作。
从未使用过searched值:
let searched = search(&mut rabbit_pos);
println!("Rabbit is at {}", rabbit_pos);https://codereview.stackexchange.com/questions/270761
复制相似问题