猜数策略:每次把范围分两半

逻辑思维 · 建议年级 4

在候选为1到16的有限集合中,验证连续折半的是非询问最多4次可确定秘密数。

逻辑思维

有限决策树层数

看一个例子

秘密数是1到16之一。每次问当前候选范围中点,例如先问“大于8吗”,再对剩余范围继续折半。最多问几次可确定?

先问是否大于8。无论回答怎样,16个候选都缩成8个。第二次对剩下的8个再折半,最多剩4个;第三次最多剩2个。第四次把最后2个分开,每条回答路径只剩1个数。候选上限依次是16、8、4、2、1,所以最多需要4次。

马上试一题

秘密数在1到8,连续折半最多问几次?