zpr c++ quick reference

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 klasy zdefiniowanej 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>

===Szablon klasy macierz:===


<code cpp>
//definicja szablonu klasy macierzy kwadratowej ktora za parametr przyjmuje rozmiar tablicy 
template <int rozmiar>
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<rozmiar>(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<rozmiar> 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<rozmiar> 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 <int rozmiar>
struct mnozenie //: public binary_function<macierz<rozmiar>, macierz<rozmiar>, macierz<rozmiar>> 
{
  macierz<rozmiar> operator()(const macierz<rozmiar>& x, const macierz<rozmiar>& 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 <int rozmiar>
macierz<rozmiar>	identity_element(mnozenie<rozmiar>) {
	return macierz<rozmiar>(1);  
};
</code>
zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
