猜數策略:每次把範圍分兩半

邏輯思維 · 建議年級 4

在候選為1到16的有限集合中,驗證連續折半的是非詢問最多4次可確定秘密數。

邏輯思維

有限決策樹層數

看一個例子

秘密數是1到16之一。每次問當前候選範圍中點,例如先問「大於8嗎」,再對剩餘範圍繼續折半。最多問幾次可確定?

先問是否大於8。無論回答怎樣,16個候選都縮成8個。第二次對剩下的8個再折半,最多剩4個;第三次最多剩2個。第四次把最後2個分開,每條回答路徑只剩1個數。候選上限依次是16、8、4、2、1,所以最多需要4次。

立即試一題

秘密數在1到8,連續折半最多問幾次?