algorithm - 如何找到计算 x^n 的最少操作数

Question

问题出自

ACM International Collegiate Programming Contest Asia Regional Contest, Yokohama, 2006-11-05

从 x 开始并重复乘以 x , 我们可以计算 x^31三十次乘法:

x^2 = x * x, x^3 = x^2 * x, x^6 = x^3 * x^3, x^7 = x^6 *x, x^14 = x^7 * x^7 ,
x^15 = x^14 * x, x^30 = x^15 * x^15 , x^31 = x^30 * x

编写一个程序来找到最少的操作数来计算x^n通过以 x 开头的乘法和除法对于给定的正整数 n和 n<=200

对于 n = 31，最少的#operations 是 6
对于 n = 50，最少的#operations 是 7

欢迎提出任何想法。

Answer 1

看这个:http://en.wikipedia.org/wiki/Addition-chain_exponentiation

没有有效的算法可以让您获得最少的步数，并且动态规划不起作用。

我猜测 n 足够小以允许暴力解决方案通过，尽管它可能需要优化。你知道如何暴力破解吗？