Come trovare il minimo numero di operazioni per calcolare x^n

Question

qui è il problema da

ACM Internazionale Collegiata Programming Contest Asia regionale Contest , Yokohama, 2006-11-05

iniziano per x e ripetutamente moltiplicando per x, possiamo calcolare x^31 con una trentina di moltiplicazioni:

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 

scrivere un programma per trovare il minor numero di operazioni per calcolare x^n per moltiplicazione e divisione iniziando con x per il dato intero positivo n e n<=200

per n = 31 meno #Operations è 6
per n = 50 l'operazione minima è 7

Tutte le idee sono benvenute.

Answer 1

vedere questo: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

Non v'è alcun algoritmo efficiente che ti porterà il numero minimo di passi, e la programmazione dinamica non funziona.

Immagino che n sia abbastanza piccolo da consentire il passaggio di una soluzione di forza bruta, anche se potrebbe essere necessario ottimizzare. Sai come forzarlo?