五洞抓狐问题

网上看到一个非常有趣的问题，据说是谷歌的一个面试题。题目如下：草原上有五个排成一排的洞穴，里面藏有一只小狐狸，这只狐狸每天晚上必换洞，并且只能走到左右相邻的洞里。我们每天也只能打开一个洞穴抓它。问是否有方法能必然抓到这只小狐狸？

答案是有的，里面涉及了一个非常巧妙的分析算法。根据算法写的模拟代码如下，具体分析在最下面。

import random 

def get_next_hole(cur_hole):
    if cur_hole <= 1:
        next_hole = cur_hole + 1
    elif cur_hole >= 5:     
        next_hole = cur_hole - 1
    else:
        next_hole = cur_hole + random.choice([-1, 1])
    return next_hole 

def caught_fox_in_hole():
    cur_hole = random.choice([1, 2, 3, 4, 5])
    guess_it = 2
    steps = 0
    caught = False

    while not caught: 
        steps += 1
        caught = (guess_it == cur_hole) 
        cur_hole = get_next_hole(cur_hole)
        if guess_it >= 4:
            guess_it = 2
        else:
            guess_it += 1

    print(f"Fox caught after {steps} steps")
    return steps

if __name__ == '__main__':
    total = 10000
    sum = 0
    for i in range(total):
        sum += caught_fox_in_hole()

    print(f"Average steps to catch the fox over {total} trials: {sum / total}")

问题分析 题目中的关键信息是狐狸只能移动到相邻的格子中，这在洞穴号码体现的就是从奇数到偶数，或从偶数到奇数。

我们首先假设狐狸在偶数号洞中。

1. 打开2号，如果不在，那它就是在4号
2. 第二天，它会从4号移到3或5号，我们打开3号，如果不在，那它就是在5号
3. 第三天，它从5号必然会移动到4号，我们打开4号，如果还不在，那我们的假设是错的

也就说说这只狐狸最开始在奇数号中。也就是前3天我们完美的错过了它，但第四天它一定是在偶数号中。因为奇->偶->奇->偶

1. 第四天，我们直接打开2号，这次我们知道它必然是在偶数号，如果没有，就重复上面的步骤
2. 第五天，打开3号
3. 第六天，打开4号

最多6天，必然会被抓到。

附上面程序的运行日志，也可以看到，期望值是3.5天。

...
Fox caught after 3 steps
Fox caught after 4 steps
Fox caught after 4 steps
Fox caught after 5 steps
Fox caught after 3 steps
Fox caught after 4 steps
Fox caught after 6 steps
Fox caught after 4 steps
Fox caught after 4 steps
Fox caught after 1 steps
Fox caught after 3 steps
Average steps to catch the fox over 10000 trials: 3.5091