企业官网建设流程全解析

• 教程
• 文档
• 示例工程
• 教育

本篇技术指南聚焦《Hello 算法》贪心章节中的最大切分乘积问题（整数拆分求最大乘积）：给定一个正整数 $n$，将其切分为至少两个正整数的和，求所有切分因子乘积的最大值。文章将完整还原问题的数学建模、两条贪心策略的推导过程、边界处理与正确性证明，并结合仓库内 14 种语言的源码实现与 PythonTutor 可视化代码，给出可直接运行、可直接验证的实战方案。读完本文，你将掌握一类"拆数最大化乘积"问题的通用贪心求解思路，并能够在 Python、Java、C++、Go、Rust 等任意语言中独立实现该算法。

问题定义：切分整数，使因子乘积最大

给定一个正整数 $n$，将其切分为 $m$（$m \geq 2$）个正整数因子 $n_1, n_2, \dots, n_m$ 的和，即：

$$ n = \sum_{i=1}^{m}n_i $$

本题的目标是求得所有整数因子的最大乘积，即：

$$ \max(\prod_{i=1}^{m}n_i) $$

需要思考的核心问题是：切分数量 $m$ 应该多大，每个 $n_i$ 应该取多少？以 $n = 6$ 为例，$2 \times 2 \times 2 = 8$ 而 $3 \times 3 = 9$，同样是切分为三个/两个因子，乘积却不同——这说明切分方案对结果影响显著，需要系统性地推导最优策略。该问题的完整定义与推导过程见 章节文档。

贪心策略推导：从"经验直觉"到"数学不等式"

贪心算法的核心是每一步都做出当前看起来最优的局部选择。本问题的贪心策略可以通过两个逐步收紧的不等式推理得到。

策略一：所有 $\geq 4$ 的因子都应被继续切分

根据经验，两个整数的乘积往往比它们的加和更大。假设从 $n$ 中分出一个因子 $2$，则切分后的乘积为 $2(n-2)$。将该乘积与原数 $n$ 作比较：

$$ \begin{aligned} 2(n-2) & \geq n \ 2n - n - 4 & \geq 0 \ n & \geq 4 \end{aligned} $$

结论非常清晰：当 $n \geq 4$ 时，切分出一个 $2$ 后乘积会变大（或相等），这说明大于等于 $4$ 的整数都应该被切分。由此得到第一条贪心策略：

贪心策略一：如果切分方案中包含 $\geq 4$ 的因子，那么它就应该被继续切分。最终切分方案中只应出现 $1$、$2$、$3$ 这三种因子。

策略二：因子 $3$ 优于因子 $2$，最多只能保留两个 $2$

在 $1$、$2$、$3$ 这三个候选因子中，$1$ 显然是最差的：$1 \times (n-1) < n$ 恒成立，即切分出 $1$ 反而会导致乘积减小，因此最优方案中不应出现因子 $1$。

接下来比较 $2$ 与 $3$ 谁更优。以 $n = 6$ 为例：

$$ 3 \times 3 = 9 > 2 \times 2 \times 2 = 8 $$

即切分出 $3$ 比切分出 $2$ 更优。更进一步，因为 $3 \times 3 = 9 > 2 \times 2 \times 2 = 8$，三个 $2$ 总是可以替换为两个 $3$ 从而获得更大的乘积。由此得到第二条贪心策略：

贪心策略二：在切分方案中，最多只应存在两个 $2$。因为三个 $2$ 总是可以替换为两个 $3$，从而获得更大的乘积。

汇总：最终的四条切分规则

综合上述两条策略，可推理出完整的贪心策略：

1. 输入整数 $n$，从其不断地切分出因子 $3$，直至余数为 $0$、$1$、$2$；
2. 当余数为 $0$ 时，代表 $n$ 是 $3$ 的倍数，因此不做任何处理；
3. 当余数为 $2$ 时，不继续划分，保留该因子；
4. 当余数为 $1$ 时，由于 $2 \times 2 > 1 \times 3$，应将最后一个 $3$ 和余数 $1$ 替换为两个 $2$。

边界情况：$n \leq 3$ 时必须切分出一个 $1$

对于 $n \leq 3$ 的边界情况，题目要求必须切分为至少两个正整数，因此无法保留完整的 $n$，必须拆分出一个 $1$，此时乘积为：

$$ 1 \times (n - 1) $$

即 $n = 2$ 时结果为 $1$（只能切为 $1 + 1$），$n = 3$ 时结果为 $2$（切为 $1 + 2$ 或 $1 + 1 + 1$，前者更优）。

代码实现：整除与取模一步到位

上述贪心策略无需通过循环逐次切分，而可以利用向下整除与取模运算一步完成：设 $a$ 为 $3$ 的个数，$b$ 为余数，此时有：

$$ n = 3a + b $$

以下为仓库中 Python 的完整实现（同时是该问题的 PythonTutor 可视化代码主体，可视化入口见 codes/pythontutor/chapter_greedy/max_product_cutting.md）：

import math def max_product_cutting(n: int) -> int: """最大切分乘积：贪心""" # 当 n <= 3 时，必须切分出一个 1 if n <= 3: return 1 * (n - 1) # 贪心地切分出 3 ，a 为 3 的个数，b 为余数 a, b = n // 3, n % 3 if b == 1: # 当余数为 1 时，将一对 1 * 3 转化为 2 * 2 return int(math.pow(3, a - 1)) * 2 * 2 if b == 2: # 当余数为 2 时，不做处理 return int(math.pow(3, a)) * 2 # 当余数为 0 时，不做处理 return int(math.pow(3, a)) """Driver Code""" if __name__ == "__main__": n = 58 # 贪心算法 res = max_product_cutting(n) print(f"最大切分乘积为 {res}")

代码逻辑清晰，仅需按 $b$ 的取值分三种情况返回：

• $b = 0$：直接返回 $3^a$；
• $b = 2$：返回 $3^a \times 2$（余数 $2$ 保留）；
• $b = 1$：返回 $3^{a-1} \times 2 \times 2$（将一对 $1 \times 3$ 转化为 $2 \times 2$，因为 $2 \times 2 > 1 \times 3$）。

14 种语言实现对照

《Hello 算法》在该章节为每种支持的语言都提供了同构实现，逻辑完全一致，仅幂运算 API 与类型转换细节因语言而异。各语言源码路径如下：

以 C 语言实现为例（codes/c/chapter_greedy/max_product_cutting.c），其主体结构与 Python 版完全对应：n <= 3边界返回1 * (n - 1)，否则用int a = n / 3; int b = n % 3;计算个数与余数，再按b的三种取值调用pow(3, ...)返回结果。Go 语言实现（codes/go/chapter_greedy/max_product_cutting.go）与之同理，仅在幂运算处使用math.Pow并做int强转。

各语言 Driver Code 统一使用n = 58作为测试输入。其中 Go 额外提供了基于testing包的单元测试 codes/go/chapter_greedy/max_product_cutting_test.go，C# 则以内嵌[Test]方法的形式组织验证逻辑，便于读者在各自语言环境中直接运行验证。

复杂度分析：时间复杂度取决于幂运算实现

本算法不需要循环，只用了一次整除、一次取模和一次幂运算，空间复杂度为 $O(1)$（仅变量 $a$、$b$ 使用常数大小的额外空间）。

时间复杂度则取决于编程语言幂运算的实现方法。以 Python 为例，常用的幂计算函数有三种：

• 运算符**和函数pow()的时间复杂度均为 $O(\log a)$（基于快速幂的整数取幂）；
• 函数math.pow()内部调用 C 语言库的pow()函数，执行浮点取幂，时间复杂度为 $O(1)$。

因此，即使不逐次切分，算法整体仍然高效：在 $O(1)$ 或 $O(\log n)$ 量级内即可得到结果，相比枚举所有切分方案的暴力求解（指数级）具有压倒性优势。

正确性证明：反证法的三条引理

贪心策略的正确性并非自明，需要通过反证法严格证明。以下只分析 $n \geq 4$ 的情况：

1. 所有因子 $\leq 3$：假设最优切分方案中存在 $\geq 4$ 的因子 $x$，那么一定可以将其继续划分为 $2(x-2)$。由前述不等式推导可知 $2(x-2) \geq x$，即继续切分能获得更大（或相等）的乘积，与"最优方案"的假设矛盾；
2. 切分方案不包含 $1$：假设最优切分方案中存在一个因子 $1$，那么它一定可以合并入另外一个因子中，从而获得更大的乘积，与假设矛盾；
3. 切分方案最多包含两个 $2$：假设最优切分方案中包含三个 $2$，那么一定可以替换为两个 $3$。由于 $3 \times 3 = 9 > 2 \times 2 \times 2 = 8$，替换后乘积更大，与假设矛盾。

三条引理逐一排除了 $\geq 4$ 的因子、因子 $1$ 和超过两个的 $2$，从而唯一确定了"尽可能多切分出 $3$"这一最优结构，完整证明了贪心策略的正确性。

运行验证：以 $n = 58$ 为例

仓库中各语言 Driver Code 统一选取 $n = 58$ 作为输入。按算法流程计算：$58 = 3 \times 19 + 1$，即 $a = 19$、$b = 1$，命中"余数为 $1$"分支，结果应为：

$$ 3^{18} \times 2 \times 2 = 387420489 \times 4 = 1549681956 $$

在仓库中直接运行 Python 实现可得到一致输出：

python3 codes/python/chapter_greedy/max_product_cutting.py # 输出：最大切分乘积为 1549681956

这一结果与手工推导完全吻合，同时验证了"余数为 $1$ 时将 $1 \times 3$ 替换为 $2 \times 2$"这一关键步骤的正确性。读者可以修改 Driver Code 中的 $n$ 值（例如 $n = 4$ 应输出 $4$，即切分为 $2 + 2$；$n = 6$ 应输出 $9$，即切分为 $3 + 3$）来进一步验证边界与一般情形。

小结

最大切分乘积问题展示了贪心算法的一种典型解题范式：先用数学不等式压缩候选方案空间（排除 $\geq 4$ 的因子与因子 $1$），再通过局部替换证明局部最优（$3$ 优于 $2$）即全局最优。在《Hello 算法》贪心章节中，这一问题与分数背包、最大容量、最大切分乘积等经典问题共同构成贪心策略的完整练习矩阵（章节导览见 docs/chapter_greedy/index.md），其"推导 → 实现 → 证明"三步走方法可迁移到更多优化类问题中。若要更直观地观察算法执行过程，可在 PythonTutor 中逐步运行 codes/pythontutor/chapter_greedy/max_product_cutting.md 内嵌的可视化代码，逐条指令查看变量 $a$、$b$ 与返回值的变化。

• 教程
• 文档
• 示例工程
• 教育