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

Question

鉴于k,我们需要写作表格1的k分数之和1/r.

例如,

1. 因为k=2,1可以唯一地写成1/2 + 1/2.
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.

我在编码竞赛中遇到了这个问题,并且无法提出相同的算法.之后的一些谷歌搜索显示,这些分数被称为埃及分数,但可能它们是一组不同的分数,总计达到一个特定的值(不是这样1/2 + 1/2).此外,当他们的号码受到限制时,我找不到计算埃及分数(如果它们对这个问题都有帮助)的算法k.

Answer 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]
• 5:[2,3,7,43,1806]
• 6:[2,3,7,43,1807,3263442]

如你所见,它迅速变得非常大.很快你就会溢出一个longif 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

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