《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一一对应。分治主文给出的两条总纲领是全部习题的理论地基分解将原问题递归地拆成两个或多个规模更小的子问题直到最小子问题合并从已知的最小子问题解出发自底向上合并子问题的解得到原问题的解。以及判断任务是否适合分治的三个准则在自测题中将被逐条检验可分解原问题能递归地拆成更小且相似的子问题子问题相互独立子问题互不重叠、互不依赖解可合并子问题的解能合并出原问题的解。二、自测题一三道任务谁适合分治假设一名学生想用切成两半 → 分别求解 → 合并结果的方式处理以下任务要求为每题给出结论并说明理由。判定基准分治为什么能省事主文曾用一个不等式说明分治的收益对长度为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.pyC 版见 fast_power.cppGo 版见 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 2n 2时求n // 2 1n 1时求n // 2 0而n 0触发基准情形返回 1不再下降。注意这里用的是整除n // 2奇数指数会被安全地降一半。问题 2自最深层起逐层返回什么递归返回值是自底向上产生的把三层计算完整展开如下层自底向上half的来源奇偶判断返回值n 0——基准情形1n 1fast_pow(3, 0) 1奇数1 × 1 × 3 3n 2fast_pow(3, 1) 3偶数3 × 3 9n 5fast_pow(3, 2) 9奇数9 × 9 × 3 243最终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]当前子树在中序中的索引区间。对象根在先序中的索引子树在中序中的区间当前树i[l, r]左子树i 1[l, m - 1]右子树i 1 (m - l)[m 1, 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 * xC 版的关键在于题点提示取负前先把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); }三个关键设计点基准情形n 0直接返回 1它同时是x 0, n 0时的约定结果只递归一次half保存x^(n//2)偶数指数返回half * half奇数指数再补乘一次x——严格对应自测题二对禁止两侧重复递归的要求负数指数先取倒数x → 1/x再取正n → -n本质上把x^n改写为(1/x)^(-n)在 C/Java 等定长整型语言中必须用long long承接取负否则最小 32 位整数会溢出成未定义行为。时间O(log n)、递归栈O(log n)。六、在仓库中实际运行与验证以上代码均可在本仓库对应语言目录下直接查看并运行无需修改任何仓库文件Pythonfast_power.py 自带__main__断言块直接运行python3 fast_power.py即可校验fast_pow(7, 0) 1、fast_pow(3, 5) 243、fast_pow(2, 6) 64Cfast_power.cpp 在main()中通过assert校验相同三组用例且已被登记进该章的构建清单 CMakeLists.txtadd_executable(fast_power fast_power.cpp)按该章常规方式配置 CMake 后即可编译执行C 版见 fast_power.cGo除 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考