4

我正在尝试进行 Euler number 219项目，但未能掌握它。我正在尝试使用 Python，根据 Euler 项目，它应该能够在一分钟内完成！这让我认为他们不可能希望我计算每个单独的位串，因为这在 Python 中太慢了——必须有一个 sub O(n) 算法。

我查看了一个递归解决方案，它存储位串可能的前缀，以便它可以快速选择一个新的位串，甚至将它们分组考虑。这仅适用于 10 多一点的暴力破解值：

cost(1) = 1
cost(2) = 5
cost(3) = 11
cost(4) = 18
cost(5) = 26
cost(6) = 35
cost(7) = 44
cost(8) = 54
cost(9) = 64
cost(10)= 74
cost(11)= 85
cost(12)= 96

过去，我正在努力理解如何减少问题。总是可以制作出如下模式：

1
01
001
0001
00001
00000

但对于超过 7 个位串来说，它并不是最优的。谁能指导我应该考虑什么？

4

6 回答 6

9

蛮力不是正确的方法。这是其中一个问题，如果你知道某件事，这并不难，但如果你从未听说过那件事，那几乎是不可能的。那东西就是哈夫曼树。

[编辑]经过进一步审查，您似乎无法在具有特定频率的 N 个节点上完全构建 Huffman 树，因为字符串的成本函数是 4*(# of 1) + (# of 0)。如果成本函数是字符串的长度（或其倍数），那么您可以创建一个霍夫曼树。

任何无前缀代码集都可以表示为类似 Huffman 的二叉树，其中每个节点有 0 或 2 个子节点，叶节点表示代码。给定一棵有 N 个节点的树，我们可以构造一棵有 N+1 个节点的树，如下所示：

  1. 选择成本最小的叶节点，其中叶节点的成本为 4*（从根到叶的路径上 1 的数量）+（路径上 0 的数量）
    • 将 2 个子节点添加到该节点

因此，如果节点的代码以前是 xxxx，那么我们从代码集中删除该代码（因为它不再是叶子），并添加两个代码 xxxx0 和 xxxx1。代码集的总成本现在增加了

`成本(xxxx0) + 成本(xxxx1) - 成本(xxxx) = 成本(0) + 成本(1) + 成本(xxxx) = 5 + 成本(xxxx)

因此，mincost(N+1) <= mincost(N) + 5 + cost（N 的最佳解决方案中最便宜的代码）。我的理论是不等式应该是等式，但我还没有能够证明它。对于你列出的所有你暴力破解的值，这个语句实际上是一个相等的。

如果它是一个平等，那么要解决这个问题你会做的是：

  1. 从总成本为零的空代码集开始
    • 从 1 迭代到 10 9，执行：
      1. 在您的代码集中找到最便宜的代码
    • 通过附加 0 和 1 将该代码分成两部分
    • 将该代码的成本 + 5 添加到总成本中

如果您使用优先队列，您应该能够在 O(N log N) 时间内完成此操作。鉴于上限为 10 9 ，这可能可行，也可能不可行。

于 2008-12-06T20:16:36.287 回答
1

亚当：感谢大量的链接 - 它看起来很有希望！在阅读 Wikipedia 文章后我不确定的是如何考虑 4 的系数。我正在努力将 Project Euler 问题“映射”到算法。字母表的长度必须是 10^9 项，但重量是多少？

另一件困扰我的事情是，正如我上面提到的，霍夫曼编码充其量是 O(n) 肯定太慢了......

mattiast：我不认为你的复发有效（或者我误解了它！）。我对它的解释是：

def cost(n):
    if n == 1: return 1

    m = None
    for k in range(1, n):
        v = cost(k)+cost(n-k)+k+4*(n-k)
        if not m or v < m: m = v

    return m

print(cost(6))

它返回的值是 41，而应该是 35。同样，如果我的值是正确的，那么我在 ATT 的整数序列百科全书中找不到差异。

于 2008-12-06T22:59:15.273 回答
1

N = 10**9

t = [0]

对于 xrange(N) 中的 c ： m = min(t) t.remove(m) t.append(m+1) t.append(m+4) 打印 sum(t), t

于 2009-01-05T15:29:32.653 回答
0

我是如何解决它的，计算成本（n）高达 n=1000，然后只是猜测它是如何从那里进行的。如果你看连续值的差异，并使用整数序列的百科全书（和一些想象），你可以猜出规则。

您可以使用一种动态编程计算小 (<=1000) 示例，使用递归Cost(n) = min {Cost(k)+Cost(n-k)+k+4*(n-k) | 0 < k < n}。

于 2008-12-06T20:51:08.637 回答
0

Adam Rosenfield 的解决方案看起来很有可能奏效。这里已经很晚了（大约午夜！）所以我会一直留到早上。我在 C 中有效地实现了优先级队列，所以明天我将尝试使用它并找到解决方案。

我将报告算法的成功，但推理对我来说似乎是合理的，并且与数据非常吻合（如上所述）。但是，正如我一直在喃喃自语，一定有一个 sub O(n) 算法！;-)

于 2008-12-07T00:06:44.433 回答
0

事实证明，O[n*log(n)] 并不算太慢，但内存复杂度大约为 O(n)。然而，上面提出的算法可以进一步降低到 O(n) 时间复杂度和低内存复杂度。为此，可以使用数组 x，其中 x[a] = 成本 a 的数值数。

所做的假设给出了 10^9 的正确结果，所以我认为它们是正确的。

于 2008-12-07T18:15:50.447 回答