Question

关于 埃及分数 的C++程序。

背景：埃及分数就是指分子为1的分数，比如1/2,1/5……。
一个埃及分数可以分解成若干埃及分数之和：1/2=1/3+1/6
1/3=1/4+1/12
分解成两个埃及分数之和的通式为1/n=1/(n+a) + 1/(n+b)
其中ab=n²。
如果分解成三个之和只要对其中一个加数再分解就可以了。
1/2=1/4+1/12+1/6
我希望能够设计一个程序实现：输入一个n,并且输入分解的个数m,输出所有的可能项。
问题是：如果m较大，岂不是要不断迭代，先分解成两个之和，再迭代分解成三个之和……就需要巨大的数组存放中间数据，这样程序运行就会特别大特别慢。有什么办法可以较好地解决吗？

Answer 1

因为要输出所有可能项，所以想省掉内存占用是不可能的，所以只能在速度上进行优化。
如 lch743 所说，如果你只是要一次结果或者少量结果，那么大可不必优化，如果你需要长期多次进行这种分解，就可以建立查找表，优化分解操作。如果这样还不能满足你的速度要求，可能你每天有很多个需要分解的数，并且m还巨大，你就得考虑分布式计算了。用更多的计算机资源加速计算，问题总有解决之道，关键就是看值不值得。

Answer 2

这个个人觉得是要很大的内存来存数据的，要加快速度可以用哈希的方式，类似于查找表，只要确定了分解方式的都放在表里，当然这个只对情况比较多的有效，不足之处可以继续探讨。

追问

如果只是纯粹使用二位数组存放的话，确实需要巨大的数据，比如m=5,就要先做二项分解,然后迭代成三项……，会特别繁琐吧？我在想能不能使用指针的方式操作，就是中间数据不要全部存储，只是用一个一维数组记录当前结果，指针指到某一项，对这一项进行二次分解，然后输出结果，之后就把结果抹掉。这样会不会更好些?

追答

这种方式当然可以的，反正也跟前面的无关了，记录当前就好，一层一层往下走，比如m=5，第一层是原始分数的话，总共就要走5层，不知道速度怎么样，因为每一层都要进行分解计算，计算结果如果可以保存的话，估计会快点。

追问

可是具体实现我还是不太清楚。比如对1/2分解吧。 m=5
1/2=1/3+1/6 (第一层，只有这一种，不讨论两个分母相同的情况)；
=（1/4+1/12）+1/6 （对1/3的二项分解，只有此一种）
=1/3+（1/7+1/42）
=1/3+（1/8+1/24）
=1/3+（1/9+1/18）
=1/4+（1/10+1/15） （对1/6的二项分解，四种情况）
到这一步我应该还可以理解，如果要用指针的方法继续做四项分解的话，我就有点混乱了。
感谢您的指点！

追答

如你所说，
第一层：1/3+1/6；
第二层：（1/4+1/12）+1/6，1/3+（1/7+1/42），1/3+（1/8+1/24），1/3+（1/9+1/18），1/4+（1/10+1/15）；
第三层：...
第四层：...
四层其实就是结果了。
我们看第二层（1/4+1/12）+1/6这一项，对每个分数依次进行二项分解，就是第三层的结果了，依此类推，用树的结构可以很好的表达，指针方法只是一种实现，建议使用STL容器；
两个容器，1：存上一层的结果，2：存这一层的结果，遍历容器1中的每一项，将分解结果加到容器2中，删除容器1中的那一项，继续下一项，直到容器1中为空为止，这时进行下一步，容器2中结果拷贝到容器1，容器2置空，从头开始，我就想到这了，还有很多细节要注意！