algorithm - 欧拉计划 #219

Question

我正在尝试做项目欧拉编号 219但我没有掌握它。我正在尝试使用 Python，根据 Euler 项目，它应该能够在一分钟内完成!这让我认为他们不可能希望我计算每个单独的位串，因为这在 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 个位串来说，它不是最佳选择。谁能指导我应该考虑什么？

Answer 1

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

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

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

1. 选择具有最小成本的叶节点，其中叶节点的成本为 4*(从根到叶的路径上的 1 的数量)+(路径上的 0 的数量)
   • 向该节点添加 2 个 child

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

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

因此，mincost(N+1) <= mincost(N) + 5 + cost(N 的最佳解决方案中的最便宜代码)。我的理论是，不平等应该是平等的，但我还没有能够证明这一点。对于您列出的所有您强行使用的值，该语句实际上是相等的。

如果它是相等的，那么要解决这个问题你会这样做:

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

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