如何猜數字

| 循序搜尋法 | 二分搜尋法 | 平均猜中次數 | 模擬猜數過程 |
策略1 -- 循序搜尋法
  • 假設被猜數的範圍是 1∼10,所謂的循序搜尋法就是由 1 開始猜,如果不對就再猜 2,如果不對就再猜 3, 如果不對就再猜 4,...... 如此一直猜下去。
  • 在最差的情況下,10 個數字在第 10 次時一定可以猜出來。100 個數字在第 100 次時一定可以猜出來。
  • 如果要猜的數字不是按照順序排列好的,數字的個數也不多,這個方法還勉強可用;但因為我們要猜的 數字全是按照順序排列好的,所以大概不會有人真的使用本法來猜數吧!
策略2 -- 二分搜尋法
  • 假設被猜數的範圍是 1∼10,所謂的二分搜尋法就是:
    1. 將 1∼10 的數字分成兩半,因為共有 10(= 10 - 1 + 1) 個數字,所以就猜 6(= 1 + 10 ÷2)。如果太大了, 猜數範圍就變成 1 ∼ 5,如果太小了,猜數範圍就變成 7 ∼ 10。
    2. 現在假設猜數範圍是 7 ∼ 10,因為共有 4(= 10 - 7 + 1) 個數字,所以就猜 9(= 7 + 4 ÷2)。如果太大了, 猜數範圍就變成 7 ∼ 8,如果太小了,猜數範圍就變成 10 ∼ 10。
    3. 現在假設猜數範圍是 7 ∼ 8,因為共有 2(= 8 - 7 + 1) 個數字,所以就猜 8(= 7 + 2 ÷2)。如果太大了, 猜數範圍就變成 7 ∼ 7。
    4. 其餘的情況請自行推演。
  • 在最差的情況下,猜數的範圍是 1∼10 時,最多只要 4 次一定可猜中, 猜數的範圍是 1∼100 時,最多只要 7 次一定可猜中。
  • 猜數的個數和所需的次數倒底有什麼關聯呢,請參考下面的表格:
    數字個數所需次數
    1 1
    2 ∼ 3 2
    4 ∼ 7 3
    8 ∼ 15 4
    16 ∼ 31 5
    32 ∼ 63 6
    64 ∼ 127 7
    128 ∼ 255 8
    256 ∼ 511 9
    512 ∼ 1023 10
    1024 ∼ 2047 11
    2048 ∼ 4095 12
    4096 ∼ 8191 13
    8192 ∼ 16384 14
    .... ...
  • 你看出猜數的個數和所需次數的關聯了嗎?沒錯,那就是:
    當 2n ≦ 猜數的個數 < 2n+1 時,則所需的次數 = n
二分搜尋法的平均猜中次數
  • 理論是理論,本法實際操作時的效率如何呢? 以下尤怪就以程式來模擬二分搜尋法,讓實際的數據來說話吧!
    電腦設定被猜數字時其範圍為:
    我要模擬猜數:
二分搜尋法的猜數過程
  • 如果你對二分搜尋法的猜數過程仍然不了解,請設定好被猜數字的範圍及被猜數字,讓電腦把二分搜尋法 猜數的過程顯示給你看吧!
    電腦設定被猜數字時其範圍為:
    我設定的被猜數字是:
 
 
 
本網頁建置日期:91.03.17 | 最近更新日期:91.03.17  | 回上頁 | 回首頁 |