猜數字

同一個問題，笨方法要一百次，聰明方法只要七次。 · ⏱ 約 30 分鐘

你會學到三件事

1. 同一個問題有很多種解法，而它們的代價差很多
2. 二分搜：每猜一次，範圍就少一半
3. 「要跑幾次」可以被計算，而亂數讓它變成真的遊戲

開始之前

這一課沒有新的語法，你已經會的東西剛好夠了：變數、while、if、比較。

而它是整個課程的轉折：在這之前你在學怎麼講， 從這裡開始你要學講什麼。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、笨方法

猜一個 1 到 100 的數字。從 1 開始一個一個試：

1int guess = 1;2while (guess != target) {3    guess = guess + 1;4}

它一定猜得到。而如果答案是 100，你要猜 100 次。

二、聰明方法

改成每次都猜範圍的正中間：

1int lo = 1, hi = 100;2int mid = (lo + hi) / 2;    // 50

猜 50，然後：

每猜一次，可能的範圍就少一半。

猜中就不必再猜了——那顆積木寫著「跳出迴圈」（第 11 課用過）。

100 → 50 → 25 → 13 → 7 → 4 → 2 → 1
 ①    ②    ③    ④   ⑤   ⑥   ⑦

七次。而笨方法最多一百次。

三、七這個數字是算得出來的

範圍每次砍一半，砍幾次會剩下 1？

100 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ≈ 0.78
      ①   ②   ③   ④   ⑤   ⑥   ⑦

也就是「2 要乘幾次才會超過 100」——答案是 7（2⁷ = 128）。

推廣一下：

範圍變成一萬倍，二分搜只多了 23 次。

這就是「複雜度」在講的事：不是「快多少」， 是「資料變大的時候，它變慢的速度」。

四、寫出來

照著打上這一段：

1int lo = 1, hi = 100, steps = 0;2while (lo <= hi) {3    int mid = (lo + hi) / 2;4    steps = steps + 1;5    if (mid == target) break;6    if (mid < target) lo = mid + 1;7    else hi = mid - 1;8}

⚠️ 三個很容易寫錯的地方：

1. lo <= hi 不是 lo < hi。寫成 < 的話，範圍剩一個數字時就不猜了
2. mid - 1 和 mid + 1 的那個 1 不能省，因為 mid 已經猜過了， 不排掉它會變成無窮迴圈
3. (lo + hi) / 2 是整數除法（第 6 課），小數會被丟掉，而這裡正好是我們要的

五、讓它變成真的遊戲

到這裡 target 是寫死的 42——你每次跑，答案都一樣。

真正的猜數字要每次不一樣。C++ 有一顆專門做這件事的：

1cout << rand() << endl;      // 一個很大的隨機整數

積木盤上它寫著「產生隨機數」。

但 rand() 給的數字太大了，要把它壓進 1 到 100：

1int target = rand() % 100 + 1;

rand()          一個很大的數
    % 100       取餘數 → 0 到 99
        + 1     → 1 到 100

⚠️ 而這樣還不夠：rand() 每次重跑程式會給出同一串數字。 它不是真的隨機，是照一條固定的規則算出來的，所以叫「偽隨機」。 要讓每次不一樣，得先給它一個種子：

1srand(time(0));

積木盤上它寫著「設定亂數種子 …」。

time(0) 是現在的時間（從 1970 年算起的秒數），每一秒都不一樣， 所以每次跑拿到的那一串就不一樣。

time(0) 這種「名字後面接一對括號」的寫法叫呼叫函式， 積木盤上那顆就寫著「呼叫函式 …（…）」。 第 18 課會整整講一課，這裡先照抄就好。

⚠️ srand 只呼叫一次，放在 main 的最前面。 放進迴圈裡的話，同一秒內每一圈的種子都相同，反而每次都拿到一樣的數字。

這兩顆各要一個標頭檔：

1#include <cstdlib>    // rand, srand2#include <ctime>      // time

完成的樣子

1#include <iostream>2using namespace std;3int main() {4    int target = 42;5    int lo = 1, hi = 100, steps = 0;6    while (lo <= hi) {7        int mid = (lo + hi) / 2;8        steps = steps + 1;9        if (mid == target) break;10        if (mid < target) lo = mid + 1;11        else hi = mid - 1;12    }13    cout << "猜了 " << steps << " 次" << endl;14    return 0;15}

把積木打散，自己排回去：排回去：把剛才那支程式的積木排好

換你了

把 target 換成 1、換成 100、換成 63，看看各要幾次。

最多是幾次？ 試出那個最壞的情況，它應該是 7。

到編輯器做這一題：練習：target 換成 1，看要幾次

做一個

讀進一個 1 到 100 的數字。用一個一個找數出要幾次，再用二分搜數一次。 印出兩個次數（各一行）。⚠️ 裁判用的是 42。

🔴 換幾個數字試試：哪一種的次數變化很大，哪一種幾乎不動？

到編輯器做這一題：做一個：兩種找法各要幾次

做一個：換人猜

把角色反過來：程式想一個 1 到 100 的數字，你來猜。 程式每次告訴你「太大了」「太小了」或「中了，你猜了 N 次」。

target 用 srand + rand 產生
while (true) {
    讀進一個猜測
    比大小，印出提示
    猜中就 break
}

🔴 這一題裁判不會幫你驗，因為答案每次都不一樣，沒有固定的輸出可以比對。 自己玩三遍，再讓旁邊的人玩一遍。

🔴 玩的時候注意你自己怎麼猜：你用的是這一課的二分搜嗎？ 如果是，你最多幾次猜到？跟理論上的 7 次對得上嗎？

到編輯器做這一題：做一個：換人猜，程式當裁判

這一課你做了什麼

• 你寫出了兩種解同一個問題的方法
• 你看到範圍一萬倍、次數只多 23 次
• 你第一次計算了「一個做法要跑幾次」
• 你用亂數種子做出了一個每次都不一樣的遊戲

如果卡住了