首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >锈蚀中的兔子搜索问题

问锈蚀中的兔子搜索问题
EN

Code Review用户
提问于 2021-12-07 09:00:09
回答 2查看 954关注 0票数 3

这是我昨天在这个视频中发现的兔子搜索算法的Rust实现。问题陈述如下。

一条线上有100个洞。一只兔子在其中一个洞里。你得抓住兔子。然而,你一次只能看一个洞。如果兔子在你看过的洞里,你就抓住兔子。如果兔子不在洞里,兔子就会移动到邻近的洞里。

该算法的工作原理是预期的。你得搜两遍。首先,进行一次完整的传递,然后执行另一次传递,但从索引1开始。然而,我还不熟悉Rust,所以在我的实现中有一些令人尴尬的代码片段。如何根据Rust的最佳实践改进代码?谢谢。

代码语言:javascript
复制
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;
}
EN

回答 2

Code Review用户

回答已采纳

发布于 2021-12-08 21:02:09

在搜索函数中,我建议删除变量found和foundpos。

如果查找成功,只需返回i。

否则,在我看来很好,尽管我只是简单地扫描了代码。

如果算法意外失败(在两个搜索循环之后没有找到兔子),也许您可以在调用中惊慌!(“未找到兔子”)。当算法失败时,简单地返回found_pos将是一个小错误!

票数 2
EN

Code Review用户

发布于 2021-12-09 16:55:35

可能的bug:

您的代码只适用于偶数行的孔。如果你把N设为99,兔子从一个奇怪的洞开始,你就找不到它了。

N=3例,兔子从1号洞开始,在#1和#0之间交替:

代码语言:javascript
复制
[_] r  _
 r [_] _
 _  r [_]
 r [_] _
 _  r [_]
"Rabbit not found" 

您可能认为这是一个bug,也可能不是。这个问题要求100,它适用于100。但是您已经通过在顶部设置N来参数化它,所以它适用于任何偶数值。但是,没有什么要求N是偶数的。要么您应该添加一个检查,或者至少添加一个注释,或者在算法中添加一个微小的修改,以便它也能与奇数长度一起工作。

从未使用过searched值:

代码语言:javascript
复制
    let searched = search(&mut rabbit_pos);
    println!("Rabbit is at {}", rabbit_pos);
票数 2
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/270761

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档