wie die geringste Anzahl von Operationen finden x zu berechnen^n

Question

hier ist das Problem von

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

Beginnend mit x und Multiplikation wiederholt von x können wir x^31 mit dreißig Multiplikationen berechnen:

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 

ein Programm schreiben, die geringste Anzahl von Operationen zu finden, mit x für die gegebene positive ganze Zahl ist und nn<=200

für n = 31 n für den am wenigsten #Operations 6
beginnend x^n durch Multiplikation und Division zu berechnen = 50 am wenigsten #Operationen ist 7

Alle Ideen sind willkommen.

Answer 1

sehen: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

Es gibt keinen effizienten Algorithmus, der die Mindestanzahl von Schritten erhalten werden, und die dynamische Programmierung funktioniert nicht.

Ich vermute, dass n klein genug ist, um eine Brute-Force-Lösung zu ermöglichen, obwohl es möglicherweise optimiert werden muss. Weißt du, wie man es zwingt?