欧拉计划 #219

Question

我正在尝试完成欧拉计划219，但是无法掌握它。我正在尝试使用Python，根据欧拉计划的说法，应该能够在一分钟内完成！这让我想到他们不可能希望我计算每个单独的位字符串，因为在Python中这将太慢了 - 必须有一个子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个比特串来说，这并不是最优的。有没有人能指导我应该考虑什么？

- PythonPower

---

我投票关闭此问题，因为Project Euler明确要求人们不要在线上发布他们问题的答案。如果StackOverflow发布所有问题的答案，这将会破坏他们网站的形象。 - john_science

Answer 1

Brute-force不是正确的方法。这是其中一个问题，如果你知道某个特定的事情，那么它并不难，但是如果你从未听说过那件事，那几乎是不可能的。那个东西是Huffman树。

[编辑]经过进一步审查，似乎无法使用具有特定频率的N个节点构建Huffman树，因为字符串的成本函数为4 *（# 1）+（# 0）。如果成本函数是字符串长度（或其倍数），则可以创建Huffman树。

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

1.选择具有最小成本的叶节点，其中叶节点的成本为从根到叶子的路径上的1的数量* 4 + 0的数量

- 添加2个子节点

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

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

因此，mincost(N+1) <= mincost(N) + 5 + cost(最佳解决方案中N的最便宜代码的成本)。我的理论是这个不等式应该是一个等式，但我还没有能够证明它。对于您列出的所有值，您使用暴力方法强制执行此语句事实上是一个等式。

如果它是一个等式，那么解决问题的方法就是这样做：

1. 从总成本为零的空代码集开始
   • 从1到10⁹迭代，执行以下操作：
     1. 在代码集中找到最便宜的代码
   • 通过添加0和1将该代码拆分为两个
   • 将该代码的成本+5添加到总成本中

如果您使用优先队列，则应该能够在O(N log N)时间内完成此操作。考虑到10⁹的上限，这可能是可行的，也可能不可行。

- Adam Rosenfield

Answer 2

N = 10**9

t = [0]

对于范围在N内的c： m = min(t) t.remove(m) t.append(m+1) t.append(m+4) print sum(t)，t

- Developer

Answer 3

Adam：非常感谢你提供的链接，看起来非常有前途！但在阅读维基百科文章后，我不确定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整数序列百科全书中的差异。

- PythonPower

---

你的基本情况是错误的 - 对于n = 1，使用“空”位串可以使总成本为0。 - Adam Rosenfield

没错，我告诉过你要发挥想象力！只需看看差异，你就应该注意到序列的某种形状。我不想为你毁掉所有的乐趣 :) - mattiast

Answer 4

我是如何解决这个问题的，是计算Cost(n)直到n=1000，然后猜测它从那里开始进行。如果你观察连续值的差异，并使用整数序列百科全书（以及一些想象力），你可以猜测规则。

您可以使用一种动态规划的方式计算小的（<=1000）示例，使用递归Cost(n) = min {Cost(k)+Cost(n-k)+k+4*(n-k) | 0 < k < n}。

- mattiast

Answer 5

Adam Rosenfield的解决方案看起来很有可能奏效。现在已经很晚了（大约午夜！），所以我会等到明天再试。我在C语言中有一个高效的优先队列实现，所以明天我将尝试使用它并找到解决方案。

我会报告算法的成功情况，但是推理对我来说似乎很合理，并且与数据非常接近（如上所述）。然而，正如我一直喃喃自语的那样，一定有一个小于O(n)的子算法！;-)

- PythonPower

Answer 6

原来 O[n*log(n)] 并不算太慢，但大约为 O(n) 的内存复杂度确实是。然而，上述提出的算法可以进一步降低时间复杂度至 O(n)，并且内存复杂度也很低。为了做到这一点，可以使用一个数组 x，其中 x[a] = 成本为 a 的数字值的数量。

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

- PythonPower