综合练习：经典题三连
这是什么：三道经典算法题，把查找、排序、递归、动态规划一次性串起来考。
为什么用：查找、排序、递归、动态规划都过了一遍，是时候综合验收了。学得越多越容易混，只有真上手做题才分得清什么时候用哪一招。
如何用：本章先猜数字（二分查找）、再排序排成绩单、最后用动态规划算爬楼梯，每题先自己想 5 分钟。
第 1 题：二分查找猜数字
经典游戏：我心里想一个 1~100 的数，你来猜，我只说"大了"或"小了"。这回换电脑当猜的人——用二分查找的思路，永远猜剩余范围的中间：
target = 66 # 心里想好的答案（1~100）
low, high = 1, 100 # 二分查找的左右指针
count = 0
while low <= high:
mid = (low + high) // 2
count += 1
if mid == target:
print(f"第 {count} 次猜 {mid}，猜中啦！")
break
elif mid < target:
print(f"第 {count} 次猜 {mid}，太小")
low = mid + 1
else:
print(f"第 {count} 次猜 {mid}，太大")
high = mid - 1
你会看到：
第 1 次猜 50，太小
第 2 次猜 75，太大
第 3 次猜 62，太小
第 4 次猜 68，太大
第 5 次猜 65，太小
第 6 次猜 66，猜中啦！1~100 最多 7 次必中；把范围换成 1~100 万？也只要 20 次。这就是二分查找的底气。
第 2 题：冒泡排序成绩单
四名同学的成绩单是乱序的，用第 3 章手写的冒泡排序，按分数从高到低排好：
scores = [("阿呆", 76), ("阿瓜", 92), ("小青蛙", 88), ("豆豆", 64)]
n = len(scores)
for i in range(n - 1):
for j in range(n - 1 - i):
if scores[j][1] < scores[j + 1][1]: # 分数高的往前冒
scores[j], scores[j + 1] = scores[j + 1], scores[j]
for name, score in scores:
print(f"{name} {score} 分")
你会看到：
阿瓜 92 分
小青蛙 88 分
阿呆 76 分
豆豆 64 分要点就一处：比较的是 scores[j][1]（元组里的分数），交换的却是整个元组。顺便一提，正式项目里一行 sorted(scores, key=lambda s: s[1], reverse=True) 也能达到同样效果。
第 3 题：爬楼梯（动态规划招牌题）
楼梯有 n 级，每次能上 1 级或 2 级，有多少种走法？想通了它就是斐波那契：到第 n 级的最后一步，要么从 n-1 级跨 1 级，要么从 n-2 级跨 2 级，所以 ways(n) = ways(n-1) + ways(n-2)。加上 @lru_cache 记住答案，50 级也瞬间出结果：
from functools import lru_cache
@lru_cache(maxsize=None)
def ways(n):
if n <= 2:
return n # 1 级有 1 种走法，2 级有 2 种
return ways(n - 1) + ways(n - 2)
print("爬 10 级楼梯有", ways(10), "种走法")
print("爬 30 级楼梯有", ways(30), "种走法")
print("爬 50 级楼梯有", ways(50), "种走法")
你会看到：
爬 10 级楼梯有 89 种走法
爬 30 级楼梯有 1346269 种走法
爬 50 级楼梯有 20365011074 种走法试试去掉装饰器再算 ways(50)——等到天荒地老也算不完。一道题串起"递归 + 动态规划"，这就是内功。