Wymagane jest zapoznanie się z następującymi podrozdziałami:
P019 - Pierwszy program dla Windows
OL031 - instalacja biblioteki SDL w środowisku Dev-C++
OL032 - inicjalizacja biblioteki SDL
OL033 - powierzchnie graficzne w SDL
OL034 - przygotowanie plików własnej biblioteki graficznej
OL035 - rysowanie po powierzchni graficznej
OL036 - algorytm Bresenhama rysowania odcinka
OL037 - obcinanie grafiki do prostokątaOL038 - podstawowe algorytmy wypełniania obszarów
OL039 - algorytm Smitha
OL040 - praca w środowisku sterowanym zdarzeniami
OL041 - czcionka bitmapowa
OL042 - czcionka wektorowa
UWAGA!!!
Bieżące opracowanie NIE JEST KURSEM programowania biblioteki SDL. Są to materiały przeznaczone do zajęć na kole informatycznym w I LO w Tarnowie.
Przed pracą z tym rozdziałem utwórz w środowisku Dev-C++ nowy projekt SDL i dołącz do niego pliki SDL_gfx.cpp oraz SDL_gfx.h. Jeśli nie przeczytałeś zalecanych rozdziałów, koniecznie zrób to, a wszystko stanie się jasne. W przeciwnym razie odpuść sobie również ten rozdział. Opis funkcji bibliotecznych znajdziesz w podsumowaniu SDL008.
Artykuł nie jest już rozwijany
Macierz (ang. matrix) jest tablicą dwuwymiarową, która składa się z n wierszy i m kolumn. Umówmy się, iż wiersze będą numerowane kolejno od 0 do n-1, a kolumny od 0 do m-1. Fakt posiadania przez macierz n wierszy i m kolumn zapisujemy w sposób następujący: An x m
Elementy macierzy posiadają dwa indeksy - pierwszy indeks określa numer wiersza, w którym dany element występuje, a drugi indeks określa numer kolumny. Na przykład macierz A3 x 4 posiada trzy wiersze i 4 kolumny. Elementy tej macierzy są następujące:
a0,0 ,a0,1 ,a0,2 ,a0,3 A3 x 4 = a1,0 ,a1,1 ,a1,2 ,a1,3 a2,0 ,a2,1 ,a2,2 ,a2,3 Element a2,1 leży w wierszu o numerze 2 (wiersz trzeci z uwagi na strat numeracji od 0!) oraz w kolumnie o numerze 1 (kolumna druga!).
W języku C++ macierz możemy utworzyć następująco:
double A[n][m]; // macierz n wierszy na m kolumn utworzona statycznie double * B = new double[n * m]; // macierz n wierszy na m kolumn utworzona dynamiczniePierwszy sposób jest przydatny, gdy znamy liczbę wierszy i kolumn w trakcie tworzenia tekstu programu. Do elementów tak utworzonej macierzy odwołujemy się bezpośrednio za pomocą indeksów:
A[i][j] - element w i-tym wierszu (pamiętaj, iż numeracja idzie od zera!) i j-tej kolumnie
Drugi sposób pozwala tworzyć dynamicznie dowolne macierze. Dostęp do elementu wykonywany jest następująco:
B[m * i + j] - element w i-tym wierszu i j-tej kolumnie.
Pozornie wydaje się to bardziej czasochłonne niż sposób pierwszy. Jednakże pamiętaj, iż te same działania wykonuje mikroprocesor również w pierwszym przypadku, tyle tylko, iż kompilator ukrywa je przed tobą w zapisie A[i][j]. Dlatego kompilator musi znać wielkość wymiaru m - w przeciwnym razie nie policzyłby właściwych adresów elementów w obszarze macierzy. Jeśli m jest potęgą liczby 2, to zamiast mnożenia można wykorzystać szybkie przesunięcia bitowe w lewo. Np. dla m = 4 będzie:
B[(i << 2) + j] - element w i-tym wierszu i j-tej kolumnie macierzy B[n][4]
Dodawanie dwóch macierzy jest możliwe tylko wtedy, gdy obie posiadają tyle samo wierszy i kolumn. Wynikiem jest macierz o tych samych rozmiarach, której elementy są sumą odpowiadających sobie elementów obu macierzy:
Cn x m = An x m + Bn x m: ci,j = ai,j + bi,j, i = 0,1,...,n-1; j = 0,1,...,m-1
Algorytm dodawania dwóch macierzy
Wejście
n - liczba wierszy m - liczba kolumn A, B - macierze o n wierszach i m kolumnach Wyjście
C - macierz o n wierszach i m kolumnach będąca sumą macierzy A i B Symbole pomocnicze
i, j - indeksy wierszy i kolumn Lista kroków
K01: Czytaj n, m, A, B ; pobieramy dane wejściowe K02: Dla i = 0, 1, ..., n - 1: wykonuj krok K03 K03: Dla j = 0, 1, ..., m - 1: wykonuj C[i][j] ← A[i][j] + B[i][j] ; obliczamy sumę macierzy K04: Wypisz C ; wyprowadzamy wynik K05: Zakończ Poniżej przedstawiamy prosty program realizujący dodawanie macierzy wg powyższego algorytmu.
Dane wejściowe i wyjściowe mają następującą postać:
Dwie pierwsze liczby określają kolejno liczbę wierszy n oraz liczbę kolumn m. Następne n • m liczb określają kolejne elementy macierzy A, a kolejne n • m liczb określa elementy macierzy B. Wynik jest wyprowadzany w postaci n wierszy zawierających po m liczb i określa macierz będącą sumą macierzy A i B.
Zarówno wejście jak i wyjście można przekierować.
Przykładowe dane wejściowe:
4 4
1 4 6 7
2 5 5 5
3 2 8 9
4 3 2 1
7 9 9 1
3 2 1 1
8 8 8 8
2 1 0 1Program należy uruchamiać z konsoli znakowej - nie czeka na naciśnięcie klawisza przy zakończeniu działania.
// I Liceum Ogólnokształcące // w Tarnowie // Koło informatyczne // // P040 - dodawanie dwóch macierzy //-------------------------------- #include <iostream> using namespace std; main() { int n, m, i, j, p; cin >> n >> m; // odczytujemy wymiary macierzy // tworzymy dynamicznie macierze A, B i C p = n * m; int * A = new int[p]; int * B = new int[p]; int * C = new int[p]; // odczytujemy zawartość macierzy A for(i = 0; i < n; i++) for(j = 0; j < m; j++) cin >> A[i * m + j]; // odczytujemy zawartość macierzy b for(i = 0; i < n; i++) for(j = 0; j < m; j++) cin >> B[i * m + j]; // Obliczamy sumę macierzy A i B w C for(i = 0; i < n; i++) for(j = 0; j < m; j++) { p = i * m + j; // indeks elementu macierzy A, B i C C[p] = A[p] + B[p]; } // Wyprowadzamy wyniki cout << endl; for(i = 0; i < n; i++) { for(j = 0; j < m; j++) cout << C[i * m + j] << " "; cout << endl; } }
4 4 1 4 6 7 2 5 5 5 3 2 8 9 4 3 2 1 7 9 9 1 3 2 1 1 8 8 8 8 2 1 0 1 8 13 15 8 5 7 6 6 11 10 16 17 6 4 2 2 |
Na podobnej zasadzie do dodawania opierają się poniższe operacje:
odejmowania macierzy
Cn x m = An x m - Bn x m → ci,j = ai,j - bi,j, i = 0,1,...,n-1; j = 0,1,...,m-1
dodawania/odejmowania stałej do macierzy
An x m = An x m +/- c → ai,j = ai,j +/- c, i = 0,1,...,n-1; j = 0,1,...,m-1
mnożenia/dzielenia macierzy przez stałą
An x m = An x m • c → ai,j = ai,j • c, i = 0,1,...,n-1; j = 0,1,...,m-1
An x m = An x m : c → ai,j = ai,j : c, i = 0,1,...,n-1; j = 0,1,...,m-1
Macierze A i B uczestniczące w mnożeniu muszą posiadać odpowiednią liczbę wierszy i kolumn:
An x m x Bm x r = Cn x r
Macierz B musi posiadać tyle wierszy, ile kolumn posiada macierz A. Macierz wynikowa C posiada tyle wierszy, ile posiada macierz A oraz tyle kolumn, ile posiada macierz B. Zasadę otrzymania wyniku mnożenia C = A x B możemy prześledzić przy pomocy poniższego schematu:
B4 x 3 = b0,0 ,b0,1 ,b0,2 b1,0 ,b1,1 ,b1,2 b2,0 ,b2,1 ,b2,2 b3,0 ,b3,1 ,b2,3 A3 x 4 = a0,0 ,a0,1 ,a0,2 ,a0,3 c0,0 ,c0,1 ,c0,2 = C3 x 3 a1,0 ,a1,1 ,a1,2 ,a1,3 c1,0 ,c1,1 ,c1,2 a2,0 ,a2,1 ,a2,2 ,a2,3 c2,0 ,c2,1 ,c2,2 Kolejne wyrazy macierzy C obliczamy jako sumę iloczynów wyrazów z wiersza macierzy A przez wyrazy z kolumny macierzy B - dlatego macierz B musi posiadać tyle samo wierszy co macierz A kolumn:
c0,0 = a0,0• b0,0 + a0,1• b1,0 + a0,2• b2,0 + a0,3• b3,0
c0,1 = a0,0• b0,1 + a0,1• b1,1 + a0,2• b2,1 + a0,3• b3,1
c0,2 = a0,0• b0,2 + a0,1• b1,2+ a0,2• b2,2 + a0,3• b3,2
...
c2,2 = a2,0• b0,2 + a2,1• b1,2 + a2,2• b2,2 + a2,3• b3,2Zatem:
Cn x r = An x m x Bm x r
ci,j = m-1 ∑
k=0( ai,k • bk,j ) : i = 0,1,...,n-1; j = 0,1,...,r - 1 Algorytm mnożenia dwóch macierzy
Wejście
n - liczba wierszy macierzy A m - liczba kolumn macierzy A i wierszy macierzy B r - liczba kolumn macierzy B A, B - macierze: A n x m oraz Bm x r Wyjście
C - macierz o n wierszach i r kolumnach będąca iloczynem macierzy A i B Symbole pomocnicze
i, j, k - indeksy wierszy i kolumn si - wyliczana suma iloczynów Lista kroków
K01: Czytaj n, m, r, A, B ; pobieramy dane wejściowe K02: Dla i = 0, 1, ..., n - 1: wykonuj kroki K03...K07 K03: Dla j = 0, 1, ..., r - 1: wykonuj kroki K04...K07 K04: si ← 0 ; zerujemy sumę iloczynów K05: Dla k = 0, 1, ..., m - 1 wykonuj krok K06 ; w pętli obliczamy sumę K06: si ← si + A[i][k] • B[k][j] K07: C[i][j] ← si ; sumę wpisujemy do elementu macierzy C K07: Wypisz C K08: Zakończ Poniższy program mnoży dwie macierze. Dane wejściowe i wyjściowe są w następującym formacie:
Pierwsza liczba określa n - liczbę wierszy macierzy A oraz C.
Druga liczba określa m - liczbę kolumn macierzy A oraz wierszy macierzy B.
Trzecia liczba określa r - liczbę kolumn macierzy B i C.
Kolejne n • m liczb definiuje zawartość macierzy A. Następne m • r liczb określa zawartość macierzy B.
Wynik tworzy n wierszy zawierających po r liczb - zawartość macierzy C będącej iloczynem macierzy A i B.Wejście i wyjście można przekierować do pliku.
Poniżej mamy przykładowe dane dla programu:
3 4 5
1 2 3 4
2 3 4 5
3 4 5 6
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8Program należy uruchamiać z konsoli znakowej - nie czeka na naciśnięcie klawisza przy zakończeniu działania.
// I Liceum Ogólnokształcące // w Tarnowie // Koło informatyczne // // P041 - mnożenie dwóch macierzy //------------------------------- #include <iostream> using namespace std; main() { int n, m, r, i, j, k, si; cin >> n >> m >> r; // odczytujemy wymiary macierzy // tworzymy dynamicznie macierze A, B i C int * A = new int[n * m]; int * B = new int[m * r]; int * C = new int[n * r]; // odczytujemy zawartość macierzy A for(i = 0; i < n; i++) for(j = 0; j < m; j++) cin >> A[i * m + j]; // odczytujemy zawartość macierzy b for(i = 0; i < m; i++) for(j = 0; j < r; j++) cin >> B[i * r + j]; // Obliczamy iloczyn macierzy A i B w C for(i = 0; i < n; i++) for(j = 0; j < r; j++) { si = 0; for(k = 0; k < m; k++) si += A[i * m + k] * B[k * r + j]; C[i * r + j] = si; } // Wyprowadzamy wyniki cout << endl; for(i = 0; i < n; i++) { for(j = 0; j < r; j++) cout << C[i * r + j] << " "; cout << endl; } }
3 4 5 1 2 3 4 2 3 4 5 3 4 5 6 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 30 40 50 60 70 40 54 68 82 96 50 68 86 104 122 |
Na podstawie powyższych algorytmów napiszemy funkcje biblioteczne obsługujące operacje na macierzach, które później będziemy wykorzystywali w przekształceniach geometrycznych. Funkcje zwracają macierz wynikową.
Utwórz nowy projekt SDL. Dołącz do niego pliki SDL_gfx.h i SDL_gfx.cpp, których opis znajdziesz w podsumowaniu SDL008.
Na końcu pliku SDL_gfx.h dopisz:
double * gfxMAdd(Sint32 n, Sint32 m, double * A, double * B); double * gfxMMul(Sint32 n, Sint32 m, Sint32 r, double * A, double * B);Parametry funkcji gfxMAdd():
n - liczba wierszy m - liczba kolumn A,B - wskaźniki dodawanych macierzy
Funkcja zwraca macierz C[n][m] będącą sumą macierzy A[n][m] i B[n][m]Parametry funkcji gfxMMul():
n - liczba wierszy macierzy A i C m - liczba kolumn macierzy A i wierszy macierzy B r - liczba kolumn macierzy B i C A,B - wskaźniki mnożonych macierzy
Funkcja zwraca macierz C[n][r] będącą iloczynem macierzy A[n][m] i B[m][r]Na końcu pliku SDL_gfx.cpp dopisz:
// Dodaje macierz A do macierzy B umieszczając wynik w macierzy C // n - liczba wierszy // m - liczba kolumn // A.B - dodawane macierze //---------------------------------------------------------------- double * gfxMAdd(Sint32 n, Sint32 m, double * A, double * B) { double * C = new double[n * m]; int p; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { p = m * i + j; C[p] = A[p] + B[p]; } return C; } // Mnoży macierz A przez macierz B umieszczając wynik w macierzy C // n - liczba wierszy macierzy A i C // m - liczba kolumn macierzy A i wierszy macierzy B // r - liczba kolumn macierzy B i C // A,B - mnożone macierze //---------------------------------------------------------------- double * gfxMMul(Sint32 n, Sint32 m, Sint32 r, double * A, double * B) { double * C = new double[n * r]; for(int i = 0; i < n; i++) for(int j = 0; j < r; j++) { double si = 0; for(int k = 0; k < m; k++) si += A[i * m + k] * B[k * r + j]; C[i * r + j] = si; } return C; }
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe