计算形如1/r的k个分数相加得到1的算法

Question

计算形如1/r的k个分数相加得到1的算法

11

给定一个整数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受限制，我找不到计算Egyption Fractions（如果它们对此问题有帮助）的算法。

- Shobhit

1

埃及分数的贪心算法 - Jim Mischel

1

@JimMischel 这是一篇不错的文章，但似乎没有回答问题。 - RBarryYoung

@JimMischel 我确实遇到过这种方法，但正如我在问题中提到的，埃及分数是不同的分数。此外，所提出的贪心算法并没有考虑到我想要恰好有k个这样的分数。 - Shobhit

这里有一篇非常好的文章。http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html - JNL

2个回答

0

我以前从未听说过埃及分数，但是这里有一些想法：

思路

你可以从几何角度来考虑它们：

从一个单位正方形（1x1）开始
画垂直或水平线将正方形分成相等的部分。
可选地在任何子框中均匀地重复绘制线条。
随时停止。

所呈现的矩形将形成一组形如1/n的分数，它们加起来等于1。

您可以对它们进行计数，它们可能等于您的“k”。

根据您将矩形分成多少个相等的部分，它将告诉您是否有1/2或1/3或其他。 1/6是1/3的1/2或1/2的1/3。（即，您将其除以2，然后将其中一个子框除以3，或者反之亦然。）

思路2

您从1个框开始。这是分数为1/1且k=1。

当您通过n进行子分割时，您将框的数量（k或总和的分数）增加n并减去1。

当你再次细分任何一个盒子时，减去1并加上n，即划分的数量。请注意，n-1是您用来划分它们的线条数。

更多

您将从k开始寻找答案。显然，k * 1/k = 1，因此您已经有一个解决方案。

k-1怎么样？

那里有一个解决方案：(k-2) * 1/(k-1) + 2 * (1/((k-1)*2))

我怎么得到的？我将k-1等分为（具有k-2个垂直线）的部分，然后在水平方向上将最后一个部分分成两半。

每个解决方案都将包括：

采用先前的解决方案
在某个阶段使用j条较少的线，并将其中一个盒子或子盒子分成j+1个相等的部分。

我不知道是否可以通过从k * 1/k开始重复此规则来形成所有解决方案。

我知道你可以通过这种方式获得有效的副本。例如：k * 1/k，其中j = 1 => (k-2) * 1/(k-1) + 2 * (1/((k-1)*2)) [来自上面]，但是k * 1/k，其中j = (k-2) => 2 * (1/((k-1)*2)) + (k-2) * 1/(k-1) [只是颠倒了部分的顺序]

有趣

k = 7 可以表示为 1/2 + 1/4 + 1/8 + ... + 1/(2^6) + 1/(2^6)，一般情况下是 1/2 + ... + 1/(2^(k-1)) + 1/(2^(k-1))。

同样地，对于任何奇数 k，它都可以表示为 1/3 + ... + 3 * [1/(3^((k-1)/2)]。

我怀疑所有整数直到 k 都有类似的模式。

- Lee Meador

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Geobits · Accepted Answer

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

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 的条件，而我们需要另外一项空间。用适合的最大值 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]

可以看到，这个集合变得非常庞大。如果 k>7，它会迅速溢出 long。如果需要，你需要找到一个适当的容器（如 Java/C# 中的 BigInteger）。

它与此序列完美映射：

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

还可以看到它与Sylvester's sequence的关系：

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

Wikipedia有一篇非常好的文章，解释了两者之间的关系，正如 Peter 在评论中指出的那样。