猜數字 - 進階 (flowchart & pseudocode)


Posted by mijouhsieh on 2022-03-17

基礎的猜數字 ,會把猜過的數字又重複猜到,為了提升效率,把猜數字 1~100,在10次內猜完。

運算思維

假設1-10中答案為7。
第1回: 猜5 (以二元搜尋法取中間值, 可確認有一半的範圍是不需要的! )

round guess next range
1 5 6 ~ 10
2 8 6 ~ 7
3 6 7
4 7 -

拆解-辨識模式

round guess next range min max compare
0 - 1 ~ 10 1 10 -
1 5 6 ~ 10 6 (guess+1) 10 < 7
2 8 6 ~ 7 6 7 (guess-1) > 7
3 6 7 7 7 =7
4 7 - - - -

辨識模式說明

  1. 設定最大值最小值
  2. 猜最大最小值中間的數字
  3. 若猜的數字比答案小,把min改成猜的數字+1
  4. 若猜的數字比答案大,把max改成猜的數字-1
  5. 重複2 ~ 4步驟,直到猜到為止。

flowchart

最終版flowchart

flowchart 思考過程

pseudocode

PSEUDOCODE STANDARD

答案為隨機值
設定 guess = 0
設定 min = 1
設定 max = 100
設定 count = 0 //回合數

WHILE guess !== answer
    count += 1
    guess = Math.floor((min + max) / 2)
    IF guess > answer
        max = guess - 1
    ELSE IF guess < answer
        min = guess + 1
    ELSE
        答對
    END IF
END WHILE

coding

完整程式碼


L14 L15 let min = 1let max = 10 不是寫在While loop內,這樣每新的回合都被重新宣告。所以移到文件最上方。


L16 L17 猜中間數字 2種寫法
guess = Math.floor((min + max)/2)
guess = Math.floor((max - min) / 2) + min


L22 L26
max = guess-1min = guess+1 若沒有賦值-1或+1(調整上下限)仍可以跑程式,且可在10次內猜完。
但是,如果答案為100時,猜99 -> 太小 -> 回合加1 -> guess = Math.floor((99 + 100)/2) = 99 -> 無限迴圈。
答案為100時,沒有調整上下,無限迴圈99


#flowchart #pseudocode #infinite loop #二元搜尋法 #Binary search #運算思維







Related Posts

[Note] JS: this

[Note] JS: this

DAY 01 : 資料結構緒論

DAY 01 : 資料結構緒論

[Note] 網頁的構成要素

[Note] 網頁的構成要素


Comments