如何在一秒钟内计算任意n <= 600的最短加法链？
如何计算一秒钟内任意n <= 600 的最短加法链（sac）？
笔记
这是本月有关Codility的编程竞赛。
加法链在数值上非常重要，因为它们是计算x ^ n（通过连续乘法）的最经济的方法。
克努斯的《计算机编程艺术》，第2卷，《半数值算法》很好地介绍了加法链和一些有趣的属性，但是我没有找到任何能够满足严格性能要求的东西。
我尝试过的（扰流板警报）
首先，我构造了一个（高度分支的） （以1-> 2->（3-> …，4->
…）开始），这样对于每个节点n，从根到n的路径是n的一个囊。但是对于> 400的值，运行时间与煮咖啡的时间相同。
然后，我使用该程序找到了
。这样一来，我就可以在煮咖啡的同时建立多达600种解决方案。但是对于n，我需要计算最多n的所有解。不幸的是，codility也会测量类初始化的运行时…
由于问题可能是NP困难的，因此我最终
了 。但是，由于codility要求
囊，所以我不知道他们是否想到了查找表，因此我感到肮脏且像作弊者。因此，这个问题。
更新资料
回答：
我刚刚获得了这个问题的黄金证书。我不会提供完整的解决方案，因为该问题仍然存在于网站上，而是给您一些提示：
- 您可以考虑进行深度优先搜索。
- 每个n <12509都有一个最小的星形链
- 您需要知道如何缩小搜索空间。
- 您需要一个合适的下限来寻找链的长度。
- 请记住，您只需要一种解决方案，而不是全部。
祝好运。
以上是 如何在一秒钟内计算任意n <= 600的最短加法链？ 的全部内容， 来源链接： utcz.com/qa/401938.html
