2026年秋第4次课

本课围绕汉诺塔、快速幂、合并排序、逆序对、木材加工和费解的开关，讨论同一个问题：怎样利用问题的结构，减少需要直接处理的工作？

先用汉诺塔复习递归任务与调用顺序，再从问题分解的角度重新理解快速幂；接着通过合并排序与逆序对学习子问题结果的合并，最后通过木材加工和费解的开关，比较利用单调性排除候选与利用约束减少枚举的两种方法。各题的完整 Python 实现、执行过程和交互动画见对应题目链接。

本课的分析主线

分析每道题时，依次回答以下问题：

1. 任务是什么？ 明确输入、输出与合法条件，区分求一个数、输出全部过程和寻找最优方案。
2. 问题怎样变小？ 明确规模参数及缩小规则，例如圆盘数减1、指数减半、数组分成两段或候选区间缩小。
3. 小问题提供什么信息？ 是一个幂值、一段有序列表、一个计数，还是一次可行性判断？
4. 怎样得到当前答案？ 说明合并、复用、排除或状态推导的依据，并证明不遗漏正确结果。
5. 总工作量是多少？ 同时考虑子调用数量、每次调用的额外工作，以及最终输出量。

递归是函数调用自身的实现方式；分治是分解问题并利用子问题结果求解的设计思想。同一种分治思路可以用递归实现，看到递归代码时，还需要进一步说明它利用了什么问题结构。

本课将快速幂放在广义的分治框架中讲解。它把幂表达式分解后复用一个较小幂值，实际只进行一次递归子调用；若采用“分治求解多个子问题、减治只求解一个子问题”的分类，它也具有减半减治的结构。合并排序则需要分别求解左右两个不同的子问题。分类的依据与实际调用数量要说清楚。

一 汉诺塔 先定义递归任务

详细题解与动画：汉诺塔。

有三根柱子 A、B、C，要借助B将A上的 $n$ 个圆盘移到C，每次只能移动一个圆盘，且大盘不能放在小盘上。先把递归函数的任务定义完整：借助辅助柱，将源柱上最上面的 $n$ 个圆盘合法地移到目标柱。

从最大圆盘推导操作顺序

要移动最大圆盘，必须先移开它上面的圆盘，因此整个任务分成三个按顺序执行的步骤：

阶段	当前要完成的任务	对应规模
1	借助C，将上面的圆盘从A移到B	$n-1$ 个圆盘
2	将最大圆盘从A移到C	一次移动
3	借助A，将上面的圆盘从B移到C	$n-1$ 个圆盘

当 $n=1$ 时，直接从源柱移到目标柱。两个子任务虽然规模相同，但源柱、辅助柱和目标柱的角色不同；第3阶段还依赖前两个阶段完成后的状态，必须顺序执行。

正确性的关键是：先假设较小规模的任务能合法完成，当前层就能够移开小盘、移动大盘、再将小盘移到大盘上。终止条件与这一推导共同保证整个移动过程合法。

区分移动次数与调用深度

最少移动次数满足：

$$M(1)=1,\qquad M(n)=2M(n-1)+1\quad(n\geq2).$$

对任意合法方案，移动最大圆盘之前必须移开小盘，最终还必须把小盘移到目标柱；这给出了两个较小任务加一次大盘移动的下界，递归方案恰好达到它。

展开递推式得到 $M(n)=2^n-1$。以3个圆盘为例，整个过程分成“前3步、第4步、后3步”，第4步将3号圆盘从A移到C，总共7步。若任务要求输出全部移动记录，仅输出就有指数数量的工作，时间为 $O(2^n)$；同一时刻的递归栈只沿一条调用链展开，辅助空间为 $O(n)$。

课堂上需要区分“输出全部移动”“只求最少次数”和“查询指定步骤”。它们的输出要求不同，不能直接套用同一个复杂度结论。

衔接快速幂： 汉诺塔每层需要执行两个不同角色的子任务。求幂时也会出现两个较小幂的乘积，这两个幂是否一定要分别求解？

二 快速幂 从递归调用转向问题分解

详细题解与动画：二分法求幂（快速幂）。

前面从递归调用与返回的角度理解了求 $a^n$。本次从分解与合成的角度分析：先找到怎样由较小规模的幂得到当前幂，再决定需要进行几次子调用。

用幂的性质缩小规模

设 $n$ 为非负整数，$k=\lfloor n/2\rfloor$。当指数大于1时：

$$a^{2k}=(a^k)^2,\qquad a^{2k+1}=(a^k)^2\cdot a.$$

因此，先求出 half = a^k，当前层只需平方；若指数为奇数，再补乘一次底数。边界为 $a^0=1$、$a^1=a$，其中 $0^0$ 沿用题目约定返回1。

表达式中两处 $a^k$ 的参数完全相同，只需计算一次并保存结果。这与汉诺塔的两次子任务不同：汉诺塔的柱子角色和操作时机不同，不能复用同一段移动过程。

分析对象	汉诺塔	快速幂
子问题规模	两个 $n-1$	一个 $\lfloor n/2\rfloor$
子任务是否相同	柱子角色不同	两处半次幂是同一个值
如何利用子问题	按先后顺序分别执行	求一次，再复用结果
当前层的操作	移动最大圆盘	平方，并按奇偶补乘底数

用同一例子检查分解与合成

求 $2^{13}$ 时，调用指数依次为 13 → 6 → 3 → 1。返回时依次得到：

$$2\ \longrightarrow\ 2\times2\times2=8 \ \longrightarrow\ 8\times8=64 \ \longrightarrow\ 64\times64\times2=8192.$$

按照题目文档中指数为1时直接返回的递归实现，这个例子进行了5次乘法。直接将13个2连续相乘需要12次乘法。

采用一次算术操作为常数时间的课程计数模型，运行时间满足：

$$T(n)=T(\lfloor n/2\rfloor)+O(1).$$

递归时间与辅助空间均为 $O(\log(n+2))$。若把相同的半次幂递归求解两次，就会出现重复计算，时间退化到线性级。Python 大整数的实际乘法成本还取决于整数位数，不能由乘法次数直接断言实际运行时间始终是对数级。

衔接合并排序： 快速幂复用了同一个子问题。如果左右子问题的内容不同，必须分别求解，合并操作又不再是常数工作量，会发生什么变化？

三 合并排序 分别求解并合并有序结果

详细题解与动画：合并排序。

合并排序将列表按位置分成左右两段。两段包含不同的元素，要分别排序；两个子调用返回后，再把两个有序列表合并为当前列表的有序副本。

长度不超过1时，列表已经有序。对更大的列表，合并时比较两侧第一个尚未取出的元素，取较小者并移动对应索引；一侧耗尽后，接上另一侧剩余元素。相等时先取左侧，保持稳定性。

正确性分成两个层次：子调用保证左右分别有序；双指针合并保证每次取出的都是剩余元素中的最小值。因此，合并结果有序且包含原来的全部元素。

对照快速幂分析工作量

以 [5, 2, 3, 1] 为例，左右子调用分别返回 [2, 5] 和 [1, 3]，最后合并为 [1, 2, 3, 5]。

对于 $n$ 个元素，时间递推式为：

$$T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+O(n).$$

它与快速幂有两处差别：左右都要递归求解，当前层还需要线性时间合并。每层总工作量为 $O(n)$，共有 $O(\log n)$ 层，所以时间为 $O(n\log n)$。列表存储的峰值为 $O(n)$，调用栈深度为 $O(\log n)$，总辅助空间为 $O(n)$。

这里的 $n$ 是元素个数，快速幂中的 $n$ 是指数。规模参数的含义与每层工作量都必须明确，不能只根据“每次减半”判断复杂度。

衔接逆序对： 合并时已经知道左右各自有序，是否可以利用当前比较，一次判断多个元素之间的关系？

四 逆序对 在合并过程中批量统计

详细题解与动画：逆序对。

逆序对要求原位置 $i<j$ 且数值 $a_i>a_j$。将序列按原位置分成左右两段后，逆序对分为三类：左段内部、右段内部和跨越左右两段。前两类由子调用统计，第三类由当前合并统计，三类互不重叠。

为什么取右侧时能批量计数

设 i、j 是两个有序段的当前索引。如果 left[i] > right[j]，左段从 i 开始的全部剩余元素都大于 right[j]；这些元素的原位置又都在右段元素之前。因此，取出这个右侧元素时，新增逆序对数为 len(left) - i。

如果 left[i] <= right[j]，取左侧且不增加计数。特别是数值相等时不构成逆序对，不能误走计数分支。

沿用合并排序的例子 [5, 2, 3, 1]：

计数来源	对应配对	数量
左段 [5, 2] 内部	(5, 2)	1
右段 [3, 1] 内部	(3, 1)	1
合并 [2, 5] 与 [1, 3]	取1时计入 (2, 1)、(5, 1)；取3时计入 (5, 3)	3
原序列总计	左段计数＋右段计数＋跨段计数	5

排序过程改变了各段内部的排列，但没有改变元素属于哪一个原始位置区间，段内计数也已经由子调用保存。因此，合并时仍然能正确统计原序列中的跨段配对。

与合并排序相比，新增的批量计数每次只做常数次操作，时间仍为 $O(n\log n)$，辅助空间仍为 $O(n)$。这里统计的是数量；如果逐个输出全部逆序对，输出量本身最坏可达平方级。

衔接木材加工： 合并排序与逆序对都要获得左右两段的结果。另一些问题只需做一次判断，就能排除一半候选，不必分别求解两边。

五 木材加工 利用单调性二分答案

详细题解与动画：木材加工。

给定若干根原木，要切出至少 $k$ 段等长木材，求最大的整数段长。不同原木的剩余部分不能拼接，因此检查候选长度 $x\geq1$ 时，可切段数为：

$$C(x)=\sum_{i=1}^{n}\left\lfloor\frac{L_i}{x}\right\rfloor.$$

候选长度可行的条件是 $C(x)\geq k$。段长越大，每根原木能切出的段数越少或不变，故 $C(x)$ 单调不增，可行候选在较小长度一侧。

根据判定结果保留可能更优的候选

在 [1, M] 中二分，其中 $M$ 是最长原木长度：

• 当前长度可行，先记录它，再检查更大的长度。
• 当前长度不可行，它及所有更大的长度都不可行，继续检查较小的一侧。

候选区间每轮缩小，而且只排除不可能产生更优答案的候选；区间清空时，已经记录的最大可行长度就是答案。若从未找到可行的正整数长度，返回0。

原木为 [232, 124, 456]、$k=7$ 时，长度114能切出 2 + 1 + 4 = 7 段，长度115只能切出 2 + 1 + 3 = 6 段，结合单调性可确认最大长度为114。

判定要求“至少”，不能要求“恰好”。例如原木 [8, 8]、$k=3$，长度4能切4段，可以只取3段；长度5只能切2段，所以答案为4。

与前面几种减小规模的方法对照

木材加工缩小的是候选答案区间，每轮只保留可能包含更优答案的一侧；它依靠单调性进行二分答案，不需要把左右区间的解再合并。快速幂缩小的是指数，并通过代数运算合成答案；合并排序则分别求解两个位置区间。

一次判定最多扫描 $n$ 根原木，总时间为 $O(n\log(M+1))$，循环实现的辅助空间为 $O(1)$，不包含输入列表的存储。不能只把二分轮数当作总时间，因为每轮还要计算可切段数。

衔接费解的开关： 缩小候选范围还可以依靠问题约束。如果少量初始选择确定后，后续操作就被唯一确定，是否还需要枚举所有位置？

六 费解的开关 枚举初始选择再逐行推导

详细题解与动画：费解的开关。

在 $5\times5$ 的棋盘上，按开关会翻转自身和上下左右有效邻格。目标是以最少操作使所有灯全亮；只有最少次数不超过6时输出该次数，否则输出 -1。

每个开关按两次会抵消，所以只需考虑按或不按。直接枚举25个位置有 $2^{25}$ 种选择；本题进一步利用逐行影响的规则，只枚举第一行的 $2^5=32$ 种按法。

第一行确定后 后续选择被强制确定

第一行按法固定后，若第一行某格仍灭着，在保留既定第一行按法的前提下，只有按它正下方的开关才能修正它。于是第二行的按法被确定。

同样，扫描第二行时，为保持已经处理好的第一行不再变化，只能按第三行的对应开关；依此向下。前四行处理完毕后，最后一行没有下一行可用于修正，只能检查是否全亮。

任意成功方案都有一种第一行按法，算法会枚举到它；该第一行按法对应的后续操作又被逐行唯一确定。因此，只枚举第一行不会漏掉成功方案。比较所有成功方案的操作次数，才能得到最少次数。

这里第一行按法决定的是整个开关选择向量。翻转操作的先后顺序不会改变最终状态，可以按从上到下的顺序组织模拟；“不回头改变已处理行”是这个逐行算法的组织规则。

用样例核对操作与目标

样例第一组的一个最优方案按下第1行第1列、第3行第3列、第5行第5列，共3次，最终全亮。这些位置在动画的0开始编号中分别为 (0, 0)、(2, 2)、(4, 4)。

这一算法属于枚举第一行选择，再递推后续操作，没有分别求解两个半棋盘并合并结果，也不依赖候选按法的单调性。

若推广为边长 $m$ 的棋盘，第一行有 $2^m$ 种选择，每种选择需要 $O(m^2)$ 工作，总时间为 $O(2^m m^2)$、辅助空间为 $O(m^2)$。本题固定 $m=5$，每组只需处理32种第一行按法；这个优化利用了规则，并没有消除一般规模下第一行枚举的指数增长。

方法比较与课堂核对

下面比较的是各题链接中本课使用的实现。算术操作采用课程常用的单位成本模型，辅助空间不包含输入存储；合并排序和逆序对的对数级结论针对至少两个元素。

题目与任务	缩小范围或规模的依据	如何得到答案	时间复杂度	辅助空间
汉诺塔，递归输出全部移动	移动大盘前后各有一个 $n-1$ 盘任务	按顺序执行两个子任务及一次大盘移动	$O(2^n)$	$O(n)$
快速幂，递归求幂值	幂的性质，指数减半	半次幂求一次，平方并按需补乘	$O(\log(n+2))$	$O(\log(n+2))$
合并排序	按位置分成两段	合并两个有序列表	$O(n\log n)$	$O(n)$
逆序对，只求数量	按位置分段，利用段内有序	左段＋右段＋跨段计数	$O(n\log n)$	$O(n)$
木材加工，循环二分答案	可切段数随段长单调不增	保留可能更优的候选长度	$O(n\log(M+1))$	$O(1)$
费解的开关，边长 $m$	第一行选择确定后续按法	枚举第一行，逐行推导并取最小次数	$O(2^m m^2)$	$O(m^2)$

各行的规模参数含义不同：汉诺塔的 $n$ 是圆盘数，快速幂的 $n$ 是指数，排序与逆序对的 $n$ 是元素数，木材加工的 $n$ 是原木数量、$M$ 是最大原木长度，开关的 $m$ 是棋盘边长。

本课要形成的判断习惯是：先明确任务和状态，再说明缩小问题或排除候选的依据，最后根据实际执行结构分析工作量。递归深度、候选数量、比较次数和输出量是不同的计数对象。

课堂核对题

1. 汉诺塔的两个规模为 $n-1$ 的子任务，为什么不能像快速幂那样求一次后复用？
2. 快速幂和合并排序都把规模约减半，为什么一个是对数级，一个是 $O(n\log n)$？
3. 对 [5, 2, 3, 1]，顶层合并新增多少个逆序对，原序列总共有多少个？
4. 木材加工发现某个长度恰好能切出 $k$ 段时，能否立即停止二分？
5. 费解的开关为什么只枚举第一行？为什么还要检查最后一行并比较操作次数？

参考答案

1. 汉诺塔两次子任务的柱子角色不同，并有操作先后和状态依赖，必须分别执行。快速幂中的两处半次幂参数相同，求出一个值后可复用。
2. 快速幂每层只有一次子调用和常数次算术操作；合并排序需要求解两个不同子问题，并用线性时间合并。只看规模减半或递归深度不能判断总时间。
3. 顶层新增3个，分别为 (2, 1)、(5, 1)、(5, 3)；左段和右段各1个，总计5个。
4. 不能。当前长度可行，但更大的长度可能仍然可行；需记录当前答案并继续向右搜索，直到排除所有更优候选。
5. 第一行按法固定后，为修正上一行而按下一行的操作被唯一确定。最后一行只能检验，不能再向下修正；所有成功方案还要比较次数，并按最多6次的要求决定输出最小次数或 -1。

相关导学：算法概览、递归与分治。