波仔
💻 第五章 与算法成为好朋友的七个要点
📄 一句话概括

好算法的两条底线：每一步写得清清楚楚（明确）、步数有个头（有限）——二分猜数 7 步必中就是典范。

📝 本节和前面几节的关系

七个要点的第一个，也是底线条款：步骤必须明确且有限。教材用猜数游戏把它讲活。

一、明确：每步无歧义

【往中间猜】不是算法——中间是谁、猜完怎么调整范围，都要写死。 二分猜数的每一步是：取当前范围的正中间数；大了就把上界改成它减一，小了就把下界改成它加一——没有任何一步需要【领会精神】。 这就是【明确】的标尺：换一个陌生人照着执行，结果完全一样。

二、有限：步数有个头

1~100 的范围每次砍一半：100 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1——最多 7 步见底。 算术根据：2 的 7 次方 = 128 > 100，所以 7 步足够把 100 个候选消灭光。 对比瞎猜：最坏 100 步。同样的问题，算法好坏差十几倍——这就是要点之间的差距。

三、反面教材：不明确与不有限

不明确的例子：【猜一个差不多的数】——机器无法执行； 不有限的例子：【随便猜，总有一天猜中】——步数没头，可能永远跑不完。 第三章讲过的死循环，就是【不有限】在代码里的样子。

四、动手 Demo：二分猜数实战

猜 1~100 里的数 73，把每一步的范围收缩打印出来。

# 二分猜数: 每次砍一半
lo, hi, target = 1, 100, 73
count = 0
while lo <= hi:
    mid = (lo + hi) // 2
    count += 1
    if mid == target:
        break
    elif mid < target:
        lo = mid + 1
    else:
        hi = mid - 1
print("猜了", count, "次猜中")

实跑输出：

--------------------------------------------------------------------
要点 1——步骤明确且有限：二分猜数
--------------------------------------------------------------------

猜 1~100 之间的数。瞎猜最坏 100 次；聪明的算法【每次砍一半】：

  第几次猜     猜的数     对方回应     剩余范围
  ----------------------------------------------
  1            50         小了         51~100
  2            75         大了         51~74
  3            62         小了         63~74
  4            68         小了         69~74
  5            71         小了         72~74
  6            73         对了!        1 个数

73 是个偏大的数，但瞎猜平均要 50 次——二分只要 7 次内必中。
这就是【步骤明确且有限】的威力：明确＝每步怎么缩小范围写得清清楚楚；
有限＝1~100 无论多倒霉，最多 7 步（2 的 7 次方 = 128 > 100）必然结束。

最多 7 次＝log2(100) 向上取整——范围每步减半，步数就是对数。 教材的下一个例子（5.3 的找卡片）会继续用【机械】视角拆解这类步骤。

30 秒实验

  1. 用二分猜数法让朋友出题，亲口报 7 次以内猜中——体验对数的力量。
  2. 想想 1~1000 需要几次？（10 次——2 的 10 次方 1024）

常见误区

  1. 以为算法只要【大概对】——必须每一步都无歧义，否则机器无法执行。
  2. 以为步数多是小事——不有限的算法就是死循环，永远交不了卷。
自测三问（点开对答案） 1. 要点 1 的两条底线是什么？ —— 步骤明确（无歧义）、步骤有限（有尽头）。 2. 1~100 用二分最多猜几次？为什么？ —— 7 次——每次范围减半，2 的 7 次方 128 已超过 100。 3. 【不有限】在程序里是什么样子？ —— 死循环——终止条件永远不满足，程序跑不完。

相关笔记