循环是算法唯一的重复手段：让同一段代码跑很多遍。 最小的循环样板是累加三件套：先给零、挨个拿出来、加到总数上。 循环次数就是代价。能推出公式的，就别用循环。
第 3 章讲的是数据怎么摆。从这一章起开始写算法本身，第一块砖就是循环。 教材用「1 加到 100」当第一个例子，因为它是所有累加问题的最小样子。 这一篇的三件套，后面 4.2 到 4.4 全是它的变形。认准这三行，第 4 章就没有新东西了。
一、1 加到 100，三种写法
同一个问题，演示里写了三种解法：for 累加、while 累加、套公式。
前两种结果一样（5050），循环次数也一样（100 次）。它们其实是同一个算法，只是换了个写法。
第三种一次都不循环：(1 + 100) * 100 / 2。这是高斯小时候那个办法——首项加末项乘项数除以二。
三种写法都得到 5050，但只有第三种把「100 次」变成「0 次」。这就是算法和写法的区别。
二、累加器的三件套
演示里那三行，是这一章的全部家当：
total = 0 是先给一个零；for x in data 是挨个拿出来；total += x 是加到总数上。
这三行能变形成：求和、求平均、数个数、求最大最小、拼字符串、求有几个及格……
变形的办法只有一招：把第三行换成你要做的动作。求和是 total += x，
求最大是 if x > best: best = x，数个数是 n += 1。
所以看到任何「逐个处理一批数据」的题，先写出这三行，再把中间那行改掉。
这一招能顶掉第 4 章大半的题。
三、循环次数就是代价
演示里有张表：n 是 100 就跑 100 次，n 是 100 万就跑 100 万次，而套公式永远是 0 次。 这就是为什么循环不是免费的。每多跑一次，就多花一次时间。 后面排序那一章会反复用这个说法：冒泡排序要比多少次、快排要比多少次，比的就是循环总次数。
要注意的是「0 次」不代表没成本——公式本身也要算，只是那点成本跟 n 无关。跟 n 无关就是快。
四、什么样的循环会写错
演示里列了三种错法，都是新手原样踩过的：
| 错法 | 写出来的样子 | 结果 |
|---|---|---|
| 少加一个 | range(1, n) |
加到 99，少 100 |
| 多加一个 | range(1, n + 2) |
多加了 101 |
| 漏了初值 | 忘了 total = 0 |
上一轮的结果还在 |
第一种最典型：range(1, 100) 得到 4950，比正确答案少 100，因为 Python 的 range 含头不含尾。
差别只在边界那一个数。这就是第 3.6 讲的差一错在下标之外的另一个面孔——它不在数组里，在范围里。
第三种更阴：忘了初值，total 里还留着上一次调用的结果，跑一次是对的、跑两次就翻倍。
这种错在测试里只跑一次根本发现不了。
五、算完拿另一个办法验一遍
演示最后那句建议值得单拎出来：算完用另一个办法验一遍。 循环算得 5050，公式也算得 5050——两个独立的办法给同一个答案，基本可以放心。 这不是多余的谨慎。 循环里的边界错只差一个数，不报错、不显眼，只在总数对不上时才被发现， 而那时已经很难查是哪一环出的错。
工程上这套做法有个名字：交叉验证。第 1 章说的「好算法要能验证」，落到手上就是这一句。
六、动手 Demo：1 加到 100：三种写法，三次结果
先用 for 和 while 各加一遍，再套公式算一遍，三个结果应该完全一样。
然后故意把 range(1, 100) 写成少一个，看差多少。
最后把三种写法的循环次数列成表。
N = 100
total = 0
for x in range(1, N + 1):
total += x
print('for ', total)
total, i = 0, 1
while i <= N:
total += i
i += 1
print('while ', total)
print('公式 ', (1 + N) * N // 2)
total = 0
for x in range(1, N):
total += x
print('少一个', total, '差', 5050 - total)
实跑输出：
--------------------------------------------------------------------
循环：算法的基础
--------------------------------------------------------------------
① 从 1 加到 100，三种写法
--------------------------------------------------------------------
| 写法 | 循环几次 | 结果 |
|---|---:|---:|
| for 累加 | 100 | 5050 |
| while 累加 | 100 | 5050 |
| 套公式 | 0 | 5050 |
前两种写法一模一样的结果，也一样的慢：要加 100 次。第三种一次都不循环。
② 累加器的固定三件套
--------------------------------------------------------------------
total = 0 1. 先给一个零
for x in data: 2. 挨个拿出来
total += x 3. 加到总数上
这三行能变形出：求和、求平均、数个数、求最大最小、拼字符串……
后面 4.2 到 4.4 全是这三行的变形。认准它，第 4 章就没有新东西了。
③ 循环次数就是代价
--------------------------------------------------------------------
| n 的大小 | 累加要跑几次 | 套公式要跑几次 |
|---:|---:|---:|
| 100 | 100 | 0 |
| 10000 | 10000 | 0 |
| 1000000 | 1000000 | 0 |
所以循环不是免费的。能推出公式的，就别用循环——这是「会写代码」和「会算」之间的分界线。
④ 什么样的循环会写错
--------------------------------------------------------------------
| 错法 | 写出来的样子 | 结果 |
|---|---|---|
| 少加一个 | range(1, n) | 加到 99，少 100 |
| 多加一个 | range(1, n + 2) | 多加了 101 |
| 漏了初值 | 忘了 total = 0 | 上一轮的结果还在 |
写成 range(1, 100) 的结果：4950，正确是 5050，差 100
差的那一个数，往往不报错、不显眼，只在总数对不上时才被发现。
这就是为什么算完要拿另一个办法验一遍——套公式就是这个「另一个办法」。
①range(1, N + 1) 才是 1 到 100。range 含头不含尾，这是必须记住的一条。
②while 那版多了两句：i = 1 和 i += 1。
for 其实是 while 的简化写法，省掉了自己维护计数器。
③公式那版用了 // 而不是 /。因为两个整数相加乘起来一定是偶数，整除不会丢东西，而且结果是整数。
④最后一行输出少 100。差的那一个数不报错，这就是为什么算完要验一遍。
30 秒实验
- 把
range(1, N + 1)改成range(0, N)，结果差多少？差在哪一头？ - 用累加三件套算 1 到 100 里所有偶数的和，第三行要怎么改？
- 算 1 到 100 的乘积（阶乘的简化版），想想答案会大到什么程度。
常见误区
- 「for 和 while 是两种算法。」同一个算法两种写法。算法说的是步骤，不是语法。
- 「循环写得越短越快。」快慢看循环次数，不看代码行数。
- 「套公式是投机取巧。」它是同一个问题的另一个解法，次数从 n 降到 0，这就是算法的价值。
自测三问（点开对答案）
1. 累加三件套是哪三行？ —— `total = 0` 给零、`for x in data` 挨个取、`total += x` 累加。换第三行就换功能。 2. `range(1, 100)` 为什么少了 100？ —— `range` 含头不含尾，只到 99。要 1 到 100 得写 `range(1, 101)`。 3. 为什么算完要用另一个办法验一遍？ —— 循环的边界错只差一个数，不报错。两个独立办法给同一个答案才靠得住。三件套会写了，接下来把它套到一批真数据上。 下一节拿一年的营业额练手，顺手把切片和二维数组都用上。
- ☐ （本篇完，下一篇 4.2 用数组处理大量数据）