貪心算法與埃及分數問題詳解

埃及分數（Egyptian Fractions）問題是數論中的經典問題，要求將一個真分數表示為互不相同的單位分數之和。本文將用2萬字全面解析貪心算法在埃及分數問題中的應用，涵蓋數學原理、算法設計、Java實現、優化策略及擴展應用。

---

一、埃及分數問題定義

1.1 基本概念

• 單位分數：分子為1的正分數（如1/2、1/3）
• 埃及分數表示：任何正有理數可表示為有限個不同單位分數之和
• 數學定理：? a/b ∈ (0,1), ? 有限序列 {1/k?, 1/k?, …, 1/k?} 使得 a/b = Σ 1/k?

1.2 問題形式化
輸入：兩個正整數 a, b（滿足 0 < a < b）
輸出：一組互不相同的單位分數，使得它們的和等于 a/b

示例：

7/8 = 1/2 + 1/3 + 1/24  
2/3 = 1/2 + 1/6  
5/6 = 1/2 + 1/3  

---

二、貪心算法策略與數學原理

2.1 貪心選擇策略
每次選擇滿足以下條件的最大單位分數：

1. 1/k ≤ 當前剩余分數
2. k 是滿足條件的最小正整數

數學推導：
對于剩余分數 a’/b’，選擇：

k = ceil(b'/a')  

然后計算新剩余分數：

a'/b' - 1/k = (a'*k - b') / (b'*k)  

2.2 正確性證明

1. 終止性：每次操作后分子嚴格遞減
   • 新分子：a’’ = a’*k - b’ < a’
2. 正確性：通過數學歸納法可證明總能找到解

2.3 算法步驟

1. 初始化剩余分數為 a/b
2. 循環直到剩余分數為0：
   a. 計算當前最大單位分數 1/k
   b. 將 1/k 加入結果集
   c. 計算剩余分數 = 剩余分數 - 1/k
   d. 化簡剩余分數
3. 返回結果集

---

三、基礎Java實現

3.1 核心代碼結構

import java.util.ArrayList;
import java.util.List;public class EgyptianFractions {// 計算最大公約數private static int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;}// 分數化簡private static int[] reduceFraction(int a, int b) {int common = gcd(a, b);return new int[]{a / common, b / common};}// 貪心算法分解埃及分數public static List<String> getEgyptianFractions(int numerator, int denominator) {List<String> result = new ArrayList<>();while (numerator != 0) {// 計算當前k值int k = (int) Math.ceil((double) denominator / numerator);result.add("1/" + k);// 計算剩余分數: numerator/denominator - 1/kint newNumerator = numerator * k - denominator;int newDenominator = denominator * k;// 化簡分數int[] reduced = reduceFraction(newNumerator, newDenominator);numerator = reduced[0];denominator = reduced[1];}return result;}public static void main(String[] args) {List<String> egyptian = getEgyptianFractions(7, 8);System.out.println("7/8 = " + String.join(" + ", egyptian));// 輸出: 7/8 = 1/2 + 1/3 + 1/24}
}

3.2 代碼解析

1. gcd函數：計算最大公約數用于分數化簡
2. reduceFraction方法：將分數化為最簡形式
3. 核心循環邏輯：
   • 計算當前最大單位分數的分母k
   • 更新剩余分數分子分母
   • 化簡分數防止數值膨脹

3.3 時間復雜度分析

• 最壞情況：O(n)（n為分解步數）
• 每步計算：O(1)
• 實際效率取決于輸入分數特性

---

四、高級實現與優化

4.1 防止整數溢出
使用長整型存儲中間結果：

public static List<String> getEgyptianFractionsSafe(int numerator, int denominator) {List<String> result = new ArrayList<>();long num = numerator;long den = denominator;while (num != 0) {long k = (den + num - 1) / num; // 避免浮點計算result.add("1/" + k);long newNum = num * k - den;long newDen = den * k;// 化簡long common = gcd(newNum, newDen);num = newNum / common;den = newDen / common;}return result;
}private static long gcd(long a, long b) {while (b != 0) {long temp = b;b = a % b;a = temp;}return a;
}

4.2 迭代代替遞歸
避免棧溢出風險：

public static List<String> getEgyptianFractionsIterative(int numerator, int denominator) {List<String> result = new ArrayList<>();int[] current = {numerator, denominator};while (current[0] != 0) {int a = current[0];int b = current[1];int k = (int) Math.ceil((double) b / a);result.add("1/" + k);int[] next = {a * k - b, b * k};int gcd = gcd(next[0], next[1]);current[0] = next[0] / gcd;current[1] = next[1] / gcd;}return result;
}

4.3 性能優化技巧

1. 預計算加速：緩存常用分數分解
2. 并行計算：多線程處理多個分數分解
3. 符號處理：擴展支持負數分數

---

五、數學證明與實例分析

5.1 正確性證明
基例：當a=1時，直接返回1/b
歸納步驟：假設對a’ < a成立，則：

1. 選擇k = ?b/a?
2. 剩余分數 (ak - b)/(bk) 的分子 a’ = a*k - b < a
3. 根據歸納假設，剩余分數可分解

5.2 實例推演
以7/8為例：

步驟1: k = ceil(8/7)=2 → 1/2  
剩余: 7/8 - 1/2 = 3/8  
步驟2: k = ceil(8/3)=3 → 1/3  
剩余: 3/8 - 1/3 = 1/24  
步驟3: k=24 → 1/24  
剩余: 0 → 終止  
結果: 1/2 + 1/3 + 1/24

5.3 算法局限性

• 分解結果可能不是最短的埃及分數表示
  示例：5/121 貪心分解需要多步，存在更優解
• 分母可能快速增長導致數值溢出

---

六、測試用例設計

6.1 基礎測試

@Test
void testBasicCases() {// 測試用例1: 7/8List<String> result1 = EgyptianFractions.getEgyptianFractions(7, 8);assertEquals(Arrays.asList("1/2", "1/3", "1/24"), result1);// 測試用例2: 2/3List<String> result2 = EgyptianFractions.getEgyptianFractions(2, 3);assertEquals(Arrays.asList("1/2", "1/6"), result2);
}

6.2 邊界測試

@Test
void testEdgeCases() {// 分子為1List<String> result3 = EgyptianFractions.getEgyptianFractions(1, 5);assertEquals(Collections.singletonList("1/5"), result3);// 大分母測試List<String> result4 = EgyptianFractions.getEgyptianFractions(1, 1000);assertEquals(Collections.singletonList("1/1000"), result4);
}

6.3 性能測試

@Test
void testPerformance() {long start = System.currentTimeMillis();EgyptianFractions.getEgyptianFractions(1234, 4321);long duration = System.currentTimeMillis() - start;assertTrue(duration < 100, "Time cost should be less than 100ms");
}

---

七、擴展應用與變種問題

7.1 最短埃及分數表示

• 屬于NP難問題
• 需結合回溯法或動態規劃
• 示例：5/121 = 1/25 + 1/757 + 1/763309 + 1/8739601…（貪心法需要更多項）

7.2 現代應用場景

1. 密碼學：在門限方案中分配秘密份額
2. 資源分配：將總資源分解為多個獨立配額
3. 數學教育：分數運算教學工具

7.3 多分子擴展
處理形如2/5的分解：

2/5 = 1/3 + 1/15  = 1/4 + 1/6 + 1/20  

---

八、與其他算法對比

8.1 貪心算法 vs 回溯法

特性	貪心算法	回溯法
時間復雜度	O(n)	指數級
結果質量	非最優但快速	可得最優解
內存消耗	O(1)	O(n)
適用場景	快速近似解	小規模精確解

8.2 貪心算法 vs 幾何方法

• 幾何方法：基于斐波那契-西爾維斯特數列
• 優勢：能產生更短的分解
• 缺點：實現復雜度高

---

九、總結

9.1 改進方向

• 結合啟發式搜索優化結果長度
• 開發混合算法（貪心+動態規劃）
• 擴展支持分數運算符號處理

更多資源：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文發表于【紀元A夢】！