Macierze i podstawowe operacje na nich

Powrót do spisu treści

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ąta
OL038 - 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ł w PRZEBUDOWIE


SDLMacierz (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 dynamicznie 

Pierwszy 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 Macierzy

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 1

Program 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

Mnożenie macierzy

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,2

Zatem:

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 8

Program 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

Funkcje obsługujące działania na macierzach

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;
}

Podsumowanie



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.