寻找埃及分数

前几天面试，老师问到关于埃及分数的问题。什么是埃及分数了?其实就是把一个真分数拆分成分子为1，分母不同的分数之和。比如 4/7 = 1/2 + 1/14。如何求解出埃及分数了? 算法一:        当时面试第一反应是想利用公式 1/n = 1/(n+1) + 1/((n+1)*n) .假如给定一个真分数4/7 , 可以先把4提出来，则1/7 = 1/8 + 1/56 . 两边在同时乘以4 ,则4/7 = 1/2 + 1/14 。如果是利用这个思想，会有两个问题：一、当有重复分母时怎么办 二、当分子不能整除时，可以利用公式展开直到能被分子整除为止。当时自己被第一个问题难倒了，所以自己很快放弃了这个方法，但事后自己想了想其实自己只要转个弯就可以解决,而且非常漂亮。这个后面在深入讲吧。之后就有第二个算法。
算法二:       假设a/b是一个真分数，定义b/a为取整。现在不考虑a整除b的情况。于是可以找到一个最临近a/b的真分数 1/(b/a+1) 。 令c = b/a + 1 , 用 a/b - 1/c 可以得到一个小于1/c的真分数A . A的分子为a*c - b , A的分母为b*c 。 由于A 也是一个真分数，那么就可以递归使用这个算法。 问题是解决了，可惜当时5个老师都不相信我的算法，唉，自己也算是失败了。关于这个算法了，我有个问题 ， 我在找寻比a/b稍小的真分数时，使用了b/a+1。 实际上也只能加1，如果加上比1大的数，在后续的递归展开中会出现分母相同的情况。这个问题现在我已经解决了，可以突破加1的限制。这个留在后面讲吧。
算法三:       自己在灰心之余心有不甘，面试完几天自己依然不服气 ， 可是已经晚了，只恨这片土地。这些就不说了，这个算法其实不是新的算法，只是对前面提出问题的解决和改进。假如有个真分数a/b , 利用算法一，可以展开为a/b = 1/A + 1/B + 1/C + 1/D ...  假设A = C ， 这个时候就出现了分母相同的情况。这个时候怎么办了？其实很简单 ， 可以 把1/C 化为 1/(C+1) + 1/((C+1)*C) ，看到了吧，还是利用 1/n = 1/(n+1) + 1/((n+1)*n) 这个公式，重复利用这个公式就可以解决这个问题了。但是...我写了一个程序，4/7的埃及可以很快的得出来，但是5/7了，悲剧了，列出来的埃及分数何其多也！这就导出了另外一个问题，就是分子不好整除的情况！在所有的整数中4容易找到整除的数，但是5了，就不容易了！怎么办了？我又想了一个方法，我想到将真分数拆分。比如5/7我可以先拆分2/7和3/7，这个2/7和3/7不就容易展开了。但是，这个还是有问题，实在不是一个完美的解决方案，幸运的是，我找到了更完美的解决方案，而且，结果非常漂亮，因为它是金字塔！说到这个，算法二如何突破加1的限制了，你自己思考吧。如果你懂了，那我问你个问题，如果我给定你一个真分数a/b，我要你在展开埃及分数中一定要包含1/c （1/c小于a/b） 。 你可以办到吗？
算法四: 埃及金字塔。       埃及人提出埃及分数可能连他们自己也没想到会引起后人对它的思考。因为我感觉埃及人提出埃及分数只是为了计算方便。好吧，现在看下如何构造金字塔式的埃及分数。       例如 4/7 ， 则埃及分数为:                                                   1/7                                               1/8   1/56                                       1/9  1/72  1/57  1/3192                          1/10 1/90 1/73 1/5256 1/58 1/3306 1/3193 1/10192056 把上面的所有的真分数加起来吧，是的，你得到埃及分数。 具体怎么来的，我还是比较私心的，你自己想吧。如果，你想到了，我再问个问题吧，金字塔里会出现相同的两个数吗？如何证明。当然我已经解决了。
悲剧的一次面试！哎。。。