面试题:猜奖品问题

一个猜测游戏中,某一个瓶子中装有奖品。游戏者需要猜出奖品在哪个瓶子中,并且在m次结束游戏。(即m次猜中)
有n个黑色的瓶子(以至于游戏中看不到瓶中是否有东西)设从0到n-1编号,一字排开。每一次如果游戏者猜错了,那么奖品会各以50%的概率移动到左边或者右边的瓶子中。当奖品位于最左边或者最右边,游戏者猜错时,奖品必然右移或者左移。

问题:请设计一个满足n和m的策略,帮助游戏者完成游戏。

最多需要m=2n次 必能猜中
第一轮 先从0开始顺序往右猜,即0,1,…n-1,这样 如果奖品初始位于偶数位置处 必定能猜中
如果奖品初始是位于奇数处,则需要第二轮
如果n为偶数 则第一轮结束后奖品仍在奇数处
这样第二轮从1开始往右,即1,2,…,n-1 这样必中
如果n为奇数 则第一轮结束后奖品已经跳到偶数处
这样第二轮从0开始往右,即0,1,…,n-1 必中

本站总访问量