12.6 练习¶
12.6.1 知识巩固¶
1. 哪些任务适合分治¶
一位同学想用“先分成两半，分别解决，再合并结果”的方法完成以下任务。 请分别判断它们是“适合分治”“可以分治，但不会减少总工作量”还是“两半不能独立解决”，并说明理由。
- 将一个无序数组排序；
- 求一个数组中的最大值；
- 按顺序执行一串
push(x)、pop()栈操作，并输出每次pop()得到的元素。
参考答案
- 适合：对半分解、两半独立排序、\(O(n)\) 合并——这正是归并排序。
- 可以分治，但不会减少总工作量：左右两半仍需合计检查全部 \(n\) 个元素， 和直接扫描一样都是 \(O(n)\) 时间。
- 两半不能独立解决：后半段开始时的栈内容取决于前半段执行结果， 两半不能在互不知道结果时独立完成。
2. 快速幂是怎样减少计算的¶
下面的递归函数用分治计算 \(x^n\)：
def fast_pow(x, n):
if n == 0:
return 1
half = fast_pow(x, n // 2)
if n % 2 == 0:
return half * half
return half * half * x
用它计算 fast_pow(3, 5)：
- 递归调用时，参数
n依次变成哪些值？ - 从最深层开始返回时，各层依次返回什么值？
- 为什么要先保存
half，而不是把fast_pow(x, n // 2)写两遍？
参考答案
-
参数依次为
5 → 2 → 1 → 0，每次都把指数减半，直到到达终止条件。 -
n = 0时返回 1；n = 1时返回 \(1×1×3=3\)；n = 2时返回 \(3×3=9\)；n = 5时返回 \(9×9×3=243\)。 -
如果把
fast_pow(x, n // 2)在乘法两边各写一次，两次递归会计算完全相同的子问题。 先把结果保存为half，每层就只递归一次，递归深度约为 \(\log n\)； 调用两次会造成大量重复计算。
3. 从遍历序列拆分左右子树¶
一棵没有重复节点的二叉树，其前序遍历和中序遍历分别为：
- 前序遍历：
[A, B, D, E, C] - 中序遍历：
[D, B, E, A, C]
只完成根节点这一层的拆分，不必继续递归，也不必画出整棵树：
- 根节点是什么？
- 左、右子树在中序遍历中分别对应哪一段？
- 左、右子树在前序遍历中分别对应哪一段？根节点有哪些直接孩子？
参考答案
-
前序遍历的第一个节点是根节点，因此根节点为
A。 -
A把中序遍历分成两部分：左子树为[D, B, E]，右子树为[C]。 -
左子树有 3 个节点，因此根节点
A后面的 3 个前序元素属于左子树， 即[B, D, E]；剩余的[C]属于右子树。 所以根节点的左孩子是B，右孩子是C。
12.6.2 编程练习¶
1. 快速幂¶
给定实数 x 和整数 n，请计算 \(x^n\)，且不能调用语言内置的幂函数。
要求使用递归分治：每次把指数缩小一半，并复用已经算出的子问题结果。
本题规定 \(x^0=1\)，包括 x = 0 时；当 n < 0 时保证 x != 0，答案可转化为 \((1/x)^{-n}\)。
解题提示
- n 等于 0 时答案是 1
- 算出 x 的 n // 2 次方后保存为 half，不要递归调用第二次
- 当 n < 0 时，先把 x 改为 1 / x，再把 n 改为 -n；使用 C++ 或 Java 时，可先把 n 转为 64 位整数，避免最小的 32 位整数取相反数时溢出
说明： 链接中的题解使用迭代位运算，与本练习指定的递归分治方法不同；请根据本题的解题提示完成递归版本