====== Algorytm power ======
Algorytm [[power]] podnosi obiekt 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ć operatory * oraz =.
===== Nagłówek =====
Algorytm jest zdefiniowany w pliku nagłówkowym numeric lub też, niestandardowym, wstecznie kompatybilnym, algo.h.
#include
===== Deklaracja (prototyp) power =====
Power jest przeładowaną nazwą. Istnieją dwie wersje algorytmu [[power]]
template
inline T power(T x, Integer n);
template
T power(T x, Integer n, MonoidOperation op);
===== 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()).
Druga wersja (power(T x, Integer n, MonoidOperation op) )jest podobna do pierwszej. Różnica polega na tym iż zamiast operacji * ( multiplies ) 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(). (patrzy przykład poniżej)
===== 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:===
int main() {
cout << "2 ** 30 = " << power(2, 30) << endl;
}
===Na obiektach klasy zdefiniowanej przez użytkownika:===
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 <
===Szablon klasy macierz:===
//definicja szablonu klasy macierzy kwadratowej ktora za parametr przyjmuje rozmiar tablicy
template
class macierz
{
private:
int rodzaj; // 0 identycznosciowa dla operacji dodawania; 1 identycznosciowa dla operacji mnozenia
float tablica[rozmiar][rozmiar];
public:
//destruktor
~macierz(void){};
//konstruktor bezargumentowy inicjuje tablice zerami
macierz(void)
{
for( int i = 0; i < rozmiar; i++)
{
for (int j = 0; j < rozmiar; j++)
{
tablica[i][j] = 0.0;
}
}
};
//konstruktor kopiujacy
macierz(const macierz& M)
{
rodzaj = M.rodzaj;
for( int i = 0; i < rozmiar; i++)
{
for (int j = 0; j < rozmiar; j++)
{
tablica[i][j] = M.tablica[i][j];
}
}
//*this = M;
};
//konstruktor przyjmujący argument klasy int pozwalający tworzyć macierz jednostkową: macierz(1)
//kontruktor ten tworzy macierz wypelniona zerami oprocz przekatnej gdzie znajduja sie jedynki
//niezbedny dla wlasciwego dzialania operacji power ktora dla zerowego wykladnika zwraca wartosc __T(0) gdzie __T jest obiektem klasy dla ktorej wywolany zostal algorym power
macierz(int x )
{
rodzaj = x;
for( int i = 0; i < rozmiar; i++)
{
for (int j = 0; j < rozmiar; j++)
{
if( i == j)
tablica[i][j] = (float)rodzaj;
else
tablica[i][j] = 0;
}
}
};
//przeladowany operator przypisania niezbedny dla poprawnego dzialania algoryty power, ktory wykorzystuje przypisanie wczasie wykonywania iloczynow czesciowych
macierz& operator=( const macierz& M)
{
rodzaj = M.rodzaj;
for( int i = 0; i < rozmiar; i++)
{
for (int j = 0; j < rozmiar; j++)
{
tablica[i][j] = M.tablica[i][j];
}
}
return *this;
};
//przeladowany operator mnozenia niezbedny dla poprawnego dzialania algorytmu power(T x, Integer n)
//w algorytmie (T x, Integer n, MonoidOperation op) sami mozemy zdefiniowac ktora operacja ma byc wykonywana na obiekcie x klasy T
macierz operator*( const macierz& M) const
{
macierz temp;
for( int i = 0; i < rozmiar; i++)
{
for (int j = 0; j < rozmiar; j++)
{
for (int k = 0; k < rozmiar; k++)
temp.tablica[i][j] += tablica[i][k] * M.tablica[k][j];
}
}
return temp;
};
//przeladowany operator dodwania - przydatny przy testowaniu klasy
macierz operator+( const macierz& M) const
{
macierz temp;
for( int i = 0; i < rozmiar; i++)
{
for (int j = 0; j < rozmiar; j++)
{
temp.tablica[i][j] = tablica[i][j] + M.tablica[i][j];
}
}
return temp;
};
//przeladowany operator na klasie ostream; sluzy do wypisania wyniku; przydatny przy testowaniu
friend ostream& operator<<(ostream& wy, const macierz& M)
{
for( int i = 0; i < rozmiar; i++)
{
for (int j = 0; j < rozmiar; j++)
{
wy << M.tablica[i][j] << "\t";
}
wy << "\n";
}
return wy;
};
//metoda klasy sluzaca do ustawiania wartosci w tablicy
//x oraz y sa z zakresu 1.. rozmiar - konwencja bardziej naturalna
void wstaw(int x, int y, float wartosc)
{
if ( ( x > 0 ) && ( x <= rozmiar ) && ( y > 0 ) && ( y <= rozmiar ) )
tablica[x-1][y-1] = wartosc;
};
//macierz& operator+=( const macierz &);
//macierz& operator*=( const macierz &);
};
//funktor - klasa definiujaca operator mnozenia dla klasy macierz.
//wlasciwie jest tutaj wykorzystany operator * zdefiniowany wewnatrz klasy
//ale mozna utworzyc wlasna metode mnozenia, np bardziej efektywna gdybysmy uzywali specjalnego rodzaju klas ipt. i latwo podmieniać w wywolaniu algorytmu power
template
struct mnozenie //: public binary_function, macierz, macierz>
{
macierz operator()(const macierz& x, const macierz& y) const
{
return x * y;
}
};
//przeladowana funkcja zwracajaca element identycznosciowy dla mnozenia macierzy
//tak jak wyzej mozna przeladowac ja wiele razy w zaleznosci od operacji mnozenia
template
macierz identity_element(mnozenie) {
return macierz(1);
};