主題: 學習筆記
Python 電腦科學與程式設計導論 第四講：迴圈、猜測逼近與二進位
MIT OpenCourseWare 6.100L 第四講筆記：字串迴圈、窮舉、近似法、二分搜尋與二進位表示。
這篇筆記以 MIT OpenCourseWare 6.100L Fall 2022 的 Lecture 4 投影片、課程頁面與對應 YouTube 影片為主軸整理。內容刻意用「故事 + 小程式」把概念黏在腦子上，讓你以後看到迴圈不會只想到
range(10)。
0. 這堂課的主軸：Iteration 的三種「出場方式」
Lecture 4 把迴圈分成三種角色來看：
- 遍歷序列（字串也是序列）：逐字掃描、逐字做決定（Loops over Strings）。
- 暴力但保證會找到的搜尋（exhaustive enumeration / guess-and-check）：當解答空間是「可枚舉」的，就一個個猜到你服。
- 理解機器怎麼存數字（binary & floating point）：你以為的
0.1，其實不是你以為的0.1。
1. Loops over Strings：你不是在「跑字串」，你是在「巡邏一條街」
很多人第一次寫迴圈會卡在「我到底要跑什麼？」其實你可以把迴圈想成：你手上有一個可按順序走訪的東西（sequence），你就可以逐一處理它的元素。
字串就是 sequence，所以概念成立。
1.1 三種常見走法：走索引、走字元、或做 membership 判斷
A) 用索引（想要位置時很好用）
s = "banana"
for i in range(len(s)):
print(i, s[i])B) 直接走字元（最直覺、最不容易寫錯）
s = "banana"
for ch in s:
print(ch)C) 用 membership（像守門員一樣）
vowels = "aeiou"
s = "banana"
count = 0
for ch in s:
if ch in vowels:
count += 1
print("vowels:", count)小觀念：
in對字串是「是否包含某字元／子字串」的語意；你不是在比大小，你是在問：「你是不是我們這個陣營的人？」
2. 例子：Robot Cheerleaders（機器人啦啦隊）—— 用字串迴圈做「語感微調」
這個例子很可愛：你要讓機器人喊口號，但要注意 a/an 的選用：
a：後面接輔音音素（例如a ball）an：後面接母音音素（例如an apple）
我們先用簡化版規則：字母本身是 A/E/F/H/I/L/M/N/O/R/S/X（常見唸法以母音起頭）時就用 an。
def cheer(word: str) -> None:
an_letters = set("aefhilmnorsx") # 只做簡化示範
for ch in word.lower():
article = "an" if ch in an_letters else "a"
print(f"Give me {article} {ch}!")
print("What does that spell?")
print(word.upper() + "!!!")
cheer("MIT")你會看到：同樣是「跑字串」，但實際做的是 每個字元的分類 + 輸出格式控制。 這就是字串迴圈最常用的型態：掃描、判斷、累積／輸出。
3. Finger Exercise：數字 N 的立方根（perfect cube 才算）
MIT OCW 的 Lecture 4 Finger Exercise 要求：給你一個正整數 N，找它的整數立方根；如果不是 perfect cube 就輸出 error。
這題的「關鍵套路」是：一定要知道什麼時候停。 因為 guess-and-check 不能測無限多值，所以你需要「停止條件」。
3.1 解法（暴力但可靠）
def cube_root_or_error(N: int) -> None:
guess = 0
while guess**3 < N:
guess += 1
if guess**3 == N:
print(guess)
else:
print("error")
cube_root_or_error(27) # 3
cube_root_or_error(28) # error4. Guess-and-Check：暴力不是罪，沒有停止條件才是
Guess-and-check（又稱 exhaustive enumeration）其實很有哲學味：**如果你能把可能的答案列出來，那你遲早能找到答案。**但前提是你要能停下來。
4.1 例子：平方根（perfect square 才算）
x = int(input("Enter an integer: "))
guess = 0
while guess**2 < x:
guess += 1
if guess**2 == x:
print("Square root of", x, "is", guess)
else:
print(x, "is not a perfect square")負數怎麼辦？
投影片也提醒：如果 x 是負的，guess**2 < x 一開始就會是 False（左邊 ≥ 0、右邊 < 0），迴圈直接不跑，你會得到「不是 perfect square」，但訊息不夠友善。
可以先做負號旗標，或直接轉正處理（視題意而定）。
5. break：迴圈的緊急出口（但別讓它變成逃生梯依賴症）
有時候你已經知道「再跑也沒意義」，那就應該停。
break 會終止最內層的 for/while，直接跳出迴圈。
5.1 立方根：快一點點版本（遇到超過就 break）
cube = int(input("Enter an integer: "))
for guess in range(abs(cube) + 1):
if guess**3 >= abs(cube):
break
if guess**3 != abs(cube):
print(cube, "is not a perfect cube")
else:
if cube < 0:
guess = -guess
print("Cube root of " + str(cube) + " is " + str(guess))這段有兩個重點：
- 提早停止：只要
guess**3 >= abs(cube)就知道後面更不可能符合條件，直接停。 - 把負數變成正數做，最後再補回符號：流程更乾淨。
5.2 for-else（超容易被誤會但很強）
Python 的 for/while 可以搭配 else：
只有在迴圈「正常跑完」沒有被 break 中斷時，才會執行 else。
這個語意很適合拿來寫「搜尋是否失敗」的情境：
secret = 7
for i in range(1, 11):
if i == secret:
print("yes, it's", i)
break
else:
print("not found")你可以把
else想成：「我真的把每個可能都翻完了，還是沒找到。」
6. Boolean flag：用布林值當訊號燈（found / not found）
如果你不想用 for-else，也可以用布林旗標（Boolean flag）：
「發現就打開燈（True），沒發現就保持關（False）」，最後看燈的狀態做事。
secret = 7
found = False
for i in range(1, 11):
if i == secret:
print("yes, it's", i)
found = True
if not found:
print("not found")這個模式在「後面還要做更多事」時特別好用，例如：你找到東西後還要記錄更多資訊，或在多段程式中傳遞狀態。
7. 童年陰影回歸：用迴圈解文字題（但要小心效能）
投影片用售票文字題示範： Alyssa、Ben、Cindy 的售票數符合某些關係，總和固定，求 Alyssa。
7.1 小數字：直接三層迴圈也可以（但很慢）
for alyssa in range(11):
for ben in range(11):
for cindy in range(11):
total = (alyssa + ben + cindy == 10)
two_less = (ben == alyssa - 2)
twice = (cindy == 2 * alyssa)
if total and two_less and twice:
print(f"Alyssa sold {alyssa} tickets")
print(f"Ben sold {ben} tickets")
print(f"Cindy sold {cindy} tickets")7.2 大數字：把未知數減少（讓迴圈降維打擊）
當數字變成 1000、差距變成 20 時，三層迴圈會非常慢。 更好的作法是：只迴圈一個變數，其他用等式直接算出來。
for alyssa in range(1001):
ben = max(alyssa - 20, 0)
cindy = alyssa * 2
if alyssa + ben + cindy == 1000:
print("Alyssa sold " + str(alyssa) + " tickets")
print("Ben sold " + str(ben) + " tickets")
print("Cindy sold " + str(cindy) + " tickets")這裡的「大 idea」是：用計算把問題結構變簡單。 不是每個問題都該用暴力枚舉三層。
8. 二進位與浮點數：你以為你在算 0.1，其實你在算「最接近 0.1 的某個二進位分數」
Lecture 4 用一段很短的程式碼當「心理震撼彈」：
x = 0
for i in range(10):
x += 0.1
print(x == 1)
print(x, "==", 10 * 0.1)有時候你會看到 x == 1 是 False。
不是 Python 在鬧，而是 二進位浮點數無法精確表示多數十進位小數。
8.1 核心原因（超精簡版）
- 電腦硬體用 0/1 兩種狀態表示資訊，二進位對硬體很友善。
- 但十進位的
1/10（也就是 0.1）在二進位是無限循環小數，所以只能近似。 - 近似在大量運算後會累積，最後可能讓比較結果出現差異。
8.2 實務建議：別用 == 比 float
改用「容許誤差」比較：
def is_close(a: float, b: float, eps: float = 1e-10) -> bool:
return abs(a - b) < eps
x = 0.0
for _ in range(10):
x += 0.1
print(is_close(x, 1.0)) # True（通常）9. 十進位整數轉二進位：用 % 2 抓最後一位、用 // 2 右移
這是你第一次明確看到「用迴圈實作一個轉換演算法」。
想法如下：
x % 2會得到最後一個 bit（0 或 1）x // 2會把整數除以 2（等於二進位右移一格）- 重複直到 x 變成 0
- 注意：你拿到的是 從右到左 的 bit，所以要反轉或反向組字串。
def dec_to_bin(n: int) -> str:
if n == 0:
return "0"
is_neg = n < 0
n = abs(n)
bits = ""
while n > 0:
bits = str(n % 2) + bits
n //= 2
return "-" + bits if is_neg else bits
print(dec_to_bin(19)) # 10011
print(dec_to_bin(1507)) # 1011110001110. 收尾：這堂課真正要你帶走的技能
你學的不是「for/while 的語法」，而是三個可重複使用的模式：
- 掃描（scan）：逐字、逐元素地看資料
- 搜尋（search）：枚舉候選答案、用條件篩選
- 轉換（transform）：把資料從一種表示法，轉成另一種表示法
一旦你腦中有這三個模式，迴圈就不再是「重複做某件事」，而是你解題的引擎。