一个猜测游戏中，某一个瓶子中装有奖品。游戏者需要猜出奖品在哪个瓶子中，并且在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 必中
Read full article from 面试题：猜奖品问题 | chaozh.com
No comments:
Post a Comment