密室酒鬼问题
这是经典题密室找小偷的改编，当然比原题难多了。有9间酒窖排成一排，一个酒鬼躲在其中一间酒窖里，每天偷喝一瓶酒，老板每天只能搜查一间酒窖，可发现被酒鬼喝空的酒瓶，而每过一天，酒鬼必定会转移到相邻的密室里. 问至少需要多少天才能保证找到酒鬼？注意：第一天会有1个空酒瓶产生。
- 上一篇：精神分裂的匠人
- 下一篇：只能看不能读的文字（七） 《饥鸡集矶记》
回复列表
至少5天才能保证找到酒鬼。。。
设酒窖编号为a，b，c，d，e，f，g，h，i。
由题意，第一天酒鬼喝完后，第二天被主人发现了。假设酒鬼第一天去了c。那么第二天老板知道他会去相邻的。所以老板就到d去查（选定一个长的方向，因为如果酒鬼去了d他就会被抓到，如果去b，这样就使逃的次数慢慢变小）如果没抓到，则第三天，去c，如果没抓到，第四天去b一定会抓到。以此类推。。。如果酒鬼第一次去了e，那么此时他的逃跑天数是最多的，此时为5天
设酒窖编号为a，b，c，d，e，f，g，h，i。
由题意，第一天酒鬼喝完后，第二天被主人发现了。假设酒鬼第一天去了c。那么第二天老板知道他会去相邻的。所以老板就到d去查（选定一个长的方向，因为如果酒鬼去了d他就会被抓到，如果去b，这样就使逃的次数慢慢变小）如果没抓到，则第三天，去c，如果没抓到，第四天去b一定会抓到。以此类推。。。如果酒鬼第一次去了e，那么此时他的逃跑天数是最多的，此时为5天
假设：主人足够聪明，并且运气极差（或者说酒鬼有先知之明，知道主人会找哪里）。并且有题带有的条件，空酒瓶必然可以发现，而且酒鬼只能在第二次移动到相邻的酒窖里。
因为如果考虑运气，第一天就可以碰巧找到那个酒鬼。
在假设的前提下：
最优化的寻找方法：
第一种:中点法。
采用理由：酒鬼每天换酒窖的关系为相邻，而酒窖是一字排开，而不是成环形。
酒窖=1的时候，天数=1；
酒窖=2的时候，天数=2；
因为第一次找任何一个，都没有找到，第二天继续找这个酒窖，必然找到。
当酒窖=3的时候，
第一天搜查第二个酒窖，没有找到（运气太差，嘿嘿）；第二天继续搜查这个酒窖，酒鬼肯定在这里。因为无论酒鬼第一天在第一个酒窖里，还是第三个酒窖里，第二天都会转移到相邻的第二个酒窖里。也就是当
酒窖=3的时候，天数=2。
而采用其它方法，当酒窖=3的时候，比如从第一个酒窖开始找，那么，没有找到，一天；第二天找第二个酒窖，没有找到，但肯定发现了一个空酒瓶（因为如果没有空酒瓶，说明酒鬼第一天肯定在第三个酒窖里，那么第二天他必然在第二个酒窖里，这与没有找到酒鬼矛盾），这时候酒鬼可能在第一个里，也可能在第三个里。第三天，继续找第二个酒窖，肯定找到酒鬼。需要3天。这个方法不是最优化的。所以，中点法比较好。
当酒窖=4的时候，
因为第二个和第三个酒窖位置作用相同，所以，可以选择从第二个或者第三个酒窖开始找。假设从第二个开始找：
第一天找第二个酒窖没有找到酒鬼。酒鬼必然在第一个，第三个，或者第四个里。产生了一个空酒瓶。
第二天找第三个酒窖，没有找到酒鬼：这时候，可能发现一个空酒瓶或者没有发现空酒瓶。
1）如果没有发现空酒瓶，那么酒鬼在第一天里，肯定不在第三个和第二个里，也就是酒鬼第一天肯定在第一个，或者第四个里，那么第二天他肯定应该在第二个，或者第三个里，而第二天第三个里没有，那么第二天酒鬼肯定在第二个里；那么第三天酒鬼会去第一个，或者第三个，这个时候，为了堵住他的去路，第三天继续寻找第三个酒窖，没有找到；说明酒鬼去了第一个（注意，第一个酒窖已经产生了2个空酒瓶），第四天，酒鬼必定在第二个里。这个时候酒窖=4，天数=4.
2）如果发现空酒瓶，那么，酒鬼在第二天的时候，肯定在第四个里，或者在第二个里，如果在第四个里，第三天继续去第三个酒窖，肯定找到；这个时候酒窖=4，天数=3。如果在第二个里，那么酒鬼在第三天可能在第三个，或者第一个里，所以为了堵住酒鬼的去路，第三天必须继续找第三个酒窖，没有找到，酒鬼去了第一个。第四天找第二个酒窖，肯定找到。这个时候，酒窖=4，天数=4
因为如果考虑运气，第一天就可以碰巧找到那个酒鬼。
在假设的前提下：
最优化的寻找方法：
第一种:中点法。
采用理由：酒鬼每天换酒窖的关系为相邻，而酒窖是一字排开，而不是成环形。
酒窖=1的时候，天数=1；
酒窖=2的时候，天数=2；
因为第一次找任何一个，都没有找到，第二天继续找这个酒窖，必然找到。
当酒窖=3的时候，
第一天搜查第二个酒窖，没有找到（运气太差，嘿嘿）；第二天继续搜查这个酒窖，酒鬼肯定在这里。因为无论酒鬼第一天在第一个酒窖里，还是第三个酒窖里，第二天都会转移到相邻的第二个酒窖里。也就是当
酒窖=3的时候，天数=2。
而采用其它方法，当酒窖=3的时候，比如从第一个酒窖开始找，那么，没有找到，一天；第二天找第二个酒窖，没有找到，但肯定发现了一个空酒瓶（因为如果没有空酒瓶，说明酒鬼第一天肯定在第三个酒窖里，那么第二天他必然在第二个酒窖里，这与没有找到酒鬼矛盾），这时候酒鬼可能在第一个里，也可能在第三个里。第三天，继续找第二个酒窖，肯定找到酒鬼。需要3天。这个方法不是最优化的。所以，中点法比较好。
当酒窖=4的时候，
因为第二个和第三个酒窖位置作用相同，所以，可以选择从第二个或者第三个酒窖开始找。假设从第二个开始找：
第一天找第二个酒窖没有找到酒鬼。酒鬼必然在第一个，第三个，或者第四个里。产生了一个空酒瓶。
第二天找第三个酒窖，没有找到酒鬼：这时候，可能发现一个空酒瓶或者没有发现空酒瓶。
1）如果没有发现空酒瓶，那么酒鬼在第一天里，肯定不在第三个和第二个里，也就是酒鬼第一天肯定在第一个，或者第四个里，那么第二天他肯定应该在第二个，或者第三个里，而第二天第三个里没有，那么第二天酒鬼肯定在第二个里；那么第三天酒鬼会去第一个，或者第三个，这个时候，为了堵住他的去路，第三天继续寻找第三个酒窖，没有找到；说明酒鬼去了第一个（注意，第一个酒窖已经产生了2个空酒瓶），第四天，酒鬼必定在第二个里。这个时候酒窖=4，天数=4.
2）如果发现空酒瓶，那么，酒鬼在第二天的时候，肯定在第四个里，或者在第二个里，如果在第四个里，第三天继续去第三个酒窖，肯定找到；这个时候酒窖=4，天数=3。如果在第二个里，那么酒鬼在第三天可能在第三个，或者第一个里，所以为了堵住酒鬼的去路，第三天必须继续找第三个酒窖，没有找到，酒鬼去了第一个。第四天找第二个酒窖，肯定找到。这个时候，酒窖=4，天数=4
