nasıl hesaplamak için operasyonların az sayısını bulmak için x^n

Question

burada

ACM Uluslararası Collegiate Programlama Yarışması Asya Bölge Yarışması, Yokohama, 2006-11-05

gelen sorundur

x ile başlayan ve art arda x ile çarpılması biz otuz çarpmalar ile x^31 hesaplayabiliriz:

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 

n<=200

için

= 31 en az #operations bir n 6
verilen pozitif tamsayı n ve için x başlayarak çarpma ve bölme ile x^n hesaplamak için işlemlerin en az sayısını bulmak için bir program bilgileri = 50 en az #operasyonlar 7

Herhangi bir fikir kabul edilir.

Answer 1

bu bakınız: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

Orada size olan en az adımda alacak hiçbir verimli algoritma ve dinamik programlama çalışmıyor.

Ben optimize edilmesi gerekebilir rağmen n, bir kaba kuvvet çözüm geçmesine izin verecek kadar küçük olduğunu tahmin ediyorum. Bunu nasıl zorlayacaklarını biliyor musun?