W9

Tablice wielowymiarowe

Spis treści

  pojęcie tablicy wielowymiarowej i przykłady zastosowań
  składnia deklarowania i używania
  czytanie i zapisywanie, 
  macierze: dodawanie, mnozenie,
  zadanie o znakomitości,
  znajdowaniem liczby w tablicy posortowanej wierszami i kolumnami.

-----------------------------------------------------------------------------------

Notatki

- Pojęcie tablicy dwu- (i więcej) wymiarowej,
     - przykłady zastosowań tablic wielowymairowych (mapa gór - tablica dwuwymiarowa,
        symulacja rzeczywistości - tablica trójwymiarowa),
     - przypomnienie, że w deklaracji po of  był dowolny typ, może więc być tablica,
     - Pascal nie narzuca żadnych ograniczeń na liczbę wymiarów tablicy, ale tablice
        więcej niż trójwymiarowe zdarzają się niezwykle rzadko,

- Składnia deklaracji i użycia,
     - ograniczymy się tylko do tablic dwuwymiarowych
     - deklaracja tablicy kwadratoej N*N ma postać:
          a: array[1..N] of array[1..N] of integer;
       albo 
          b: array[1..N,1..N] of integer;
     - użycie  (przy obu rodzajach deklaracji)
          a[1,2] := 13;
	  b[i,j] := 5;
	Można też pisać:
	    a[1][2] := 13;
            b[i][j] := 5;
        Pierwsza deklaracja pozwala też odwolywac sie do całych wierszy.  

-Przykłady programów działających z tablicami dwuwymiarowymi,
       - deklaracje,
	       const
		 n = ;  {Rozmiar macierzy}

		type
		 Indeks  = 0..n-1;
		 Macierz = array[ Indeks, Indeks ] of real;

		var
		  i,j          : Indeks;
		  A,B,C   : Macierz;
                  pom      : real;

  - wczytywanie i wypisywanie macierzy,

               {Wczytanie macierzy M}

		  for i:=0 to n-1 do
                   begin {Wczytuje jeden wiersz macierzy}
                     for j := 0 to n-1 do
		      begin
		       write('Podaj element [', i, ',', j, '] macierzy: ');
		       readln(M[i,j]);
                   end;

		{Wypisanie macierzy M}

		  for i:=0 to n-1 do
                   begin {Wypisuje jeden wiersz macierzy}
                     for j := 0 to n-1 do
		        write(M[i,j]:8:2);
                     writeln;
                   end;

   - dodawanie i mnożenie macierzy,

		 {Dodawanie macierzy A i B, wynik zapisujemy na macierz C.}

		  for i:=0 to n-1 do
		   {Oblicza jeden wiersz macierzy C}
		    for j := 0 to n-1 do
		     C[i,j]:=A[i,j] + B[i,j];

		 {Mnożenie przez siebie macierzy A i B, wynik zapisujemy na macierz C.}

		  for i:=0 to n-1 do
		   {Oblicza jeden wiersz macierzy C}
		    for j := 0 to n-1 do
		     {Oblicza jeden element macierzy}
		     begin
		      pom := 0;
		      for k:=0 to n-1 do
			pom := pom + A[i,k]*B[k,j];
		      C[i,j] := pom; {Można to zapisać bez pom}
		     end

   - znakomitość,
              {Osobę nazywamy znakomitością jeśli zna wszystkich, lecz nikt (oprócz}
              {jej samej) jej nie zna. Naoisz program, który dla zadanej tablicy kwadratowej
	      {Zna (Zna[i,j] wtw gdy osoba i zna osobę j) poda indeks znakomitości (o ile}
	      {jakaś znakomitość występuje).}

         Pytania pomocnicze:
         - czy zawsze musi być znakomitość? (nie)
         - czy mogą być dwie znakomitości? (nie)

		const
		 N = ; {Liczba osób}

		type
		 Indeks   = 1..N;
		 DlIndeks = 1..N+1;
		 Tablica  = array[ndeks,Indeks] of Boolean;

		var
		 Zna: Tablica;      {Zna[i,j] wtw gdy osoba i zna osobę j}
		  i,j: Indeks;         { i indeks pomocniczy, j kandydat ma znakomitosc}
		  Jest: Boolean;   { czy jest znakomitość}

		 begin
		  j := 1;
		  for i := 2 to n do
		   {P(i): jeśli wśród osób 1..i jest kandydat, to jest nim j}
		   {Zauważmy, że P(1) jest prawdziwe przed pętlą}
		     if Zna[j,i]
		     then
			 j := i;

		  {Jedynym możliwym kandydatem jest j,  sprawdzamy, czy jest osobistością} 
		  Jest := True;
		  i := 1;
		  while Jest and (i<=N) do
                     if Zna[i,j] and (not Zna[j,i] or (i=j))
		       {Wszyscy ją znają a ona nikogo, prócz siebie, nie zna}
		     then
		         i := i + 1
		     else
		         Jest := False;
		  
		  {Jeśli jest znakomitość, to Jest i jej indeksem jest j, wpp not Jest}

   - znajdowanie wartości w  tablicy posortowaej wierszami i kolumnami,
		 {Wyszukuje w posortowanej wierszami i kolumnami tablicy T liczbę x. Jeśli x znajduje się w tablicy, to   }
		 {Jest ma wartość True i T[i,j] = x, wpp. Jest ma wartość False. }

		 const
		  n = ;
		  m = ;
		  var
		    i,j     : integer;
		    Jest  : boolean;
		    T      : array[1..n,1..m] of integer;
		 begin
		  i := n;
		  j := 1;
		  Jest := false;
		  while (i>=1) and (j<=m) and not Jest do
                     { Jeśli x jest w T, to jest w części T znajdującej się powyżej i     }
		     { na prawo od elementu [i,j] (włącznie z [i,j]).                     }
		      if T[i,j] < x
		      then {x nie ma w kolumnie j}
		          j := j + 1
		      else
		         if T[i,j] > x
		         then {x nie ma w wierszu i}
		              i := i - 1
		         else {x = T[i,j]}
		             Jest := true;