报数游戏

来自计算思维百科
跳转至: 导航搜索
报数游戏.png

问题介绍:对方给出一个1到100之间的数字,你可以问他六个问题,然后你根据他的回答猜测对方的数字。

解决方案---按大小二分查找

这种问题和你问我答类似,都是通过提问一步一步地缩小问题可能存在的范围,从而找到最终的解。那么有没有这种可能,就是我只问六个问题,就一定能找到对方的数字呢?答案是有的。解决这个问题的主要思想是折半查找,把一个大问题(从1到100 中找到对方的数字)转化为更小的问题(比如说从1-50或是50-100中找到这个数字),这样子逐步缩小解空间,然后在更小的范围中再查找,直到找到解为止。

假设对方的数字是1,我只需问六个问题:

  1. 比50大还是比50小还是相等?(回答:小)
  2. 比25大还是比25小还是相等?(回答:小)
  3. 比12大还是比12小还是相等?(回答:小)
  4. 比6大还是比6小还是相等?(回答:小)
  5. 比3大还是比3小还是相等?(回答:小)
  6. 比2大还是比2小还是相等?(回答:小)
  7. 答案是1

可以体现的计算思维

利用二分查找法确定这个数字,每次都是把大的搜索空间缩小一半,在缩小的搜索空间中继续采用相同的求解方法,体现计算思维的递归特点。