przejście do zawartości
zpr c++ quick reference
Narzędzia użytkownika
Zarejestruj się!
Zaloguj
Narzędzia witryny
Narzędzia
Pokaż stronę
Poprzednie wersje
Odnośniki
Ostatnie zmiany
Menadżer multimediów
Indeks
Zaloguj
Zarejestruj się!
Ostatnie zmiany
Menadżer multimediów
Indeks
Ślad:
power
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Algorytm power ====== Algorytm [[power]] podnosi obiekt klasy dowolnej klasy (o ile spełnia pewne wymagania) do zadanego wykładnika będącego nieujemną liczbą całkowitą. Algorytm korzysta z operatora * dlatego też, aby używać funkcji szablonowej power na własnych klasach należy przeładować operator * oraz =. ===== Nagłówek ===== Algorytm jest zdefiniowany w pliku nagłówkowym numeric lub też, niestandardowym, wstecznie kompatybilnym, algo.h. <code cpp> #include <numeric> </code> ===== Deklaracja (prototyp) power ===== Power jest przeładowaną nazwą. Istnieją dwie wersje algorytmu [[power]] <code cpp>template <class T, class Integer> inline T power(T x, Integer n); template <class T, class Integer, class MonoidOperation> T power(T x, Integer n, MonoidOperation op); </code> ===== Parametry ===== * //x// – obiekt klasy typu T tworzącej monoid (półgrupa z działaniem które ma element neutralny); x może być typu wbudowanego (int, float) jak również typu zdefiniowanego przez programistę; ważne jest aby na elementach tego typu była wykonywalna operacja mnożenia (niekoniecznie trywialna); * //n// – nieujemna liczba całkowita; ważne by typ Integer był zgodny z typem wbudowanym int; Oraz występujący w drugiej wersji [[power]]: * //op// – obiekt klasy funkcyjnej (funktor), definiującej działanie, które ma wykonywać algorytm ( w szczególności może to być mnożenie elementów); ===== Wartość zwracana ===== Obie wersje algorytmu zwracają obiekt takiego samego typu jak pierwszy argument funkcji. power(T x, Integer n) zwraca wartość x * x .... * x, gdzie x jest powtórzone n razy. Kiedy n = 0, wartość zwracana wynosi identity_element(multiplies<T>()). Druga wersja (power(T x, Integer n, MonoidOperation op) )jest podobna do pierwszej. Różnica polega na tym iż zamiast operacji * ( multiplies<T> ) wykonywana jest operacja op. Kiedy n = 0 funkcja zwraca identity_element(op). Obie funkcje należy zdefiniować, tworząc np. funktor oraz przeładowując identity_element(). ===== Działanie ===== Ponieważ kolejne mnożenie przez siebie kolejnych wartości (n-1 razy) byłoby nieefektywne, [[power]] implementuje „algorytm chłopów rosyjskich”. Jego złożoność obliczeniowa wynosi log2(n) + n1(n) gdzie log2 jest logarytmem o podstawie 2 z liczby n, a n1(n) jest liczbą jedynek w zapisie binarnym liczb n. Nie zawsze [[power]] wykonuje minimalną liczbę mnożeń; np. możliwe jest podniesienie wartości do potęgi piętnastej wykonując tylko pięć operacji mnożenia; power() wykonuje sześć. Dla prostych elementów nie powoduje to znaczącej różnicy, ale dla np. wielowymiarowych macierzy własna metoda podnoszenia do potęgi mogłaby być efektywniejsza czasowo. ===== Ostrzeżenie ===== Algorytm [[power]] nie wymaga aby operacja mnożenia na obiektach typu T była przemienna, natomiast krytyczne jest aby operacja ta była łączna. Jeśli operacja * lub op na obiektach klasy T nie jest łączna wtedy [[power]] zwróci złą wartość. ===== Przykład użycia ===== na obiektach klas wbudowanych: <code cpp> int main() { cout << "2 ** 30 = " << power(2, 30) << endl; } </code> na obiektach klas zdefiniowanych przez użytkownika: <code cpp> void main(void) { //stworzenie macierzy o wymiarze 3x3 zawierajacej 2 na przekątnej macierz<3> pierwsza(2); //wstawienie 4 na miejscu (1,2) oraz (3,2) - pola są numerowane od 1 do wymiar pierwsza.wstaw(1,2,4); pierwsza.wstaw(3,2,4); //wyswietlenie przykladowo stworzonej macierzy cout << pierwsza << "\n"; //stworzenie macierzy jednostkowej i jej wyswietlenie na ekranie macierz<3> druga(1); cout << druga << "\n"; // stworzenie macierzy zerowej; dodanie pierwszej i drugiej oraz przypisanie sumy do trzeciej macierz<3> trzecia; trzecia = pierwsza + druga; cout << trzecia << "\n"; //wyswietlenie wyniku dla operacji power(x,0) //w przypadku macierzy wynikiem takiej operacji jest maciez jednostkowa //pierwszy rodzaj algorytmu power cout << power(trzecia,0) << "\n"; //drugi rodzaj algorytmu power cout << power(trzecia,0,mnozenie<3>()) << "\n"; //stworzenie macierzy zerowej i przypisanie do niej wyniku podnoszenia macierzy do potegi 3 macierz<3> czwarta; czwarta = power(trzecia,3,mnozenie<3>()); cout <<czwarta << "\n"; } </code>
power.1229099491.txt.gz
· ostatnio zmienione: 2008/12/12 17:31 przez
makabe
Narzędzia strony
Pokaż stronę
Poprzednie wersje
Odnośniki
Do góry