猜數策略:每次把範圍分兩半
在候選為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次。