企业官网建设流程全解析

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 算法》倉庫中貪婪演算法章節的經典例題「最大切分乘積問題」（原始文檔），完整講解其貪婪策略的數學推導過程、O(1)空間的常數級實現、以及使用反證法的嚴格正確性證明。讀者讀完後，將掌握如何從「區域性最優選擇」出發推導出全域性最優解，並能在 Python、C、C++、Java、Go、Rust、TypeScript 等十餘種語言中直接套用官方實現（如 Python 實現），同時理解貪婪演算法與動態規劃的適用邊界。

問題定義：從整數切分到最大乘積

!!! question

給定一個正整數 $n$ ，將其切分為至少兩個正整數的和，求切分後所有整數的乘積最大是多少。

假設將 $n$ 切分為 $m$ 個整數因子，其中第 $i$ 個因子記為 $n_i$ ，即

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

本題的目標是求得所有整數因子的最大乘積，即

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

要解決這個問題，核心在於回答兩個問題：切分數量 $m$ 應該多大？每個因子 $n_i$ 應該是多少？這正是貪婪策略需要回答的。需要注意的是，題目要求「至少切分為兩個正整數」，因此即使 $n$ 本身很小，也必須執行切分——這個約束直接影響後文 $n \leq 3$ 的邊界處理。

貪婪策略的兩步推導

與零錢兌換等「策略可能失效」的貪婪例題不同（可對比 貪婪演算法總論 中提到的反例），本題的貪婪策略可以透過嚴謹的數學推導得出，且能證明其必然得到最優解。推導分為兩步。

貪婪策略一：大於等於 4 的因子都應被繼續切分

根據經驗，兩個整數的乘積往往比它們的加和更大。假設從 $n$ 中分出一個因子 $2$ ，則剩餘部分與 $2$ 的乘積為 $2(n-2)$ 。將該乘積與原數 $n$ 作比較：

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

上述不等式說明：當 $n \geq 4$ 時，切分出一個 $2$ 後乘積會變大。因此可以得出第一條貪婪策略：

貪婪策略一：如果切分方案中包含 $\geq 4$ 的因子，那麼它就應該被繼續切分。最終的切分方案只應出現 $1$、$2$、$3$ 這三種因子。

貪婪策略二：因子 3 優於 2，最多只保留兩個 2

在 $1$、$2$、$3$ 這三個候選因子中，顯然 $1$ 是最差的，因為 $1 \times (n-1) < n$ 恆成立，即切分出 $1$ 反而會導致乘積減小。

接下來比較 $2$ 與 $3$ 誰更優。以 $n = 6$ 為例：$3 \times 3 = 9 > 2 \times 2 \times 2 = 8$ ，這意味著切分出 $3$ 比切分出 $2$ 更優。

進一步推廣：三個 $2$ 的乘積是 $8$，而兩個 $3$ 的乘積是 $9$，因此任何包含三個 $2$ 的方案都可以替換為兩個 $3$ 而獲得更大乘積。由此得出第二條貪婪策略：

貪婪策略二：在切分方案中，最多隻應存在兩個 $2$ 。因為三個 $2$ 總是可以替換為兩個 $3$ ，從而獲得更大的乘積。

綜合策略：盡可能切分出 3

綜合以上兩步推導，可以得到完整的貪婪策略：

1. 輸入整數 $n$ ，從其不斷地切分出因子 $3$ ，直至餘數為 $0$、$1$、$2$ 。
2. 當餘數為 $0$ 時，代表 $n$ 是 $3$ 的倍數，因此不做任何處理。
3. 當餘數為 $2$ 時，不繼續劃分，保留。
4. 當餘數為 $1$ 時，由於 $2 \times 2 > 1 \times 3$ ，因此應將最後一個 $3$ 和餘數 $1$ 替換為兩個 $2$ 。

這個策略的本質是：以 3 為最優基本單位，並在最壞餘數（1）出現時用「兩個 2」補救。

程式碼實現：用除法與取模代替迴圈

我們無須透過迴圈來逐步切分整數，而可以利用向下整除運算得到 $3$ 的個數 $a$ ，用取模運算得到餘數 $b$ ，此時有：

$$ n = 3a + b $$

其中 $a = \lfloor n / 3 \rfloor$，$b = n \bmod 3$，$b \in {0, 1, 2}$。根據 $b$ 的取值直接計算答案，即可將時間複雜度壓縮到常數級別。

請注意，對於 $n \leq 3$ 的邊界情況，必須拆分出一個 $1$（因為題目要求至少切分成兩個正整數），此時乘積為 $1 \times (n - 1)$ 。這對應 $n=2$ 時答案為 $1$、$n=3$ 時答案為 $2$ 的退化情形。

以下是倉庫中 Python 官方實現 的完整程式碼（繁體版位於 zh-hant/codes/python）：

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))

三種餘數分支的含義

• $b = 0$（n 是 3 的倍數）：直接返回 $3^a$，所有因子都是 3。
• $b = 2$：返回 $3^a \times 2$，保留一個因子 2。
• $b = 1$：這是唯一需要「修正」的情況。若直接返回 $3^a \times 1$，等於引入了最差的因子 1。根據策略二，將最後一個 3 與餘數 1 合併重組：$3 \times 1 \rightarrow 2 \times 2$（因為 $4 > 3$），故返回 $3^{a-1} \times 2 \times 2$。

多語言實現對照

《Hello 算法》在 codes 目錄下提供了同構實現，核心邏輯完全一致，僅在語言層面有細微差異：

值得注意的細節：C/C++/Java/Go 的pow()系列函式返回浮點型，需要強制型別轉換；而 Rust 實現 直接使用整數冪方法3_i32.pow(a as u32)，避免了浮點精度問題，是語言層面的最佳實踐範例。

實戰驗證：n = 58

所有語言的 Driver Code 均以n = 58作為測試樣例。代入公式：$58 = 3 \times 19 + 1$，即 $a = 19$、$b = 1$，屬於餘數為 1 的分支，答案為：

$$ 3^{18} \times 2 \times 2 = 1{,}549{,}681{,}956 $$

執行各語言程式（例如python codes/python/chapter_greedy/max_product_cutting.py）均輸出「最大切分乘積為 1549681956」，與手算結果一致。此外，倉庫還提供了 Python Tutor 可視化連結，可逐步觀察變數 $a$、$b$ 的演算過程，適合初學者理解演算法執行軌跡。

複雜度分析

• 時間複雜度：主體僅為一次除法和取模運算，實際耗時取決於程式語言的冪運算實現方法。以 Python 為例，常用的冪計算函式有三種：

  • 運算子**和函式pow()的時間複雜度均為 $O(\log a)$（基於快速冪的整數運算）。
  • 函式math.pow()內部呼叫 C 語言庫的pow()函式，其執行浮點取冪，時間複雜度為 $O(1)$。
  • 若使用 Rust 的3_i32.pow()，底層同樣是快速冪，時間複雜度為 $O(\log a)$。

  因此，在 Python 中選用math.pow()可以獲得常數時間的冪運算；而在其他語言中，浮點pow()與整數快速冪的差異需要結合語言實現具體權衡。

• 空間複雜度：變數 $a$ 和 $b$ 使用常數大小的額外空間，因此空間複雜度為 $O(1)$。

整個演算法不依賴任何動態規劃表格或遞迴棧，無論 $n$ 多大，記憶體佔用恆定——這是貪婪演算法相對於動態規劃的典型效率優勢（可參見 貪婪演算法章節 中「貪婪演算法不僅操作直接、實現簡單，而且通常效率也很高」的論述）。

正確性證明：三步反證法

貪婪演算法並非總能保證全域性最優（零錢兌換即是反例），因此必須對策略進行嚴格證明。本題使用反證法，只分析 $n \geq 4$ 的情況（$n \leq 3$ 的邊界已由程式碼直接處理）。

1. 所有因子 $\leq 3$：假設最優切分方案中存在 $\geq 4$ 的因子 $x$ ，那麼一定可以將其繼續劃分為 $2(x-2)$ ，而由前述不等式 $2(x-2) \geq x$（當 $x \geq 4$）可知新乘積更大（或相等），這與「原方案最優」的假設矛盾。
2. 切分方案不包含 $1$：假設最優切分方案中存在一個因子 $1$ ，那麼它一定可以合併入另外一個因子中（例如將 $1$ 與因子 $y$ 合併為 $y+1$，因為 $(y+1) > 1 \times y$），以獲得更大的乘積，這與假設矛盾。
3. 切分方案最多包含兩個 $2$：假設最優切分方案中包含三個 $2$ ，其乘積為 $2 \times 2 \times 2 = 8$；若替換為兩個 $3$，乘積為 $3 \times 3 = 9$，更大，這與假設矛盾。

三步證明恰好對應前述三條貪婪策略，形成閉環：策略一排除 ≥4 的因子，證明二排除因子 1，證明三限定 2 的數量上限。最終方案只能由若干個 3（以及至多兩個 2）組成，而「盡可能多取 3」正是因為 3 是唯一可行的最優基本單位——這與「反證法或數學歸納法」的貪婪正確性證明套路完全一致（見 貪婪演算法解題步驟）。

與動態規劃的對比與延伸思考

值得注意的是，最大切分乘積問題同樣存在動態規劃解法（狀態轉移可定義為「將 n 切出一個因子 i 後，剩餘部分繼續切分或不再切分」）。兩者對比可以清晰地體現貪婪演算法的特性：

• 動態規劃：需要 $O(n)$ 或 $O(n^2)$ 的狀態與轉移，記憶體佔用隨 n 線性增長；
• 貪婪演算法：本題實現僅 $O(1)$ 空間、$O(1)$（或 $O(\log n)$）時間，代價是必須先用反證法證明貪婪選擇性質與最優子結構。

從 貪婪演算法章節 的分類看，本題屬於「可以保證找到最優解」的貪婪適用場景——這得益於因子 3 的「邊際收益遞減」特性恰好滿足貪婪選擇性質。而零錢兌換問題之所以不適用貪婪，是因為硬幣面值組合破壞了這種性質。透過本題，讀者可以建立起判斷「何時能用貪婪、何時必須用動態規劃」的直覺：當每一步的區域性最優選擇（切出 3）可以數學證明恆優於其他選擇時，貪婪即是終極解法。

最後建議讀者動手實驗：修改各語言 Driver Code 中的n值（如 $n = 4, 5, 6, 10, 100$），對比輸出與手算結果，並在 Python Tutor 中逐幀觀察演算法過程，以加深對貪婪策略推導與證明全流程的理解。

【免费下载链接】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