Potęgowanie rekurencyjne Opcje

[lord2105]

Witajcie mój problem brzmi następująco mam do napisania klase która w sposób rekurencyjny ma realizować potęgowanie i taką napisałem,

kolejną rzeczą jest to że obiekt tej klasy ma buforować wyniki i wykorzystać bufor zamiast wykonywania metody

co przez to rozumiecie?

Ten post edytował lord2105 17.08.2010, 17:07:35

[flashdev]

Specjalnie nie podałem gotowego algorytmu, żeby zmusić czytelnika do myślenia. Ale widzę, że nie znając jeszcze tego prostego algorytmu już udało Ci się wykonać jego analizę wydajnościową (IMG:style_emoticons/default/smile.gif)

Poniżej przedstawiam mój (no bez przesady, jaki tam mój... ja nie wymyślam na poczekaniu takich mądrych rzeczy) algorytm.

Kod

// zadanie: a ^ b

// Przeliczamy b na system binarny. A tak naprawdę to nie przeliczamy, bo ona już jest zapisana binarnie. Użyjemy funkcji: bin(numer_bitu, liczba_int);

Liczymy długość pętli:
N = ceil(log2(b));

res = 1;
mul = a;
for( i = 0; i < N; i++ ){
res *= bit(i, b) ? mul : 1;
mul *= mul;
}

To cały algorytm - jedna pętla. Nie jest to co prawda rekursja, ale jak wiadomo rekursję można zrealizować iteracyjnie i vice versa.

Tak przy okazji to dokładnie w ten sam sposób działa algorytm szybkiego mnożenia, tylko że tam zamiast *=, będzie +=, oraz niezmiennik mnożenia (1), będzie zastąpiony niezmiennikiem dodawania (0).

Ten post edytował flashdev 18.08.2010, 10:25:11