Dvojrozmerné polia - matice

Dvojrozmerné polia – matice

Dvojrozmerné pole si môžeme predstaviť ako  dvojrozmernú tabuľku s istým číslom riadku a stĺpca, v bunkách tabuľky sú samotné hodnoty.
Napríklad šachovnica je typickým príkladom štvorcovej matice (8 riadkov a 8 stĺpcov), riadky sú indexované písmenami ‘A’..’H’ a stĺpce sú indexované číslami 1..8.

Budeme sa stretávať s úlohami, kde je výhodné pracovať s „dvojrozmernou tabuľkou“ ako napríklad vzájomné zápasy tímov, šifrovanie tajných správ, rôzne hry na hracom poli, rôzne grafové úlohy a podobne.

V našich úlohách budeme často pristupovať k údajom v matici pomocou čísla riadku (najčastejšie premennou „i“) a čísla stĺpca (najčastejšie premennou „j“). Napríklad v matici K typu 3x4 (3 riadky a 4 stĺpce) je farebne vyznačený prvok K[3,2]=-12.

Deklarácia matice K v hlavičke programu bude nasledujúca:

var K: array [1..3,1..4] of integer;

Druhy matíc a ich vlastnosti

Rozmery matice a jej hodnoty zaraďujú matice do skupín s istými vlastnosťami:

Štvorcová matica typu NxN – má rovnaký počet riadkov a stĺpcov, napríklad matica A typu 3x3 bude mať prvky:

Obdĺžniková matica typu MxN – má M riadkov a N stĺpcov, napríklad matica B typu 4x2 bude mať prvky:

Hlavná diagonála matice obsahuje prvky s rovnakým číslom riadka a stĺpca (a1,1, a2,2, a3,3, ... , aN,N), napríklad prvky 1, 4 a 12 ležia na hlavnej diagonále:

Vedľajšiu diagonálu tvoria prvky, ktorých súčet čísla riadku a čísla stĺpca je N+1 (a1,N, a2,N-1, a3,N-2, ... , aN,1):

Trojuholníkový tvar matice má štvorcová matica, ktorá má pod hlavnou diagonálou nulové prvky, napríklad nasledujúca matica typu 3x3 je trojuholníková:

Lichobežníkový tvar matice má obdĺžniková matica, ktorá má pod hlavnou diagonálou nulové prvky, napríklad nasledujúca matica typu 4x3 je lichobežníková:

Jednotková matica je štvorcová matica, ktorá má na hlavnej diagonále jednotky, pod a nad hlavnou diagonálou má nuly, napríklad nasledujúca matica typu 3x3 je jednotková:

Operácie s maticami

Matice môžeme sčítavať, odčítavať, násobiť, pri operáciách platia však isté pravidlá:

• Sčítať (odčítať) môžeme len matice rovnakého typu, napríklad A(MxN) a B(MxN) tak, že sčítame (odčítame) odpovedajúce prvky matíc: c_i,j=a_i,j+b_i,j (c_i,j=a_i,j-b_i,j) pre každé i z 1..M a pre každé j z 1..N
• Násobenie matíc je o niečo zložitejšie. Napríklad vynásobením matice A(3x2) maticou B(2x4) je matica C(3x4) pre prvky ktorej platí , napríklad prvok c _1,1 dostaneme vynásobením prvého riadku matice A prvým stĺpcom matice B: c_1,1=a_1,1.b_1,1+a_1,2.b_2,1 , prvok c _1,2 dostaneme vynásobením prvého riadku matice A druhým stĺpcom matice B: c_1,2=a_1,1.b_1,2+a_1,2.b_2,2 , prvok c_1,3 dostaneme vynásobením prvého riadku matice A tretím stĺpcom matice B: c_1,3=a_1,1.b_1,3+a_1,2.b_2,3 a t.ď.

Všeobecne: A(MxL) . B(LxN) = C(MxN), kde
Násobiť môžeme len matice, z ktorých má prvá rovnaký počet stĺpcov, ako druhá riadkov!

Príklad
Je dané dvojrozmerné pole znakov, ktoré je už zaplnené nejakým textom. Napíšte program, ktorý presunie prvý riadok do druhého, druhý do tretieho, atď., až posledný do prvého (napr. motivácia: rolovanie obrázka). Najprv nie pekné riešenie:

var
  Pole: array [1..10, 1..25] of Char;
  Riadok: array [1..25] of Char;
  I, J: Integer;
begin
  ... // pole je už zaplnené
  for I := 1 to 25 do     // odložíme posledný riadok do pomocného poľa
    Riadok[I] := Pole[10, I];
  for I := 9 downto 1 do  // postupne kopírujeme všetky riadky
    for J := 1 to 25 do
      Pole[I+1, J] := pole[I, J];
  for I := 1 to 25 do     // presunieme pomocné pole do prvého riadka
    Pole[1, I] := Riadok[I];
  ...

A teraz zapíšeme to isté, ale využijeme to, že ak sú dve polia zadeklarované identicky, môžeme ich kopírovať obyčajným priradením:

type
  TRiadok = array[1..25] of Char;
  TPole = array[1..10] of TRiadok;
var
  Pole: TPole;
  Riadok: TRiadok;
  I: Integer;
begin
  ...
  Riadok := Pole[10];
  for I := 9 downto 1 do
    Pole[I+1] := Pole[I];
  Pole[1] := Riadok;
  ...

Nasledujúci príklad ukazuje spôsob prezerania prvkov dvojrozmerného poľa (zisťujeme, či matica NxN je symetrická). Najprv ukážeme nie najlepší spôsob riešenia:

const
  N = 100;
type
  TMatica = array [1..N, 1..N] of Integer;

function Symetricka(const M: TMatica): Boolean;
var
  I, J: Integer;
begin
  Result := True;
  for I := 2 to N do
    for J := 1 to I-1 do
      if M[I, J] <> M[J, I] then
      begin
        Result := False;
        Break;      
      end;
end;

Toto riešenie sa snaží použiť príkaz Break, ktorý spôsobí vyskočenie z najvnútornejšieho cyklu. To je ale nedostatočné, lebo aj tak sa budú kontrolovať ešte všetky nasledujúce riadky poľa.  Keďže po skončení cyklu táto funkcia končí, v tomto prípade môžeme použiť príkaz na vyskočenie z podprogramu - Exit.
Pozrite sa ešte na riešenie, ktoré je z programátorského hľadiska správnejšie - ak potrebujeme vyskakovať z viacerých cyklov, nepoužijeme for-cyklus ale while-cyklus:

function symetricka(const M: TMatica): Boolean;
var
  I, J: Integer;
begin
  Result := True;
  I := 2
  while Result and (I <= N) do
  begin
    J := 1;
    while Result and (J <= I-1) do
    begin
      if M[I, J] <> M[J, I] then
        Result := False;
      Inc(J);
    end;
    Inc(I);
  end;
end;

Príklad :
Deti sa hrajú s kamienkami v obdĺžnikovom poli s okienkami, v každom okienku majú istý počet kamienkov, ktoré navzájom medzi okienkami presúvajú. Zistite, s koľkými kamienkami sa deti hrajú a vypíšte aktuálny stav hracieho poľa - počet kamienkov v okienkach.
Podstatou úlohy je súčet všetkých prvkov, uložených v štruktúre matice, ako aj jej výpis.

type
  matica = array[1..100,1..100] of Integer;

var
  A: matica;
  M,N: Integer;

procedure TForm1.Button1Click(Sender: TObject);

procedure generuj(mat: matica; K,L: integer);
var
  i,j: Integer;
begin
  Randomize;
  for i := 1 to K do
    for j := 1 to L do A[i,j] := Random(100);
end;

procedure vypis(mat: matica; K,L: Integer);
var
 i,j: Integer;
 riadok: String;
begin
  for i := 1 to K do
   begin
     riadok := '';
     for j := 1 to L do
       if mat[i,j] < 10 then riadok := IntToStr(mat[i,j]) + '  ' + riadok
                        else riadok := IntToStr(mat[i,j]) + ' ' + riadok;
     Memo1.Lines.Add(riadok);
   end;
end;

function scitaj(mat: matica; K,L: Integer): Integer;
var
  i,j: Integer;
begin
  Result := 0;
  for i := 1 to K do
    for j := 1 to L do Result := Result + mat[i,j];
end;

begin
 Memo1.Clear;
 M := SpinEdit1.Value;
 N := SpinEdit2.Value;
 generuj(A,M,N);
 vypis(A,M,N);
 Edit3.Text := IntToStr(scitaj(A,M,N));
end;

end.

Príklad :

Naprogramujme jednoduchú hru „Lodičky“, pre počítač  a jedného hráča, hráč bude triafať vygenerované 3 náhodné lode zvolené počítačom v poli o veľkosti 13x13 (loď zaberá jedno políčko).
Program vyhodnotí počet úspešných a neúspešných striel. More bude predstavovať napr. nulová matica, umiestnenie lode bude číslo 1, zasiahnutá loď napr. 2.

type
  matica = array[1..13,'A'..'M'] of Char;

const
  zahlavie = 'ABCDEFGHIJKLM';

var
  lode,skryta: matica;
  riadok,k,l: Integer;
  stlpec: String[1];
  retazec: String;

procedure napln;
var
  i,j,k: Integer;
  S: Char;
begin
  Randomize;
  for i := 1 to 13 do
     for S := 'A' to 'M' do skryta[i,S] := '0';
  j := 1;
  while j <= 3 do
    begin
      i := Random(13)+1;
      k := Random(13)+1;
      S := zahlavie[k];
      if skryta[i,S] = '0' then
                              begin
                                skryta[i,S] := '1';
                                Inc(j);
                              end
    end;
  for i := 1 to 13 do
     for S := 'A' to 'M' do lode[i,S] := ' ';
end;


procedure TForm1.Button1Click(Sender: TObject);
begin
  try
   riadok := StrToInt(Edit1.Text);
  except
    ShowMessage('Zadaj číslo od 1 do 13');
    Edit1.SetFocus;
  end;
  if (riadok < 1) OR (riadok > 13) then
      begin
        ShowMessage('Zadaj číslo od 1 do 13');
        Edit1.SetFocus;
        Exit;
      end;
  stlpec := Edit2.Text;
  if (stlpec < 'A') OR (stlpec > 'M') then
      begin
        ShowMessage('Zadaj písmeno od A do M');
        Edit2.SetFocus;
        Exit;
      end;
  if skryta[riadok,stlpec[1]] = '0' then lode[riadok,stlpec[1]] := '0'
                                    else lode[riadok,stlpec[1]] := '2';
  retazec := '               ';
  if riadok < 10 then
                    begin
                       retazec[1] := ' ';
                       retazec[2] := IntToStr(riadok)[1];
                    end
                  else
                       begin
                       retazec[1] := IntToStr(riadok)[1];
                       retazec[2] := IntToStr(riadok)[2];
                    end ;
   for k := 1 to 13 do retazec[k+2] := lode[riadok,zahlavie[k]];

  Memo1.Lines.Strings[riadok] := retazec;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
 napln;
end;

end.

Úlohy na riešenie

Úloha 1
Pri sčítavaní prvkov na diagonálach nepotrebujeme prechádzať všetkými prvkami matice, lebo v istom i-tom riadku je prvok b[i,i] prvkom hlavnej diagonály a prvok b[i,N+1-i] prvkom vedľajšej diagonály (súčet indexov je N+1). Preto postačí prechádzať iba riadkami a vybrať len prvky na diagonálach. Maticu vytvoríme pomocou generátora náhodných čísel od 1 do 100, vygenerovanú maticu aj vypíšeme.

Úloha 2
Žiaci dostali test pozostávajúci z „N“ otázok, v každej z otázok sú 4 možné odpovede (práve 1 z nich je správna). Vyhodnoťte percentuálne správnosť odpovedí pre „M“ žiakov.
Program načíta správne odpovede testu do jednorozmerného poľa, a „M“ „N“-tíc odpovedí žiakov. Pre každého žiaka vypíše počet správnych odpovedí a percentuálnu úspešnosť, ako aj  úspešnosť celej triedy.
Napríklad pre 3 žiakov a 4 testové otázky bude pri istých správnych odpovediach vyzerať nasledovne:

Zaveďme si teda 3 jednorozmerné polia – spravne(N), pocet(M) a uspesnost(M), a dvojrozmerné pole – maticu klasifikacia(MxN)a porovnajte pre každého žiaka jeho odpovede so správnymi a vyhodnoťte ich.

Úloha 3
Jednotlivé štáty získali na olympiáde istý počet zlatých, strieborných a bronzových medailí, za ktorý každý štát získa 3, 2 a 1 bod. Zistite, ktorý štát získal najviac bodov a ktorý najviac medailí. (Využite 3 – stĺpcovú maticu, pričom do prvého stĺpca je výhodné načítať počty bronzových medailí, do druhého počty strieborných a do tretieho počet zlatých, potom stačí násobiť počet medailí už len číslom stĺpca 1, 2 alebo 3).