Koło informatyczne 2012

Symulator mnożenia macierzy

W grafice dwu i trójwymiarowej stosowane są macierze do wyznaczania różnych przekształceń. Macierz jest tablicą dwuwymiarową, która posiada określoną liczbę wierszy i kolumn. Możesz ją sobie wyobrazić jako tabelkę.

 

 

Komórki tablicy dwuwymiarowej posiadają po dwa indeksy: indeks wiersza i indeks kolumny. Indeksy te w języku C++ zapisuje się w osobnych klamerkach. Macierz dwuwymiarową definiujemy następująco:

 

typ_elementów nazwa[liczba_wierszy][liczba_kolumn];

 

Na przykład,

 

double A[6][3];

 

oznacza tablicę dwuwymiarową o 6 wierszach i 3 kolumnach. W każdej komórce tej tablicy można przechowywać jedną daną typu double.

Jeśli liczba wierszy jest równa liczbie kolumn, to otrzymujemy macierz kwadratową (ang. square matrix).

Na macierzach określone są działania arytmetyczne (macierze są jakby rozszerzeniem liczby na wiele wymiarów). Nas najbardziej będzie interesowało mnożenie macierzy, ponieważ ta operacja jest najczęściej wykorzystywana w grafice komputerowej. Na zajęciach stworzymy program prostej symulacji mnożenia dwóch macierzy kwadratowych o wymiarach 3 x 3 (3 wiersze na 3 kolumny).

Wynikiem mnożenia macierzy A przez macierz B jest macierz C, co zapisujemy następująco:

 

C = A x B

 

Zasada otrzymywania macierzy C jest następująca:

 

Zawartość każdej komórki macierzy C[w,k] jest sumą iloczynów kolejnych komórek z wiersza w macierzy A przez kolejne komórki z kolumny k macierzy B.

Dla przykładu weźmy dwie macierze A i B o wymiarach 3 x 3:

 

A =     1   2   3  
    4   5   6  
    7   8   9  

 

B =     9   8   7  
    6   3   4  
    1   2   3  

 

Ustawmy macierz A po lewej stronie, a macierz B u góry. Macierz C niech znajdzie się na ich "przecięciu":

 

 
B =     9   8   7  
    6   3   4  
    1   2   3  
A =     1   2   3  
    4   5   6  
    7   8   9  
C =     ?   ?   ?  
    ?   ?   ?  
    ?   ?   ?  

 

Policzmy zawartość komórki C[0][0]. W tym celu sumujemy kolejne iloczyny:

 
 
B =     9   8   7  
    6   3   4  
    1   2   3  
A =     1   2   3  
    4   5   6  
    7   8   9  
C =     ?   ?   ?  
    ?   ?   ?  
    ?   ?   ?  

 

C[0][0] = A[0][0] x B[0][0] + A[0][1] x B[1][0] + A[0][2] x B[2][0]
C[0][0] = 1 x 9 + 2 x 6 + 3 x 1
C[0][0] = 9 + 12 + 3
C[0][0] = 24

 

 
B =     9   8   7  
    6   3   4  
    1   2   3  
A =     1   2   3  
    4   5   6  
    7   8   9  
C =   24   ?   ?  
    ?   ?   ?  
    ?   ?   ?  

 

Podobnie liczymy C[0][1] - elementy z wiersza 0 macierzy A będą mnożone przez elementy z kolumny 1 macierzy B, a otrzymane iloczyny sumowane:

 

 
 
B =     9   8   7  
    6   3   4  
    1   2   3  
A =     1   2   3  
    4   5   6  
    7   8   9  
C =   24   ?   ?  
    ?   ?   ?  
    ?   ?   ?  

 

C[0][1] = A[0][0] x B[0][1] + A[0][1] x B[1][1] + A[0][2] x B[2][1]
C[0][1] = 1 x 8 + 2 x 3 + 3 x 2
C[0][1] = 8 + 6 + 6
C[0][1] = 20

 

 
B =     9   8   7  
    6   3   4  
    1   2   3  
A =     1   2   3  
    4   5   6  
    7   8   9  
C =   24 20   ?  
    ?   ?   ?  
    ?   ?   ?  

 

Postępując w ten sposób systematycznie dalej, otrzymamy całą macierz wynikową C. Nasz symulator będzie właśnie tak wyliczał tę macierz i prezentował fazy tych obliczeń. Poszczególne macierze zrealizujemy jako zbiory etykiet (wiem, że można inaczej, ale to jest projekt dydaktyczny i szybkość nie jest tutaj istotna). Pokażemy, jak komponenty formy zebrać w tablice dwuwymiarowe i obsługiwać je algorytmicznie w programie.

Na początek na formie umieść komponent Panel. Komponenty Panel mogą na swojej powierzchni zawierać inne komponenty, są więc czymś w rodzaju pojemnika. U nas będą one symbolizowały macierze.

Dla panelu wstępnie ustaw własności:

Panel1

Caption = usuń wszelki tekst

Height = 145

Width = 265

 

 

Teraz mając wybrany Panel1, kliknij dwukrotnie lewym przyciskiem myszki komponent Label na palecie komponentów. Zostanie on umieszczony na panelu – jeśli przemieścisz panel na formie, to umieszczony na nim komponent również odpowiednio się przemieści. Ta własność pozwoli nam za chwilę wypozycjonować nasze macierze.

Zmień własności etykiety:

Label1

Alignment = taRightJustify
Tekst wewnątrz pola etykiety będzie dosuwany do prawej krawędzi. Dzięki temu liczby będą lepiej wyglądały w macierzy.

Caption = 00000
W sumie tekst etykiety jest tutaj zbędny, gdyż i tak zastąpimy go na początku programu. Jednak pozwoli on nam lepiej wypozycjonować etykiety w panelu.

FontSize = 10
Wielkość czcionki

StylefsBold = true
Czcionka pogrubiona

Left = 31

Top = 22

 

Teraz kliknij myszką w etykietę i naciśnij Ctrl-C. Etykieta znajdzie się w schowku Windows. Kliknij panel i wklej ze schowka 8 etykiet, naciskając Ctrl-V. Rozmieść je równomiernie w panelu.

 

 

Wybierz jeszcze raz panel i umieść na nim dodatkową etykietę w lewym górnym rogu. Będzie ona informowała nas o nazwie macierzy:

Label10

Caption = A

FontColor = clBlue

FontSize = 14

StylefsBold = true
Czcionka pogrubiona

Left = 8

Top = 4

 

Kliknij myszką w panel i skopiuj go do schowka (Ctrl-C). Następnie wklej go dwukrotnie na formę (pamiętaj, aby po wklejeniu każdego panelu skasować jego wybór, inaczej nowy panel ze schowka trafi na aktualnie wybrany panel, a nie na formę). Otrzymasz trzy panele, a na każdym z nich po 10 etykiet.

Kliknij myszką w formę, aby skasować wybór ostatniego panelu i umieść na niej trzy przyciski Button, jedną etykietę Label oraz jeden komponent Timer (znajdziesz go na zakładce System palety komponentów).

Ustaw własności:

Form1

BorderIconsbiMaximize = false

BorderStyle = bsSingle

Caption = Symulator mnożenia macierzy

ClientHeight = 370

ClientWidth = 577

Name = frmSimMul

Position = poScreenCenter

Button1

Caption = Nowe dane

Left = 16

Name = btnNew

Top = 16

Button2

Caption = Mnóż

Left = 16

Name = btnMul

Top = 48

Button3

Caption = Koniec

Left = 16

Name = btnQuit

Top = 83

Panel1

Left = 16

Name = pnlA

Top = 176

Panel2

Left = 296

Name = pnlB

Top = 16

Panel3

Left = 296

Name = pnlC

Top = 176

Label31

Alignment = taCenter
Tekst etykiety będzie centrowany wewnątrz jej obszaru.

FontSize = 16

FontStylefsBold = true

Left = 16

Name = lblMessage

Top = 366

Width = 545

AutoSize = false
Tę własność ustaw na końcu. Powoduje ona, iż pole etykiety nie będzie się automatycznie dostosowywało do jej rozmiaru i tekst zostanie faktycznie wycentrowany w obszarze etykiety.

Timer1

Interval = 500

Name = tmrSim

Timer ustaw gdzieś na formie, najlepiej obok przycisków.

 

Na koniec w panelach pnlB i pnlC zmień tekst narożnych etykiet odpowiednio na B i C. W panelu pnlB etykieta ta powinna być zielona, a w panelu pnlC czerwona.

 

 

Zaznacz w panelu pnlA pierwszą etykietę macierzy w lewym górnym rogu.

 

 

W Object Inspector wybierz własność Tag. W polu tym, które jest dostępne w każdym komponencie, można przechowywać swoje wartości do identyfikacji komponentu. Umieść tam 1, następnie wybieraj kolejne etykiety rzędami i wprowadzaj dalsze wartości do 9 (na poniższym rysunku wartości tagów dla poszczególnych etykiet zaznaczono kolorem czerwonym):

 

 

W panelu pnlB w identyczny sposób wprowadź tagi od 11 do 19, a w panelu pnlC od 21 do 29. Po wykonaniu tych operacji interfejs graficzny aplikacji jest gotowy i możemy zacząć tworzyć kod.

Na początku programu utworzymy kilka zmiennych globalnych:

 

#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

TLabel * A[3][3], * B[3][3], * C[3][3];
int Phase,CRow,CCol,Ci,CSum;
bool Simulation = false;

//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)

 

A, B i C to tablice dwuwymiarowe o 3 wierszach i 3 kolumnach. W naszym programie będą one symbolizowały macierze. Elementami tych tablic są wskaźniki do komponentów typu TLabel, czyli do etykiet. Wartości elementów macierzy będziemy przechowywali w tekstach etykiet. Nie jest to najlepszy sposób, ale z dydaktycznie poprawny. Zaletą tego rozwiązania jest to, iż nie musimy utrzymywać osobnych tablic dla wartości i osobnych dla etykiet.

Phase będzie przechowywało numer fazy animacji obliczeń. W każdej fazie są wykonywane określone działania. Opiszemy je nieco dalej.

CRow – numer wiersza macierzy C

CCol – numer kolumny macierzy C

Ci – indeks w kolumnie A i wierszu B

CSum – zapamiętuje sumę częściową iloczynów elementów z A i B. Na koniec ta suma staje się elementem macierzy C.

Simulation – wartość true oznacza wykonywanie symulacji

 

Kliknij dwukrotnie myszką przycisk Koniec i wpisz do edytora kod:

 

void __fastcall TfrmSimMul::btnQuitClick(TObject *Sender)
{
  Close();
}

 

Kliknij dwukrotnie formę i wpisz kod:

 

void __fastcall TfrmSimMul::FormCreate(TObject *Sender)
{
  int i,t,row,col,sel;

  srand(time(NULL));

  for(i = 0; i < ComponentCount; i++)
    if((t = Components[i]->Tag) != 0)
    {
         sel = t / 10;
         t = (t - 1) % 10;
         row = t / 3;
         col = t % 3;
         switch(sel)
         {
             case 0: A[row][col] = (TLabel *) Components[i];
                     A[row][col]->Caption = "0";
                     break;
             case 1: B[row][col] = (TLabel *) Components[i];
                     B[row][col]->Caption = "0";
                     break;
             case 2: C[row][col] = (TLabel *) Components[i];
                     C[row][col]->Caption = "?";
                     break;
         }
    }
    lblMessage->Caption = "";
}

 

Zadaniem tej funkcji jest odpowiednie ustawienie danych w programie. Na początku jest inicjowany generator liczb pseudolosowych. Następnie w pętli przeglądamy kolejne komponenty formy. Własność ComponentCount zawiera zawsze liczbę komponentów na formie. Dostęp do poszczególnych komponentów uzyskujemy za pomocą tablicy Components. Dla każdego przeglądanego komponentu zapamiętujemy w zmiennej t wartość tagu. Jeśli tag jest większy od 0, to oznacza on etykietę macierzy. W macierzy A kolejne etykiety mają tagi od 1 do 9, w macierzy B od 11 do 19, a w C od 21 do 29. Wydzielamy w zmiennej sel numer macierzy: 0 – A, 1 – B i 2 – C. Następnie modyfikujemy t tak, aby miało wartość od 0 do 8. Teraz bardzo łatwo jest wyznaczyć numer wiersza row i kolumny col dla znalezionego elementu. Na podstawie sel wskaźnik komponentu umieszczamy w odpowiedniej tablicy. Od tego momentu możemy odwoływać się do poszczególnych etykiet poprzez elementy tablic A, B i C. W macierzach A i B zerujemy elementy, w macierzy C ustawiamy wszędzie pytajniki.

 

Kliknij dwukrotnie myszką w przycisk Nowe dane i wprowadź kod:

 

void __fastcall TfrmSimMul::btnNewClick(TObject *Sender)
{
int row,col;

  Simulation = false;

  for(row = 0; row < 3; row++)
    for(col = 0; col < 3; col++)
    {
      A[row][col]->Caption = IntToStr(rand() % 100);
      A[row][col]->Font->Color = clBlack;
      A[row][col]->Color = clBtnFace;
      B[row][col]->Caption = IntToStr(rand() % 100);
      B[row][col]->Font->Color = clBlack;
      B[row][col]->Color = clBtnFace;
      C[row][col]->Caption = "?";
      C[row][col]->Font->Color = clBlack;
      C[row][col]->Color = clBtnFace;
    }

  lblMessage->Caption = "Nowe dane";        
}

 

Zadaniem tej funkcji jest wprowadzenie danych do macierzy A i B oraz wyzerowanie macierzy C. Na samym początku zatrzymujemy symulację. Następnie przebiegamy przez wszystkie wiersze i kolumny macierzy. Do macierzy A i B wprowadzamy liczby pseudolosowe z zakresu od 0 do 99. W macierzy C umieszczamy pytajniki. Dodatkowo przywracamy standardowe kolory tekstu i tła etykiet, ponieważ symulacja je zmienia.

 

Kliknij dwukrotnie myszką w przycisk Mnóż i wprowadź kod:

 

void __fastcall TfrmSimMul::btnMulClick(TObject *Sender)
{
  int row,col;

  Simulation = false;

  for(row = 0; row < 3; row++)
    for(col = 0; col < 3; col++)
    {
      A[row][col]->Font->Color = clBlack;
      A[row][col]->Color = clBtnFace;
      B[row][col]->Font->Color = clBlack;
      B[row][col]->Color = clBtnFace;
      C[row][col]->Caption = ".";
      C[row][col]->Font->Color = clBlack;
      C[row][col]->Color = clBtnFace;
    }
  lblMessage->Caption = "";
  Phase = CRow = CCol = CSum = 0;
  Simulation = true;
}

 

Funkcja najpierw zatrzymuje symulację, przywraca standardowe kolory etykietom, zeruje wiadomość oraz inicjuje zmienne globalne. Następnie włącza symulację.

 

Kliknij dwukrotnie myszką w Timer i wprowadź kod:

 

void __fastcall TfrmSimMul::tmrSimTimer(TObject *Sender)
{
  if(Simulation)
  {
    AnsiString c = lblMessage->Caption;
    AnsiString a = A[CRow][Ci]->Caption;
    AnsiString b = B[Ci][CCol]->Caption;

    switch(Phase)
    {
       case 0: Ci = CSum = 0;
               C[CRow][CCol]->Font->Color = clWhite;
               C[CRow][CCol]->Color = clRed;
               C[CRow][CCol]->Caption = "0";
               c = "";
               Phase++;
               break;
       case 1: A[CRow][Ci]->Font->Color = clWhite;
               A[CRow][Ci]->Color = clBlue;
               B[Ci][CCol]->Font->Color = clWhite;
               B[Ci][CCol]->Color = clGreen;
               CSum += StrToInt(a) * StrToInt(b);
               C[CRow][CCol]->Caption = IntToStr(CSum);
               c += A[CRow][Ci]->Caption + "x" + B[Ci][CCol]->Caption + " ";
               if(Ci < 2) c += "+ ";
               else       c += "= " + C[CRow][CCol]->Caption;
       case 2: ;
       case 3: ;
       case 4: ;
               Phase++;
               break;
       case 5: A[CRow][Ci]->Font->Color = clBlack;
               A[CRow][Ci]->Color = clBtnFace;
               B[Ci][CCol]->Font->Color = clBlack;
               B[Ci][CCol]->Color = clBtnFace;
               if(Ci < 2)
               {
                 Ci++;
                 Phase = 1;
               }
               else
               {
                  C[CRow][CCol]->Font->Color = clBlack;
                  C[CRow][CCol]->Color = clBtnFace;
                  if(CCol < 2) CCol++;
                  else
                  {
                     CCol = 0;
                     if(CRow < 2) CRow++;
                     else
                     {
                       Simulation = false;
                       c = "Koniec mnożenia";
                       break;
                     }
                  }
                  Phase = 0;
                  break;
               }
               break;
    }
    lblMessage->Caption = c;
  }
}

 

Symulację mnożenia wykonujemy w funkcji obsługi przerwań od Timera. Funkcja ta jest wywoływana co 0,5 sekundy. Sprawdza stan zmiennej Simulation. Jeśli zawiera ona true, to wykonywana jest jedna faza animacji. Numer fazy zawiera zmienna Phase. W kolejnych fazach wykonywane są następujące operacje:
Faza 0: Zerowana jest suma częściowa CSum oraz indeks Ci, który służy do indeksowania kolumn w A oraz wierszy w B. Następnie ustawiany jest kolor biały tekstu etykiety, która znajduje się w C w wierszu CRow i kolumnie CCol. Tło tej etykiety przyjmuje kolor czerwony. Tekst etykiety ustawiany jest na 0. Zerowana jest etykieta wiadomości.
Faza 1: Ustawione zostają kolory w odpowiednich etykietach A i B. Elementy te zostają pomnożone i dodane do sumy częściowej CSum. Suma ta trafia do odpowiedniej etykiety w C. Informacja o sumowaniu zostaje również dodana do etykiety wiadomości. Na koniec do etykiety tej dodany zostaje znak +, jeśli będą jeszcze sumowane iloczyny, lub znak " = " wraz z sumą końcową, jeśli zostały już dodane iloczyny wszystkich komórek z wiersza CRow macierzy A przez komórki z kolumny CCol macierzy B.
Fazy 2-4: Puste przebiegi.
Faza 5: Kończymy dodawanie elementów. Przywracamy im standardowe kolory. Jeśli są dalsze komórki do mnożenia (Ci < 2), to zwiększamy Ci, a Phase ustawiamy na 1. Spowoduje to wejście do fazy 1 przy kolejnym przerwaniu, czyli kontynuowanie dodawania iloczynów.

Jeśli Ci = 2, to zakończyliśmy mnożenie wiersza A przez kolumnę B i w C[CRow][CCol] mamy końcowy wynik. Przywracamy etykiecie w C standardowe kolory i przechodzimy do następnej kolumny o ile nie osiągnęliśmy już ostatniej kolumny. Jeśli osiągnęliśmy ostatnią kolumnę, to cofamy się na początek wiersza, a numer wiersza CRow zwiększamy, o ile nie był to już ostatni wiersz macierzy. Jeśli tak, to cała macierz C została wyliczona i kończymy zatrzymując symulację. W przeciwnym wypadku rozpoczynamy od fazy 0, czyli zliczania kolejnych iloczynów wiersza A przez kolumnę B.

 

Życzę zrozumienia zasad mnożenia macierzy.

 



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.