Monika Dekster

Laboratorium 5. Tablice wielowymiarowe

Zadania

  1. Napisz program, który na wejściu otrzymuje macierz kwadratową i sprawdza, czy jest ona trójkątna dolna. Macierz $L$ jest dolnotrójkątna, jeżeli $l_{ij} = 0$ dla $i < j$ (czyli nad główną przekątną znajdują się elementy zerowe).

    Wejście

    W pierwszym wierszu standardowego wejścia znajduje się liczba naturalna $n$ (z zakresu $[1, 1000]$) reprezentująca rozmiar macierzy. Po niej następuje $n$ wierszy, każdy z nich zawiera $n$ liczb naturalnych z zakresu $[0, 1000]$.

    Wyjście

    Na standardowym wyjściu programu powinno znaleźć się jedno słowo - YES, jeśli dana macierz jest trójkątna dolna, NO w przeciwnym przypadku.

    Przykład

    Wejście

    3
    1 0 0
    2 3 0
    4 5 6

    Wyjście

    YES

  2. Dana jest tabelka $F$ ($n\times n$) wypełniona liczbami ze zbioru $\{0, 1\}$; liczbę znajdującą się w $i$-tej kolumnie i $j$-tym wierszu tabelki oznaczamy przez $F[i,j]$. Jeśli $[i, j]$ i $[i', j']$ są dwoma miejscami w tabelce $F$, to odległością między nimi nazywamy liczbę $\max{(|i-i'|, |j-j'|)}$.

    Proszę napisać program, który:

    1. wczyta ze standardowego wejścia liczby $n$, $r$, oraz tabelkę $F$,
    2. obliczy tabelkę $W$ taką, że $W[i,j]$ jest sumą wszystkich liczb z tabelki $F$ leżących w odległości co najwyżej $r$ ($r \lt n$) od $[i,j]$.
    3. wypisze ją na standardowe wyjście.

    W pierwszym wierszu standardowego wejścia znajdują się dwie dodatnie liczby całkowite: $n$ i $r$. W kolejnych $n$ wierszach znajduje się opis tabelki $F$. Każdy z tych wierszy zawiera $n$ liczb ze zbioru $\{0, 1\}$, $i$-ta liczba zapisana w $(j+1)$-szym wierszu to $F[i,j]$.

    Przykład:

    Dla danych wejściowych:

    5 1
    1 0 0 0 1
    1 1 1 0 0
    1 0 0 0 0
    0 0 0 1 1
    0 1 0 0 0

    poprawną odpowiedzią jest:

    3 4 2 2 1
    4 5 2 2 1
    3 4 3 3 2
    2 2 2 2 2
    1 1 2 2 2

  3. Gra w życie:

    Gra toczy się na planszy o rozmiarze nXn podzielonej na nXn kwadratowych komórek. Każda komórka ma ośmiu "sąsiadów", czyli komórki przylegające do niej bokami i rogami. Każda komórka może znajdować się w jednym z dwóch stanów: może być albo "żywa" (włączona), albo "martwa" (wyłączona). Stany komórek zmieniają się w pewnych jednostkach czasu. Stan wszystkich komórek w pewnej jednostce czasu jest używany do obliczenia stanu wszystkich komórek w następnej jednostce. Po obliczeniu wszystkie komórki zmieniają swój stan dokładnie w tym samym momencie. Stan komórki zależy tylko od liczby jej żywych sąsiadów.

    Reguły gry według Conwaya:

    1. Martwa komórka, która ma dokładnie 3 żywych sąsiadów, staje się żywa w następnej jednostce czasu (rodzi się)
    2. Żywa komórka z 2 albo 3 żywymi sąsiadami pozostaje nadal żywa; przy innej liczbie sąsiadów umiera (z "samotności" albo "zatłoczenia").

    Napisz program symulujący stan gry w kolejnych chwilach czasu. Rozmiar planszy n jest podany parametrem programu. Stan początkowy generowany jest losowo z udziałem "żywych" komórek 30%. Kolejne stany wyświetlają się po naciśnięciu Enter.