算法计算k个形式为1/r的小数加总为1

给定k，我们需要将1编写为k形式的1/r分数的总和。

例如，

对于k=2，1可以唯一地写为1/2 + 1/2。

对于k=3，1可以写为1/3 + 1/3 + 1/3或1/2 + 1/4 + 1/4或1/6 + 1/3 + 1/2

现在，我们需要考虑所有此类k分数集合，这些分数总和为1，并返回所有此类集合中的最高分母。例如，示例2，我们的算法应返回6。

我在一次编码竞赛中遇到了这个问题，却无法提出相同的算法。稍后，Google进行了一些搜索，发现这些分数被称为 Egyption分数，但是可能它们是一组不同的分数，总和为一个特定值(不像1/2 + 1/2)。另外，当它们的数量受k限制时，我找不到计算埃及分数的算法(如果它们对这个问题完全有帮助)。

最佳答案

如果您要做的就是找到最大的分母，则没有理由找到所有可能性。您可以非常简单地执行此操作:

public long largestDenominator(int k){
    long denominator = 1;
    for(int i=1;i<k;i++){
        denominator *= denominator + 1;
    }
    return denominator;
}

对于递归类型:

public long largestDenominator(int k){
    if(k == 1)
        return 1;
    long last = largestDenominator(k-1);
    return last * (last + 1); // or (last * last) + last)
}

为什么这么简单？

要创建集合，您需要在每个步骤(最后一个步骤除外)中插入最大的分数，将其保留在1下。 “最大分数”是指值，即最小的分母。

对于简单的k=3而言，这意味着您从1/2开始。您无法容纳另一半，因此请使用1/3。然后剩下1/6，为您提供三个术语。

对于下一种情况k=4，您可以从最后删除该1/6，因为它不适合一个，并且我们需要为另一个术语留出空间。将其替换为1/7，因为这是最大的适合值。其余的是1/42。

根据需要重复。

例如:

2:[2,2]

3:[2,3,6]

4:[2,3,7,42]

5:[2,3,7,43,1806]

6:[2,3,7,43,1807,3263442]

如您所见，它迅速变得很大。足够快地，如果long，您将溢出k>7。如果需要，您将需要找到一个合适的容器(即Java/C#中的BigInteger)。

它完美地映射到this sequence:



您还可以看到与Sylvester's sequence的关系:



彼得在评论中指出，Wikipedia有一篇非常不错的文章，解释了两者之间的关系。

关于算法计算k个形式为1/r的小数加总为1，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18087395/