你怎么能计算出一个任意N℃的最短加法链; = 600在一秒钟？ [英] How can you compute a shortest addition chain for an arbitrary n <= 600 within one second?

问题描述

你怎么能计算最短加法链（SAC）一个任意N＆LT; = 600在一秒钟内？

How can you compute a shortest addition chain (sac) for an arbitrary n <= 600 within one second?

这是本月在 codility 的编程竞赛。

This is the programming competition on codility for this month.

加法链在数值上是非常重要的，因为他们是最经济的方式来计算x ^ N（通过连续的乘法）。

Addition chains are numerically very important, since they are the most economical way to compute x^n (by consecutive multiplications).

Knuth的计算机程序设计艺术，第2卷，半数值算法有一个很好的介绍，除了连锁店和一些有趣的属性，但我没有发现任何东西，使我能够满足严格的性能要求。

Knuth's Art of Computer Programming, Volume 2, Seminumerical Algorithms has a nice introduction to addition chains and some interesting properties, but I didn't find anything that enabled me to fulfill the strict performance requirements.

首先，我构成的（高度支化）的树（与起动1-> 2 - >（3 - > ...，4 - > ...）），使得对每个节点n，从根到n的路径是囊n个。但有关值> 400，运行时是大致相同用于制备咖啡

Firstly, I constructed a (highly branching) tree (with the start 1-> 2 -> ( 3 -> ..., 4 -> ...)) such that for each node n, the path from the root to n is a sac for n. But for values >400, the runtime is about the same as for making a coffee.

然后我用该程序发现的 <一个href="http://math.stackexchange.com/questions/131277/properties-of-shortest-addition-chains-for-small-numbers-e-g-up-to-600">some为了减少搜索空间有用的属性 。就这样，我能够建立所有的解决方案高达600，同时使咖啡。但对于N，我需要计算所有的解决方案直到n。不幸的是，codility测量类初始化的运行时，太...

Then I used that program to find some useful properties for reducing the search space. With that, I'm able to build all solutions up to 600 while making a coffee. But for n, I need to compute all solutions up to n. Unfortunately, codility measures the class initialization's runtime, too...

既然问题是<一个href="http://math.stackexchange.com/questions/109904/is-finding-the-length-of-the-shortest-addition-chain-for-a-number-n-really-np">probably NP难，我结束了硬编码的查找表。但由于codility要求为构造囊，我不知道他们是否在心中有一个查找表，让我觉得脏，像一个骗子。因此这个问题。

Since the problem is probably NP-hard, I ended up hard-coding a lookup table. But since codility asked to construct the sac, I don't know if they had a lookup table in mind, so I feel dirty and like a cheater. Hence this question.

如果您认为硬codeD，全面查找表是要走的路，你可以给一个说法，为什么你认为一个完整的计算/部分计算解决方案/启发式将无法正常工作？

推荐答案

我刚刚得到了我的黄金证书这个问题。我不会提供完整的解决方案，因为这个问题仍然可以在site.I反而给你一些提示：

I have just got my Golden Certificate for this problem. I will not provide a full solution because the problem is still available on the site.I will instead give you some hints:

1. 您可以考虑做一个深度优先搜索。
2. 存在一个最小的星链的每个n＆LT; 12509
3. 您需要知道如何修剪你的搜索空间。
4. 您需要为您正在寻找链的长度降低了良好的结合。
5. 请记住，你只需要一个解决方案，不是全部。

祝你好运。

这篇关于你怎么能计算出一个任意N℃的最短加法链; = 600在一秒钟？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！