项目欧拉#219

Question

我正在努力做项目Euler 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

蛮力不是正确的做法.这是其中一个问题,如果你知道某件事情,那并不难,但如果你从未听说过这件事,那实际上是不可能的.那东西是霍夫曼树.

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

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

1. 选择成本最小的叶子节点,其中叶子节点的成本为4*(从根到叶子的路径上的#的1)+(路径上的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 +成本(N的最佳解决方案中最便宜的代码).我的理论是,不平等应该是平等的,但我还没有能够证明它.对于您列出的所有强制强制的值,此声明实际上是相等的.

如果它是平等的,那么要解决问题,你会做的是:

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

如果使用优先级队列,则应该能够在O(N log N)时间内执行此操作.考虑到10 ^9的上限,这可能是也可能是不可行的.