Cześć, mam problem z prostym algorytmem X^n. Muszę to napisać w formie iteracyjnej I rekurencyjnej na dwa sposoby: naiwny i przez podział. I problem w tym że nie bardzo wiem jak zabrać się za tą rekurencje, bo nie wiem o co chodzi z tymi dwoma sposobami :/. Jeśli byłoby łatwiej ro wystarczy mi nawet w formie diagramu i sobie poradzę :)
Dzięki za pomoc
0
1
Sposób naiwny, to
x^9 = x*x*x*x*x*x*x*x*x
8 mnożeń
przez podział, to
x^9 = x^4*x^4*x
x^4 = x^2*x^2
x^2 = x*x
cztery mnożenia
0
Wikipedia, podaje algorytmy, wraz z opisem i pseudokodem: https://en.wikipedia.org/wiki/Exponentiation_by_squaring. A oto kod w C:
/* Exponentiation by squaring iterative version of classical O(log(n)) algorithm*/
int exp_squaring_iter(int x, unsigned int n){
if (n == 0) return 1;
int y = 1;
while (n > 1){
if (is_even(n)){
x *= x;
n >>= 1;
}
else{
y *= x;
x *= x;
n = (n - 1) >> 1;
}
}
return x * y;
}