用蛮力法解决埃及分数问题

埃及分数问题"/>

用蛮力法解决埃及分数问题

问题

埃及分数是埃及分数是指分子是1的分数，也叫单位分数。古代埃及人在进行分数运算时。只使用分子是1的分数。因此这种分数也叫做埃及分数，或者叫单分子分数^{[百度百科]}。举例来说： 7/8 = 1/2 + 1/3 + 1/24。

分析

由于每个组成都是用的真分数（即分子为1的分数），所以我们可以使用蛮力法，将分数从2开始，逐一进行测试，设分数为f, 分母为d，则步骤如下：

1. 比如 f 和 1/d，若 f >= 1/d，则到第2步，否则d++，继续本步
2. f = f - 1/d，然后将 1/d 进行记录，如果f == 0，循环结果，否则d ++后回到第1步

以7/8为例，具体步骤如下：
-> 7/8 - 1/2 = 3/8
-> 3/8 - 1/3 = 1/24
-> 1/24 - 1/4 跳过
-> 1/24 - 1/5 跳过
-> 1/24 - 1/6 跳过
。。。
-> 1/24 - 1/23 跳过
-> 1/24 - 1/24 = 0 循环结束

Java实现

源代码中利用了之前的分数类《一个完整的Java版的分数类》。具体实现代码如下所示：

	public static void main(String[] args) {Fraction f = new Fraction(99, 100);ArrayList<Fraction> fs = new ArrayList<>();System.out.print(f + " = ");int p = 2;while (f.toDouble() > 0) {Fraction f1 = new Fraction(1, p++);if (f.toDouble() >= f1.toDouble()) {fs.add(f1);f.sub(f1);}}for (int i = 0; i < fs.size(); i++)System.out.print(fs.get(i) + (i == fs.size() - 1 ? "" : " + "));}

示例中求的是99/100，结果显示如下：
99/100 = 1/2 + 1/3 + 1/7 + 1/73 + 1/9018 + 1/230409900。