来自：Google面试题

    题目：五个洞从左到右排成一排，按顺序分别是12345号，其中有一个洞里有一只狐狸。每天晚上，狐狸都会跳到一个相邻的洞里，每个白天，你只能允许检查其中的一个洞，要求在一个星期以内确保狐狸被抓住，请问应该用什么方法来检查洞？

    image.png

    思路：
    假设一种特殊情况，看看能不能推导到一般情况。
    假设狐狸第一天在偶数洞中，2 / 5 。

    • 第一天：检索 2 ，在则找到，不在则🦊在 4 。
    • 第二天：检索 3 ，🦊 第一天在 4 ，第二天在 3 / 5。不在则🦊5。
    • 第三天：检索 4 ，🦊第二天在 5 ，今天必在 4 。（必定抓住）

    所以在 🦊第一天在偶数洞的假设下，我们通过依次检索 2 3 4 必定可以抓到狐狸，如果没有抓住则假设不成立，🦊第一天在奇数洞中。
    狐狸第一天在奇数洞中，每天移动一格且必须移动，则有：

    • 第一天：在奇数洞。
    • 第二天：必定在偶数洞。
    • 第三天：必定在奇数洞。
    • 第四天：必定在偶数洞，及可以理解我第四天重新进入了 假设狐狸“第一天”在偶数洞中 的循环。检索 2 。
    • 第五天：检索 3
    • 第六天：检索 4（必定抓住）

    总结：我们的检索顺序按照 2 3 4 2 3 4 必定可以抓到狐狸，无论🦊第一天在奇数洞还是偶数洞，在第 3 天 和 第 6 六天必定抓住🦊。

    吧友提出的其他方案： 234432 、 432234