问题 计算形式1 / r的k个分数的算法总计为1

如果您想要做的就是找到最大的分母，那么没有理由找到所有可能性。你可以非常简单地做到这一点：

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]
• 五 ：[2,3,7,43,1806]
• 6 ：[2,3,7,43,1807,3263442]

如您所见，它迅速变得非常大。很快你就会溢出来 long 如果 k>7。如果您需要这样做，您需要找到一个合适的容器（即Java / C＃中的BigInteger）。

它完美映射到 这个序列：

a(n) = a(n-1)^2 + a(n-1), a(0)=1。

你也可以看到与之的关系 西尔维斯特的序列：

a(n+1) = a(n)^2 - a(n) + 1, a(0) = 2

维基百科 有一篇非常好的文章解释了两者之间的关系，正如彼得在评论中指出的那样。