8 algorithm np-complete dynamic-programming
这是问题所在
ACM国际大学生程序设计竞赛亚洲区域竞赛,横滨,2006-11-05
从x开始并重复乘以x,我们可以计算x^3130次乘法:
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
欢迎任何想法.
IVl*_*lad 11
请参阅:http://en.wikipedia.org/wiki/Addition-chain_exponentiation
没有有效的算法可以帮助您获得最少的步骤,并且动态编程不起作用.
我猜这个n小到足以允许强力解决方案通过,尽管可能需要进行优化.你知道怎么暴力吗？