企业官网建设流程全解析

《Hello 算法》分治策略习题精讲：三道自测题与快速幂编程实战

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文基于开源仓库《Hello 算法》俄文版分治章（ru/docs/chapter_divide_and_conquer/exercises.md）的习题展开成文。分治（"разделяй и властвуй"，divide and conquer）是贯穿全书最重要的算法思想之一，习题册把抽象的思想拆解为三类可验证的训练：判定任务是否适用分治、追踪快速幂递归的执行过程、仅凭先序与中序序列在根层切分二叉树。读完本文，你将掌握"能否分治"的三条判据、自底向上的递归追踪方法，以及一道可迁移到工程代码中的x^n完整实现。

一、习题文档在全章中的位置

本习题文档是该章 divide_and_conquer.md 主文的配套练习，延续了 Hello 算法各章统一的"自测题（Вопросы для самопроверки）+ 编程题（Задачи по программированию）"体例。自测题按"先独立尝试、再对照折叠答案"设计，原文中每道题都带有可展开的答案区（??? success "Ответ"），与主文的分治三判据、复杂度分析（divide_and_conquer.md）一一对应。

分治主文给出的两条总纲领是全部习题的理论地基：

1. 分解：将原问题递归地拆成两个或多个规模更小的子问题，直到最小子问题；
2. 合并：从已知的最小子问题解出发，自底向上合并子问题的解，得到原问题的解。

以及判断任务是否适合分治的三个准则（在自测题中将被逐条检验）：

• 可分解：原问题能递归地拆成更小且相似的子问题；
• 子问题相互独立：子问题互不重叠、互不依赖；
• 解可合并：子问题的解能合并出原问题的解。

二、自测题一：三道任务谁"适合分治"

假设一名学生想用"切成两半 → 分别求解 → 合并结果"的方式处理以下任务，要求为每题给出结论并说明理由。

判定基准：分治为什么能"省事"

主文曾用一个不等式说明分治的收益：对长度为n的数组做朴素冒泡排序约需O(n²)次操作；若在中间切一次，则切分约O(n)、两半各O((n/2)²)、合并约O(n)，总开销为O(n²/2 + 2n)。当n > 4时，切分后的操作数严格更少（对应示意图 divide_and_conquer_bubble_sort.png）。递归地把每一半继续二分下去，就得到时间复杂度O(n log n)的归并排序。这道判定题正是要你复用这条"减少总工作量"的逻辑。

题 1：对无序数组排序 —— 适合分治

结论：适合。数组从中点切成两半后，左右两半可互相独立地各自完成排序，最后用一次O(n)的有序合并即可拼出完整有序数组——这正是归并排序。它的分解、独立、合并三条判据全部满足：数组递归二分直至单元素（最小子问题），再自底向上两两合并有序段。

题 2：找数组中的最大元素 —— 可切分但不减少总工作量

结论：切分可行，但不能降低总工作量。即便把数组切为两半、分别在两半里找最大值，两半合计仍然要把全部n个元素各比较一遍；最后还需要一次额外的"两半最大值比大小"。因此总工作量与直接一趟扫描相同，仍是O(n)。切分没有带来渐近收益，也没有并行以外的实际价值。

题 3：依次执行栈操作push(x)/pop()并打印每次pop结果 —— 两半无法独立求解

结论：不适合，两半无法独立求解。栈是后进先出结构，第二段操作开始时栈的内容（以及每一步pop弹出来的元素）完全取决于第一段操作留下的栈状态。若把操作序列硬切成两半、互不通信地"独立"执行，第二段的模拟结果必然是错的。这正好触发了三判据中的第二条——子问题不独立，属于典型的"不可分治"反例。

主文还补充过两个与判定相关的深化视角：其一，分治不仅能降低操作次数，还能天然适配并行计算——独立子问题可交由多核同时求解，例如桶排序中每个桶可单独并行排序再汇总（divide_and_conquer_parallel_computing.png）；其二，二分查找、快速排序、树与堆的操作、汉诺塔、最近点对、Karatsuba 大数乘法、Strassen 矩阵乘法、逆序对计数等经典问题背后都藏着这条"静默"的分治线索。

三、自测题二：亲手追踪快速幂fast_pow(3, 5)

分治不仅能组织排序，还能把"计算x^n"这种看似平凡的任务从O(n)降到O(log n)。习题给出仓库中分治快速幂的递归实现，让你在x = 3, n = 5下逐步推演。仓库内的基准实现位于 fast_power.py，C++ 版见 fast_power.cpp，Go 版见 fast_power.go。三者的逻辑完全一致（以 Python 版为例）：

def fast_pow(x: int, n: int) -> int: """Быстрое возведение в степень（快速幂）""" if n == 0: return 1 half = fast_pow(x, n // 2) # 只递归一次，先存进 half if n % 2 == 0: return half * half return half * half * x

问题 1：参数n沿递归调用依次取何值

沿着"每次把指数折半"的递归链，n的取值序列为：

5 → 2 → 1 → 0

因为n = 5时求n // 2 = 2，n = 2时求n // 2 = 1，n = 1时求n // 2 = 0，而n = 0触发基准情形返回 1，不再下降。注意这里用的是整除n // 2，奇数指数会被安全地"降一半"。

问题 2：自最深层起逐层返回什么

递归返回值是自底向上产生的，把三层计算完整展开如下：

最终fast_pow(3, 5) = 243，与基准实现内嵌的断言fast_pow(3, 5) == 243完全一致。

问题 3：为什么先存入half，而不是在乘号两侧各递归一次

这是本题的灵魂。"每层只递归一次"决定了O(log n)的复杂度：

• 若写成return fast_pow(x, n // 2) * fast_pow(x, n // 2)（或两侧各来一次），同一子问题会被重复求解。递归树每层节点翻倍，总调用次数约为O(n)——虽然有log n的深度，却做了大量重复计算，与朴素O(n)逐乘没有本质区别；
• 先half = fast_pow(x, n // 2)再复用它，每一层只产生一个递归调用、一次乘法翻倍。以n = 5为例总共只发生5 → 2 → 1 → 0四次调用。

因此正确写法的单层乘法开销是O(1)，递归深度约O(log n)，时间与栈空间复杂度均为O(log n)。这也是"合并子问题的解"这一分治原则在数学运算上的体现：x^5 = (x^2)² · x，上一层的解复用了下一层的解。

四、自测题三：只用先序+中序，在根层切分左右子树

给定一棵不含重复结点的二叉树（本题以字母标识结点），已知：

• 先序遍历（прямой обход）：[A, B, D, E, C]
• 中序遍历（симметричный обход）：[D, B, E, A, C]

本题只要求在根结点层完成划分，不必继续递归画整棵树。

问题 1：根结点是谁

先序遍历的第一个元素必然是整棵树的根。因此根结点是A。

问题 2：中序序列中左右子树各占哪一段

在中序序列里，根结点恰好位于中间，把序列切成两段：

[D, B, E] A [C] 左子树 右子树

所以中序中左子树对应[D, B, E]，右子树对应[C]。

问题 3：先序序列中左右子树各占哪一段，根的左右孩子是谁

先序的结构是[根 | 左子树 | 右子树]。由问题 2 可知左子树含 3 个结点，因此先序中紧跟根A之后的 3 个元素都属于左子树：

A [B, D, E] [C] 根 左子树 右子树

剩余元素[C]属于右子树。又因为先序中每棵子树的首元素就是该子树的根，可以立刻读出：根A的左孩子是B，右孩子是C。这个切分技巧被进一步推广后，正是"由先序+中序重建整棵二叉树"的经典分治问题（完整解法见 build_binary_tree_problem.md 与其实现 build_tree.py）。

仓库的完整重建实现用变量统一描述切分区间，可作为本题答案的"公式化版本"：

• i：当前子树根结点在先序中的索引；
• m：当前子树根结点在中序中的索引；
• [l, r]：当前子树在中序中的索引区间。

其中(m - l)即左子树结点数——它解释了为什么右子树根要先序跳过"根自己 + 全部左子树"。在本习题中，m - l对应的正是 3，于是先序里右子树起点落在C上。为快速定位m，完整实现还用哈希表预存中序"值 → 索引"的映射，最终整体时间与空间复杂度均为O(n)。

五、编程实战：实现x^n（不调用内置幂函数）

原文档的编程题（对应 LeetCode 第 50 题 "Pow(x, n)" 的同类要求，原文附有在线题目跳转按钮，此处不展开外链）完整陈述如下：

给定实数x与整数n，不借助内置幂函数计算x^n。采用分治递归：每次把指数折半，并复用已算出的子问题结果。约定x^0 = 1（包括x = 0时）；若n < 0，题目保证x ≠ 0，可将答案转化为(1/x)^(-n)。

参考实现

仓库中的fast_pow只覆盖了非负指数场景（三份断言测试均针对n ≥ 0），负数指数的兼容正是留给练习者的扩展点。以下给出可直接运行的完整版，Python 借助大整数天然免疫取负溢出：

def fast_pow(x: float, n: int) -> float: """计算 x^n：分治快速幂（支持负数指数）""" if n == 0: return 1.0 # x^0 = 1，含 x = 0 if n < 0: return fast_pow(1.0 / x, -n) # 题目保证此时 x != 0 half = fast_pow(x, n // 2) # 每层只递归一次 return half * half if n % 2 == 0 else half * half * x

C++ 版的关键在于题点提示：取负前先把n提升为 64 位整数，避免INT_MIN = -2^31取负时发生 32 位整型溢出：

/* 核心递归：n 已保证非负 */ double fastPowRec(double x, long long n) { if (n == 0) return 1.0; double half = fastPowRec(x, n / 2); return (n % 2 == 0) ? half * half : half * half * x; } /* 对外接口：先提升到 64 位，再处理负数指数 */ double fastPow(double x, int n) { long long N = n; // 关键：先转型再取负 if (N < 0) { x = 1.0 / x; N = -N; } return fastPowRec(x, N); }

三个关键设计点

1. 基准情形：n == 0直接返回 1，它同时是x = 0, n = 0时的约定结果；
2. 只递归一次：half保存x^(n//2)，偶数指数返回half * half，奇数指数再补乘一次x——严格对应自测题二对"禁止两侧重复递归"的要求；
3. 负数指数：先取倒数x → 1/x再取正n → -n，本质上把x^n改写为(1/x)^(-n)；在 C++/Java 等定长整型语言中必须用long long承接取负，否则最小 32 位整数会溢出成未定义行为。时间O(log n)、递归栈O(log n)。

六、在仓库中实际运行与验证

以上代码均可在本仓库对应语言目录下直接查看并运行，无需修改任何仓库文件：

• Python：fast_power.py 自带__main__断言块，直接运行python3 fast_power.py即可校验fast_pow(7, 0) == 1、fast_pow(3, 5) == 243、fast_pow(2, 6) == 64；
• C++：fast_power.cpp 在main()中通过assert校验相同三组用例，且已被登记进该章的构建清单 CMakeLists.txt（add_executable(fast_power fast_power.cpp)），按该章常规方式配置 CMake 后即可编译执行；C 版见 fast_power.c；
• Go：除 fast_power.go 外，该目录还单独维护了 fast_power_test.go，可在 Go 模块目录下用go test运行测试。

跑通基准实现后，即可把第五节中处理负数指数与 64 位转型的扩展移植回自己熟悉的语言，形成一套完整的"正数核心 + 边界防御"快速幂工具箱——这也正是分治习题"以练促学"的终点：把O(log n)的折半直觉内化成可随时调用的代码直觉。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo