11

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

例如，

  1. 对于k=2,1可以唯一地写为1/2 + 1/2。
  2. 对于k=3,1可以写成1/3 + 1/3 + 1/3or 1/2 + 1/4 + 1/4or1/6 + 1/3 + 1/2

现在，我们需要考虑在所有这些集合中k求和1并返回最高分母的所有这些分数集合；例如，示例案例 2，我们的算法应该返回6.

我在编码比赛中遇到了这个问题，但无法提出相同的算法。后来通过谷歌搜索发现，这样的分数被称为埃及分数，但它们可能是一组不同的分数，总和为一个特定的值（不像1/2 + 1/2）。此外，当埃及分数的数量受到k.

4

2 回答 2

16

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

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.

您还可以看到与Sylvester 序列的关系：

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

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

于 2013-08-06T18:33:53.517 回答
0

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

主意

您可以从几何上考虑它们：

  • 从单位正方形 (1x1) 开始
  • 绘制垂直或水平线将正方形分成相等的部分。
  • 选择性地在任何子框内均匀地重复绘制线条。
  • 随时停止。

出现的矩形将形成一组 1/n 形式的分数，它们加到 1。

您可以计算它们，它们可能等于您的“k”。

根据您将矩形分成多少相等的部分，它会告诉您是 1/2 还是 1/3 或其他。1/6 是 1/3 的 1/2 或 1/2 的 1/3。（即您潜入 2 分，然后其中一个子框潜入 3 分或相反。）

想法 2

你从 1 个盒子开始。这是 k=1 的分数 1/1。

当您除以 n 时，您将 n 添加到框数（k 或求和的分数）并减去 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 with 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 的所有整数都有类似的模式。

于 2013-08-06T18:22:38.953 回答