¿Cómo encontrar el menor número de operaciones para calcular x^n

Question

aquí está el problema de

ACM Internacional Colegiado Programación Concurso Regional de Asia concurso, Yokohama, 2006-11-05

a partir de x y repetidamente multiplicando por x, podemos calcular x^31 con treinta y multiplicaciones:

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 

escribir un programa para encontrar el menor número de operaciones para calcular x^n por multiplicación y división empezando por x para el número entero positivo dado n y n<=200

para n = 31 los menos #Operations se 6
para n = 50 el mínimo #operations es 7

Cualquier idea es bienvenida.

Answer 1

ver esto: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

No existe un algoritmo eficiente que les permite conocer el número mínimo de pasos, y la programación dinámica no funciona.

Supongo que n es lo suficientemente pequeño como para permitir el paso de una solución de fuerza bruta, aunque podría necesitar una optimización. ¿Sabes cómo forzarlo brutalmente?