8
tutaj jest problem zjak znaleźć najmniejszą liczbę operacji obliczyć x^n
ACM International CollegiateProgramming Contest Azja Regional Contest, Yokohama, 2006-11-05
Począwszy od X i wielokrotnie pomnożenie przez x, możemy obliczyć x^31 z trzydziestoma mnożenia:
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
napisać program znaleźć najmniejszej liczby operacji, w celu obliczenia x^n przez mnożenie i dzielenie wychodząc z x dla danej liczby całkowitej n i n<=200
dla n = 31 najmniej #Operations wynosi 6
dla n = 50 najmniej # operacji to 7
Wszelkie pomysły są mile widziane.
Podpowiedź: http://en.wikipedia.org/wiki/Exponentiation_by_squaring –
@Martinho Fernandes - potęgowanie przez kwadraty nie użyje minimalnej liczby operacji. – IVlad