猜数策略:每次把范围分两半
在候选为1到16的有限集合中,验证连续折半的是非询问最多4次可确定秘密数。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 秘密数只在1到16中。每次问当前范围中点,把候选尽量分成两半。
- 先问是否大于8。无论回答怎样,16个候选都缩成8个。
- 第二次对剩下的8个再折半,最多剩4个;第三次最多剩2个。
- 第四次把最后2个分开,每条回答路径只剩1个数。
- 候选上限依次是16、8、4、2、1,所以最多需要4次。
- 这是对1到16这个有限集合的保证,不延伸成任何情境下都最快的结论。四层回答路径的叶子必须覆盖全部16个候选。
逻辑思维
有限决策树层数
看一个例子
秘密数是1到16之一。每次问当前候选范围中点,例如先问“大于8吗”,再对剩余范围继续折半。最多问几次可确定?
先问是否大于8。无论回答怎样,16个候选都缩成8个。第二次对剩下的8个再折半,最多剩4个;第三次最多剩2个。第四次把最后2个分开,每条回答路径只剩1个数。候选上限依次是16、8、4、2、1,所以最多需要4次。
马上试一题
8→4→2→1,需要3次。