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

斐波那契数列的规律是【每项等于前两项之和】；查表法把反复算的东西提前算好——规律是算法提速的两大法宝之一。

📝 本节和前面几节的关系

要点 5 的【高斯公式】就是规律的功劳，这一节把【找规律】本身当成一项正经手艺来练。

一、数列里的规律：斐波那契

1, 1, 2, 3, 5, 8, 13……规律：每项＝前两项之和。 找到规律后，第 100 项不需要从头数——顺着规律递推即可；这个数列在自然界（花瓣、鹦鹉螺）与计算机（斐波那契堆、黄金分割搜索）里处处露面。 找规律的手法：先看相邻项差（+0+1+1+2+3），再看相邻项关系（前两项相加）——差分与递推是两把万能钥匙。

二、规律变现：查表法

把反复计算的东西提前算好存成表，用时一次查找——平方表、三角函数表、乘法口诀，本质相同。 早期 CPU 没有乘法电路，乘法全靠查表或连加；今天查表思想仍活在【缓存】里（第五章缓存服务器存的就是网页的【表】）。 规律＋查表的组合拳：先发现【平方只跟自己有关】（规律），再决定【预先算好】（查表）。

三、找规律是思维习惯

拿到重复计算先问：结果之间有没有依赖？有没有上限？能不能提前算？ 三问都答上来，算法就从【埋头硬算】升级成【借力打力】——这正是要点 5 与要点 6 的合流。

四、动手 Demo：斐波那契递推与平方查表

两个小实验：递推生成斐波那契数列、造平方表代替乘法。

# 斐波那契: 每项 = 前两项之和
a, b = 1, 1
for i in range(6):
    a, b = b, a + b
print("数列推进到:", a, b)
# 查表代替乘法
sq = [i * i for i in range(21)]
print("查表: 13^2 =", sq[13])

实跑输出：

--------------------------------------------------------------------
要点 6——找出数字间的规律
--------------------------------------------------------------------

规律一来，账就省了。两道例题：

[例 1] 数列找规律: 1, 1, 2, 3, 5, 8, 13, ...
    规律: 每个数 = 前两个数之和 (斐波那契数列)
    前 8 项: 1, 1, 2, 3, 5, 8, 13, 21
    有了规律, 第 100 项不用回头数, 沿着规律推就行

[例 2] 查表代替计算: 算平方太慢就先造一张平方表
    先造表: 1^2=1 ... 20^2=400 (存进数组)
    之后查 13^2 = 169 <- 一次查找, 不用乘法

规律和查表是算法提速的两大法宝：**把反复算的东西提前算好**。
第五章的兄弟教材《算法图解》整本书都在玩这两个思路。

a, b = b, a + b 一行完成【滚动推进】——递推规律的代码往往只有一行核心。 查表的代价是内存（存表），收益是时间（不计算）——用空间换时间，这是算法世界的通用汇率。

30 秒实验

  1. 手推斐波那契数列第 10 项（答案 55），再用代码验证。
  2. 造一张立方表（1~10 的立方），查 7 的立方——体会【空间换时间】。

常见误区

  1. 以为找规律是数学家的专利——差分与递推两招就能对付大多数数列。
  2. 以为查表过时了——缓存、索引、预计算，全是查表的现代马甲。
自测三问（点开对答案） 1. 斐波那契数列的规律是什么？ —— 每项等于前两项之和（1, 1, 2, 3, 5, 8, 13…）。 2. 查表法用什么东西换什么？ —— 用内存空间换计算时间——提前算好，用时查找。 3. 找规律的两把万能钥匙？ —— 看相邻项的差（差分）、看项与项的递推关系。

相关笔记