Laboratorium 6: Omówienie zadania zaliczeniowego 1

Rozpoczynamy pracę nad pierwszym zadaniem zaliczeniowym. Oto przykładowe zadania z poprzednich lat:

Rok 2010/2011, zadanie 1

Wprowadzenie

W Pokera gra się talią 52 różnych kart. Karty mają jedną z 13 wartości, w kolejności od najwyższej do najniższej (po każdej w nawiasie podajemy oznaczenie):

as ( A )
król ( K )
dama ( Q )
walet ( J )
dziesiątka ( T )
dziewiątka ( 9 )
ósemka ( 8 )
siódemka ( 7 )
szóstka ( 6 )
piątka ( 5 )
czwórka ( 4 )
trójka ( 3 )
dwójka ( 2 )

oraz jeden z 4 kolorów (w nawiasach oznaczenie):

pik ( s )
kier ( h )
karo ( d )
trefl ( c )

Zapisując informacje o karcie najpierw podajemy znak określający jej wartość a następnie znak określający kolor.

Zbiór pięciu kart z talii nazywamy ręką. Rękę zapisujemy, podając ciąg 10 znaków składający się z 5 par znaków będących zapisem poszczególnych kart.

Ręce porównuje się pod względem siły. O sile ręki decyduje jej układ (kategoria) - silniejsza jest ręka z silniejszym układem. Porównując siłę rąk o tym samym układzie, uwzględniamy wartości poszczególnych kart.

Wyróżniamy 9 układów, w kolejności od najsilniejszego:

poker: Pięć kart o kolejnych wartościach, w tym samym kolorze, np. 9dQdTdJd8d.
Dodatkowo, za pokera uznajemy układ kart w jednym kolorze o wartościach 5, 4, 3, 2 oraz asa, który w takiej ręce ma wartość 1. Przy porównaniu siły z innym pokerem decyduje najwyższa wartość karty.
kareta: Ręka zawierająca cztery karty o tej samej wartości, np. 6c6d6hAc6s.
Przy porównaniu siły z inną karetą decyduje powtarzająca się wartość a gdy ta jest równa, wartość karty, która się nie powtarza.
ful: Ręka zawierająca karty o dwóch wartościach - jednej powtarzającej się trzy razy i jednej powtarzającej się dwa razy, np. 4sJd4hJh4c.
Przy porównaniu z innym fulem o sile decyduje wartość powtarzająca się trzykrotnie a gdy ta jest równa - wartość powtarzająca się dwukrotnie.
kolor: Ręka składająca się z kart w tym samym kolorze, ale nie o kolejnych wartościach, np. 3s7s2sAsQs.
Przy porównaniu z innym kolorem o sile decyduje najwyższa wartość karty, gdy ta jest równa - wartość druga co do wysokości itd.
strit: Ręka składająca się z kart o kolejnych wartościach, ale nie w tym samym kolorze, np. 9s6c8s5h7c.
Jak w przypadku pokera, stritem jest też ręka z kartami o wartościach 5, 4, 3, 2 i as, który ma w takiej ręce wartość 1. Przy porównaniu z innym stritem o sile decyduje najwyższa wartość karty.
trójka: Ręka składająca się z kart o trzech różnych wartościach, z których jedna powtarza się trzykrotnie, np. 2cJhAcJsJd.
Przy porównaniu z inną trójką o sile decyduje wartość powtarzająca się trzykrotnie, gdy ta jest równa - wyższa z dwóch pozostałych wartości a gdy i ta jest równa - niższa z dwóch pozostałych wartości.
dwie pary: Ręka składająca się z kart o trzech różnych wartościach, z których dwie powtarzają się dwukrotnie, np. Kd6cKh3d6d.
Przy porównaniu z innymi dwiema parami o sile decyduje wyższa z wartości powtarzających się dwa razy, gdy jest równa - niższa z wartości powtarzających się dwa razy a gdy i ta jest równa - wartość karty nie
powtarzająca się.
para: Ręka składająca się z kart o czterech różnych wartościach, np. Ad8h3c5c8s.
Przy porównaniu z inną parą o sile decyduje wartość powtarzająca się dwukrotnie, gdy ta jest równa - najwyższa z pozostałych, gdy ta jest równa - kolejna co do wysokości itd.
wysoka karta: Ręka, która nie ma żadnego z wymienionych powyżej układów, np. 6s3hAs2sQs.
Przy porównaniu z inną kartą o takim układzie o sile decyduje najwyższa wartość karty, gdy ta jest równa - wartość druga co do wysokości itd.

Obserwacje

Kolejność kart w ręce nie ma znaczenia.

Kolorów kart używa się tylko do stwierdzenia, czy w ręce jest układ "kolor" lub "poker". Porównując indywidualne karty, ich koloru nie uwzględniamy.

Dwie ręce są równie silne wtedy i tylko wtedy, gdy wartości kart w obu rękach są takie same i albo obie ręce mają układ "kolor" lub "poker" albo żadna z nich nie ma takiego układu.

W stricie lub pokerze złożonym z kart o wartościach as, 2, 3, 4, 5 kartą o najwyższej wartości jest 5. Oznacza to, że np. strit
Ac2s3h4d5c
jest słabszy od
2c3s4h5d6c
mimo, że w tym pierwszym występuje as.

Polecenie

Napisz program, który wczyta z wejścia dwa wiersze zawierające 10-znakowe reprezentacje rąk pokerowych i wypisze na wyjście wiersz z nazwami ich układów, umieszczając pomiędzy nimi znak '=' gdy obie ręce mają równą siłę, '<' gdy pierwsza ręka jest słabsza od drugiej,'>' gdy pierwsza ręka jest silniejsza od drugiej.

Przykłady

Dla danych:
6s3hAs2sQs
9dQdTdJd8d
program powinien wypisać:
wysoka karta<poker
Dla danych:
Kd6cKh3d6d
6h3cKs6dKh
program powinien wypisać:
dwie pary=dwie pary
Dla danych:
2cJhAcJsJd
JcJhQhJdKc
program powinien wypisać:
trojka>trojka

Uwagi

Wolno założyć, że dane są poprawne.

By uniknąć problemów z reprezentacją znaków specyficznych dla alfabetu polskiego, w wyniku programu piszemy "trojka", bez kreski nad 'o'.

Informacje uzupełniające

Zapis rozwiązania zadania może uprościć zastosowanie instrukcji case.

Zadanie można rozwiązać na wiele sposobów. Da się to zrobić nawet za pomocą czystego drzewa decyzyjnego, ale kod takiego programu byłby gigantyczny. By zmniejszyć jego rozmiar, trzeba się posłużyć się pętlami, tablicami i procedurami.

Jak w przypadku każdego zadania programistycznego, sugerujemy pracę metodą kolejnych rozszerzeń. Warto tu zacząć od programu rozpoznającego układ, a dopiero później dodać porównywanie wartości rąk. Samo rozpoznawanie ręki również dzielimy na podproblemy związane z poszczególnymi układami. Można
np. zacząć od programu rozpoznającego kolor a następnie rozszerzać go o kolejne układy.

Ponieważ wolno założyć poprawność danych, wygodnie będzie wczytywać je za pomocą operacji readln() na zmienną typu String. Na wartościach tego typu moża operować na pomocą funkcji length() dającej długość napisu oraz operatora [] pozwalającego na odwoływanie się do poszczególnych znaków tak, jak do elementów tablicy. Demonstruje to program (podkreslenia.pas):

program podkreslenia;
 
var s : String;
    i : Integer;
 
begin
    readln(s);
    if s <> '' then begin
        write(s[1]);
        for i := 2 to length(s) do
            write('_', s[i])
    end;
    writeln
end.

Rok 2010/2011, zadanie 1 - rozwiązanie

program wp10zad1;
 
const
    AS = 14;
    KOLORY = 4;
    REKA = 5;
 
var s1, s2, n1, n2 : String;
    u1, u2 : Integer;
    w1, w2 : String;
 
procedure rozpoznaj(s : String; var u : Integer; var n, w : String);
var jestKolor : Boolean;
    i, j, x : Integer;
    wystapienia : array [2 .. AS] of 0 .. KOLORY;
    powtorzenia : array [0 .. KOLORY] of 0 .. REKA;
begin
    for i := 2 to AS do
        wystapienia[i] := 0;
    powtorzenia[0] := REKA;
    for i := 1 to KOLORY do
        powtorzenia[i] := 0;
    jestKolor := true;
    assert(length(s) = 2 * REKA);
    for i := 1 to REKA do begin
        assert(s[2 * i] in ['c', 'd', 'h', 's']);
        jestKolor := jestKolor and (s[2 * i] = s[2]);
        x := pos(s[2 * i - 1], '123456789TJQKA');
        assert(x > 1);
        assert(wystapienia[x] < KOLORY);
        dec(powtorzenia[wystapienia[x]]);
        inc(wystapienia[x]);
        inc(powtorzenia[wystapienia[x]])
    end;
    w := '';
    for i := KOLORY downto 1 do
        for j := AS downto 2 do
            w := w + chr(ord('0') + ord(wystapienia[j] = i));
    if pos('1000000001111', w) > 0 then begin
        w[(AS - 1) * KOLORY - (AS - 2)] := '0';
        w := w + '1'
    end;
    u := 9 * ord(jestKolor) + 8 * ord(pos('11111', w) > 0) +
            11 * powtorzenia[4] + 7 * powtorzenia[3] + 3 * powtorzenia[2];
    case u of
        0 :
            n := 'wysoka karta';
        3 * 1 :
            n := 'para';
        3 * 2 :
            n := 'dwie pary';
        7 :
            n := 'trojka';
        8 :
            n := 'strit';
        9 :
            n := 'kolor';
        7 + 3 * 1 :
            n := 'ful';
        11 :
            n := 'kareta';
        9 + 8 :
            n := 'poker'
    end
end;
 
begin
    readln(s1);
    rozpoznaj(s1, u1, n1, w1);
    readln(s2);
    rozpoznaj(s2, u2, n2, w2);
    if (u1 = u2) and (w1 = w2) then
        writeln(n1, '=', n2)
    else if (u1 < u2) or ((u1 = u2) and (w1 < w2)) then
        writeln(n1, '<', n2)
    else
        writeln(n1, '>', n2)
end.

Rok 2009/2010, zadanie 1

Wprowadzenie

Tematem zadania jest interpreter, czyli "program wykonujący programy" w języku Malina ("MAłe LItery i NAwiasy klamrowe").

Składnia programów w Malinie opisana jest gramatyką:

Program -> CiągInstrukcji
CiągInstrukcji -> &epsilon; | CiągInstrukcji Instrukcja
Instrukcja -> InstrukcjaOdejmowania | InstrukcjaPętli
InstrukcjaOdejmowania -> Zmienna Zmienna
InstrukcjaPętli -> Zmienna { CiągInstrukcji }
Zmienna -> ZmiennaZwykła | ZmiennaSpecjalna
ZmiennaZwykła -> a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x
ZmiennaSpecjalna -> y|z

ε jest tu oznaczeniem słowa pustego a małe litery i nawiasy klamrowe to symbole końcowe gramatyki. Oprócz małych liter i klamerek, żadne inne znaki, nawet spacje, w programie nie mogą wystąpić.

Program w Malinie jest ciągiem instrukcji, które wykonujemy w kolejności od pierwszej do ostatniej.

Mamy dwa rodzaje instrukcji: odejmowanie i pętlę.

Instrukcja odejmowania postaci Zmienna Zmienna odejmuje wartość drugiej zmiennej od pierwszej. Np. instrukcji Maliny postaci ab odpowiada w Pascalu a := a - b.

Instrukcja pętli postaci Zmienna { CiągInstrukcji } wykonuje ciąg instrukcji w klamerkach dopóki wartość zmiennej przed klamerką otwierającą jest większa od zera. Np. instrukcji Maliny postaci a{...} odpowiada w Pascalu while a > 0 do begin ... end.

Program w Malinie ma dostęp do 26 zmiennych o nazwach od a do z. Zmienne od a do w mają wartości początkowe 0, a zmienna x ma wartość początkową 1. Dwie zmienne, y i z, mają specjalne znaczenie. Zmienna y służy do realizacji wejścia/wyjścia liczbowego (od
"lYczby"), a zmienna z do realizacji wejścia/wyjścia znakowego (od "Znaki").

Jeśli zmienna y wystąpiła na drugiej pozycji w instrukcji przypisania lub przed klamerką otwierającą w pętli, pobranie jej wartości powoduje odczytanie z wejścia liczby całkowitej. Np. instrukcja
ay wczytuje z wejścia liczbę i odejmuje ją od wartości zmiennej a.

Jeśli zmienna y wystąpiła na pierwszej pozycji w instrukcji odejmowania, wykonanie instrukcji powoduje wypisanie na wyjście liczby będącej wartością zmiennej z drugiej pozycji. Np. instrukcja ya wypisuje na wyjście wartość zmiennej a.

Jeśli zmienna z wystąpiła na drugiej pozycji w instrukcji przypisania lub przed klamerką otwierającą w pętli, pobranie jej wartości powoduje odczytanie z wejścia znaku i przekazanie jego kodu. Gdyby na wejściu znaków nie było, przekazaną wartością będzie -1. Np. instrukcja
az wczytuje z wejścia znak i odejmuje jego kod od wartości zmiennej a.

Jeśli zmienna z wystąpiła na pierwszej pozycji w instrukcji odejmowania, wykonanie instrukcji powoduje wypisanie na wyjście znaku o kodzie, będącym wartością zmiennej z drugiej pozycji tej instrukcji. Np. instrukcja za wypisuje na wyjście znak, którego kod jest zapisany na
zmiennej a.

Polecenie

Napisz interpreter programów w języku Malina.

Interpreter powinien sprawdzić, czy argument, z którym został wywołany, jest poprawnym składniowo programem w Malinie i jeśli tak, wykonać go, a jeśli nie, wypisać odpowiedni komunikat o błędzie.

Przykłady programów w Malinie

Wczytanie liczby i wypisanie liczby o 1 większej:

  ./malina axaybayb

Sumowanie wyrazów ciągu nieujemnych liczb zakończonego zerem:

  ./malina x{aaayxxxaba}yb

Wypisywanie liczb od 10 do 1:

  ./malina axaxbaabaxcacac{yccx}

Wyznaczanie algorytmem Euklidesa NWD dwóch liczb wczytanych z wejścia:

  ./malina aybycac{dddcdbd{baddcc}c{abcc}ca}vbyv

Wypisanie na wyjście wiersza o treści Hello:

  ./malina axaxbabacbcbdcdcededfefefczffafbfxfezffcfxzfzffcfbfxzfbcbxbxzb

Rozwiązanie zadania laboratoryjnego o medianie trzech liczb:

  ./malina aybycyeafbefe{dagbaaagbbbdee}haibjckjkawxlwk{yhkkll}l{mjmbnwm{yjmmnn}n{yinn}ll}

Rozwiązanie zadania laboratoryjnego o choince:

  ./malina axaxbabacbcbdcdcededsegegcgaucuanyini{kkkijkjxj{zsjx}jnjij{zgzgjx}zgzuix}icibixi{jnjxjxj{zsjx}zgzgzgzuix}

Informacje uzupełniające

Do rozwiązania zadania będzie potrzebnych kilka nowych funkcji standardowych. Przedstawimy je na przykładzie programu realizującego "szyfr" ROT13 (zastępowanie litery literą, która jest w alfabecie o 13 pozycji dalej, cyklicznie). Dla uproszczenia, poniższy program zajmuje się tylko małymi literami (rot13.pas):

program rot13;
 
var s : String;
    i : Integer;
    c : Char;
 
begin
    if paramCount <> 1 then begin
        writeln('Program oczekuje jednego argumentu');
        halt
    end;
    s := paramStr(1);
    for i := 1 to length(s) do begin
        c := s[i];
        if ('a' <= c) and (c <= 'z') then
            write(chr(((ord(c) - ord('a') + 13) mod 26) + ord('a')))
        else
            write(c)
    end;
    writeln
end.

Mamy tu:

funkcje paramCount() i paramStr()
procedurę halt
typ String, funkcję length(), odczytywanie znaków napisu
typ Char, funkcje chr() i ord()

Przyda się też wczytywanie z wejścia pojedynczych znaków za pomocą operacji read() z argumentem będącym zmienną typu Char oraz funkcja eof(), której bezparametrowy wariant sprawdza, czy na wejściu jest koniec danych.

Rok 2009/2010, zadanie 1 - rozwiązanie

program wp09zad1;
 
procedure zbadajPoprawnosc(prg : String);
var otwarte, litery, i : Integer;
 
    procedure sprawdz(w : Boolean);
    begin
        if not w then begin
            writeln('Blad skladniowy na pozycji ', i);
            halt
        end
    end;
 
begin
    litery := 0;
    otwarte := 0;
    for i := 1 to length(prg) do
        if prg[i] = '{' then begin
            sprawdz(litery mod 2 = 1);
            litery := 0;
            otwarte := otwarte + 1
        end else if prg[i] = '}' then begin
            sprawdz((otwarte > 0) and (litery mod 2 = 0));
            litery := 0;
            otwarte := otwarte - 1
        end else begin
            sprawdz(('a' <= prg[i]) and (prg[i] <= 'z'));
            litery := litery + 1
        end;
    i := length(prg) + 1;
    sprawdz((otwarte = 0) and (litery mod 2 = 0))
end;
 
procedure wykonajProgram(prg : String);
var pc : Integer;
    mem : array ['a' .. 'x'] of Integer;
    c : Char;
 
    function para(i, d : Integer) : Integer;
    var ile : Integer;
    begin
        ile := 1;
        while ile <> 0 do begin
            i := i + d;
            if prg[i] = '{' then
                ile := ile + d
            else if prg[i] = '}' then
                ile := ile - d
        end;
        para := i
    end;
 
    function wartosc(zmienna : Char) : integer;
    var c : Char;
    begin
        if zmienna = 'y' then
            read(wartosc)
        else if zmienna = 'z' then
            if eof then
                wartosc := -1
            else begin
                read(c);
                wartosc := ord(c)
            end
        else
            wartosc := mem[zmienna]
    end;
 
    procedure odejmij(zmienna : Char; co : Integer);
    begin
        if zmienna = 'y' then
            writeln(co)
        else if zmienna = 'z' then
            write(chr(co))
        else
            mem[zmienna] := mem[zmienna] - co
    end;
 
begin
    for c := 'a' to 'w' do
        mem[c] := 0;
    mem['x'] := 1;
    pc := 1;
    while pc <= length(prg) do
        if prg[pc] = '}' then
            pc := para(pc, -1) - 1
        else if prg[pc + 1] = '{' then
            if wartosc(prg[pc]) > 0 then
                pc := pc + 2
            else
                pc := para(pc + 1, 1) + 1
        else begin
            odejmij(prg[pc], wartosc(prg[pc + 1]));
            pc := pc + 2
        end
end;
 
begin
    if paramCount <> 1 then
        writeln('Interpreter jezyka Malina oczekuje jednego argumentu')
    else begin
        zbadajPoprawnosc(paramStr(1));
        wykonajProgram(paramStr(1))
    end
end.

Rok 2008/2009, zadanie 1

Wprowadzenie

Gramatyki bezkontekstowe będziemy zapisywali w postaci:

< N,T,P,S >

gdzie:

N: zapis zbioru symboli pomocniczych
T: zapis zbioru symboli końcowych
P: zapis zbioru produkcji postaci "A->w", gdzie "A" to symbol pomocniczy, a "w" to ciąg prawych stron produkcji tego symbolu, rozdzielonych znakiem "|". Prawa strona produkcji to, być może pusty, ciąg symboli
pomocniczych i końcowych.
S: nazwa jednego z symboli pomocniczych

Zapis zbioru rozpoczyna się od znaku '{' a kończy znakiem '}'. Pomiędzy tymi znakami umieszczamy, rozdzielone przecinkami, elementy zbioru.

Zakładamy, że w zapisie gramatyki nie ma żadnych innych znaków, oprócz tych wymienionych powyżej. W szczególności nie występują w nim spacje.

Inaczej, niż na wykładzie lub ćwiczeniach, nie używamy symbolu ε na oznaczenie słowa pustego. Słowo puste jest reprezentowane przez pusty ciąg znaków.

Przyjmujemy, że nazwy symboli pomocniczych są dużymi literami, a nazwy symboli końcowych to małe litery.

Nie wymagamy, by dla każdego symbolu pomocniczego była przynajmniej jedna produkcja.

Polecenie

Napisz program, który sprawdzi, czy na wejściu znajduje się wiersz tekstu z poprawnym zapisem gramatyki bezkontekstowej. Jeśli tak jest, program ma wypisać komunikat:

Poprawne dane

w przeciwnym przypadku należy wypisać:

Bledne dane

Przykłady danych poprawnych:

<{S},{a,b},{S->aSa|bSb|},S>
<{A},{},{A->},A>
<{S},{x,y},{S->xSy,S->,S->},S>
<{A,B,C},{x,y,z},{A->|A,B->xy|CCC},B>
<{A,B,C},{},{},A>

Przykłady danych błędnych:

{S},{a,b},{S->aSa|bSb|},S>
<{A},{},{A->B},A>
<{S},{x,y},{S->xSy,S->,S->,},S>
<{},{x,y,z},{A->|A,B->xy|CCC},B>
<{B,C},{},{},A>

Wskazówki

Dostępna we Free Pascalu operacja halt powoduje przerwanie programu.
Funkcja eoln() sprawdza, czy na wejściu znajduje się aktualnie koniec wiersza.
Wolno skorzystać z typu String. Nie jest on jednak do rozwiązania zadania potrzebny.

Rok 2008/2009, zadanie 1 - rozwiązanie

program wp08zad1;
 
var aktualny : Char;
    jestNieterminalem : array ['A' .. 'Z'] of Boolean;
    jestTerminalem : array ['a' .. 'z'] of Boolean;
 
procedure sprawdz(warunek : Boolean);
begin
    if not warunek then begin
        writeln('Bledne dane');
        halt
    end
end;
 
function nastepny : Char;
begin
    read(aktualny);
    nastepny := aktualny
end;
 
begin
    for aktualny := 'A' to 'Z' do
        jestNieterminalem[aktualny] := false;
    for aktualny := 'a' to 'z' do
        jestTerminalem[aktualny] := false;
    sprawdz(nastepny = '<');
    sprawdz(nastepny = '{');
    repeat
        sprawdz(nastepny in ['A'..'Z']);
        jestNieterminalem[aktualny] := true
    until nastepny <> ',';
    sprawdz(aktualny = '}');
    sprawdz(nastepny = ',');
    sprawdz(nastepny = '{');
    read(aktualny);
    while aktualny <> '}' do begin
        sprawdz(aktualny in ['a' .. 'z']);
        jestTerminalem[aktualny] := true;
        if nastepny = ',' then
            sprawdz(nastepny <> '}')
    end;
    sprawdz(nastepny = ',');
    sprawdz(nastepny = '{');
    read(aktualny);
    while aktualny <> '}' do begin
        sprawdz(aktualny in ['A' .. 'Z']);
        sprawdz(jestNieterminalem[aktualny]);
        sprawdz(nastepny = '-');
        sprawdz(nastepny = '>');
        while nastepny in ['A' .. 'Z', 'a' .. 'z', '|'] do
            if aktualny in ['A' .. 'Z'] then
                sprawdz(jestNieterminalem[aktualny])
            else if aktualny in ['a' .. 'z'] then
                sprawdz(jestTerminalem[aktualny]);
        if aktualny = ',' then
            sprawdz(nastepny <> '}')
    end;
    sprawdz(nastepny = ',');
    sprawdz(nastepny in ['A' .. 'Z']);
    sprawdz(jestNieterminalem[aktualny]);
    sprawdz(nastepny = '>');
    sprawdz(eoln);
    writeln('Poprawne dane')
end.

Rok 2007/2008, zadanie 1

Polecenie

Napisz program, który będzie symulował zachowanie obiektów na planszy o rozmiarze 40 na 20.

Obiekty dzielimy na:

martwe: nie poruszają się
żywe: w kolejnych krokach symulacji poruszają się "po przekątnych"

Postać danych

Na wejściu programu znajduje się 21 wierszy tekstu. W pierwszym wierszu jest nieujemna liczba całkowita określająca, ile kolejnych stanów planszy program powinien wypisać. Kolejnych 20 wierszy, z których każdy ma 40 znaków, zawiera opis stanu początkowego symulacji.

Wśród tych znaków:

spacja oznacza, że to miejsce jest puste
znaki '-', '+' i '|' reprezentują obiekty martwe
znaki '0', '1', '2' i '3' reprezentują obiekty żywe. Cyfra '0' oznacza obiekt, który w chwili rozpoczęcia symulacji porusza się w kierunku "prawo-góra", '1' - "prawo-dół", '2' - "lewo-dół", '3' - "lewo-góra".

Wolno założyć, że dane są poprawne.

Postać wyniku

Program ma wypisać na wyjście określoną liczbę stanów planszy z kolejnych kroków symulacji, zaczynając od stanu z chwili rozpoczęcia symulacji. Każdy zapis stanu planszy powinien się składać z 20 wierszy, po 40 znaków każdy. Wśród tych znaków spacja, '-', '+' i '|' będą miały znaczenie takie, jak na wejściu. Pozycje, jaką w danej chwili ma obiekt żywy, program powinien oznaczyć wypisując gwiadkę ('*').

Program ma wykonać określoną liczbę kroków symulacji. W każdym kroku należy wykonać ruch każdym ze znajdujących się na planszy obiektów żywych.

Symulator zna pozycję każdego obiektu żywego, oraz kierunek, w jakim obiekt się porusza. Wykonując ruch sprawdza, co znajduje się na polu sąsiednim do aktualnie zajmowanego przez obiekt, w kierunku, w jakim
ten obiekt się porusza. Jeśli nie ma tam obiektu martwego, obiekt żywy przenosi się na to pole. Jeśli na polu docelowym jest obiekt martwy, obiekt żywy nie zmienia aktualnie zajmowanej pozycji, zmienia tylko kierunek poruszania się wg następujących reguł:

obiekt martwy oznaczony '-' zmienia składowa kierunku obiektu żywego z "w dół" na "w górę" i na odwrót. Np. obiekt poruszający się w "lewo-górę" zmieni kierunek na "lewo-dół".
obiekt martwy oznaczony '|' zmienia składową kierunku obiektu żywego z "w lewo" na "w prawo" i na odwrót. Np. obiekt poruszający się w "prawo-dół" zmieni kierunek na
"lewo-dół".
obiekt martwy oznaczony '+' zmienia obie składowe kierunku obiektu żywego na przeciwne. Np. obiekt poruszający się w "lewo-górę" zmieni kierunek na "prawo-dół".

Jeśli obiekt żywy wykona ruch, po którym znajdzie się poza planszą, jest eliminowany z dalszej symulacji.

Uwaga: Podczas symulacji może się zdarzyć, że na tym samym polu jednocześnie znajdzie się kilka obiektów żywych.

Przykład działania programu

Dla danych:

10
+-------------     --------------------+
|                       2              |
|                                      |
|   |   2     --------+                |
|   |                 |                |
|   |         0       |             3  |
|   |                 |                |
|   |                 |  3             |
|   |                 |                |
|   |                                  |
| 1 |                                  |
|   |                                   
|   |         2                         
|   |                                  |
|   |         -----------------        |
|                                  0   |
|                         3            |
|               0                      |
|                                      |
+--------------------------------------+

program powinien wypisać:

+-------------     --------------------+
|                       *              |
|                                      |
|   |   *     --------+                |
|   |                 |                |
|   |         *       |             *  |
|   |                 |                |
|   |                 |  *             |
|   |                 |                |
|   |                                  |
| * |                                  |
|   |                                   
|   |         *                         
|   |                                  |
|   |         -----------------        |
|                                  *   |
|                         *            |
|               *                      |
|                                      |
+--------------------------------------+
+-------------     --------------------+
|                                      |
|                      *               |
|   |         --------+                |
|   |  *       *      |            *   |
|   |                 |                |
|   |                 | *              |
|   |                 |                |
|   |                 |                |
|   |                                  |
|   |                                  |
|  *|                                   
|   |                                   
|   |        *                         |
|   |         -----------------     *  |
|                        *             |
|                *                     |
|                                      |
|                                      |
+--------------------------------------+
+-------------     --------------------+
|                                      |
|                      *               |
|   |         --------+           *    |
|   |          *      |                |
|   | *               |*               |
|   |                 |                |
|   |                 |                |
|   |                 |                |
|   |                                  |
|   |                                  |
|  *|                                   
|   |                                   
|   |                                * |
|   |       * -----------------        |
|                 *      *             |
|                                      |
|                                      |
|                                      |
+--------------------------------------+
+-------------     --------------------+
|                       *              |
|                                *     |
|   |         --------+                |
|   |                 |                |
|   |           *     |*               |
|   |*                |                |
|   |                 |                |
|   |                 |                |
|   |                                  |
|   |                                  |
|   |                                   
| * |                                 * 
|   |                                  |
|   |         -----------------        |
|          *      *                    |
|                       *              |
|                                      |
|                                      |
+--------------------------------------+
+-------------     --------------------+
|                       *       *      |
|                                      |
|   |         --------+                |
|   |                 | *              |
|   |                 |                |
|   |*           *    |                |
|   |                 |                |
|   |                 |                |
|   |                                  |
|   |                                  |
|   |                                  *
|   |                                   
|*  |                                  |
|   |         -----------------        |
|                                      |
|         *        *                   |
|                      *               |
|                                      |
+--------------------------------------+
+-------------     --------------------+
|                               *      |
|                        *             |
|   |         --------+  *             |
|   |                 |                |
|   |                 |                |
|   |                 |                |
|   | *           *   |                |
|   |                 |                |
|   |                                  |
|   |                                  |
|   |                                   
|   |                                   
|*  |                                  |
|   |         -----------------        |
|                                      |
|                                      |
|        *          *                  |
|                     *                |
+--------------------------------------+
+-------------     --------------------+
|                                      |
|                         *    *       |
|   |         --------+   *            |
|   |                 |                |
|   |                 |                |
|   |                 |                |
|   |                 |                |
|   |  *           *  |                |
|   |                                  |
|   |                                  |
|   |                                   
|   |                                   
|   |                                  |
| * |         -----------------        |
|                                      |
|                                      |
|                                      |
|       *            **                |
+--------------------------------------+
+-------------     --------------------+
|                          *           |
|                                      |
|   |         --------+       *        |
|   |                 |    *           |
|   |                 |                |
|   |                 |                |
|   |                 |                |
|   |                 |                |
|   |   *           *                  |
|   |                                  |
|   |                                   
|   |                                   
|   |                                  |
|   |         -----------------        |
|  *                                   |
|                                      |
|                    *                 |
|       *            *                 |
+--------------------------------------+
+-------------     --------------------+
|                          *           |
|                                      |
|   |         --------+                |
|   |                 |      *         |
|   |                 |     *          |
|   |                 |                |
|   |                 |                |
|   |                 |                |
|   |                                  |
|   |    *           *                 |
|   |                                   
|   |                                   
|   |                                  |
|   |         -----------------        |
|                                      |
|   *               *                  |
|      *              *                |
|                                      |
+--------------------------------------+
+-------------     --------------------+
|                                      |
|                           *          |
|   |         --------+                |
|   |                 |                |
|   |                 |     *          |
|   |                 |      *         |
|   |                 |                |
|   |                 |                |
|   |                                  |
|   |                                  |
|   |     *           *                 
|   |                                   
|   |                                  |
|   |         -----------------        |
|                  *                   |
|     *                *               |
|    *                                 |
|                                      |
+--------------------------------------+

Rok 2007/2008, zadanie 1 - rozwiązanie

program wp07zad1;
 
const
    MAX_X = 40;
    MAX_Y = 20;
 
var swiat : array [1 .. MAX_X, 1 .. MAX_Y] of Char;
    nowex, nowey, liczbaGeneracji, i, j, ile : Integer;
    wspx, wspy, dx, dy : array [1..MAX_X * MAX_Y] of Integer;
 
begin
    ile := 0;
    readln(liczbaGeneracji);
    for j := 1 to MAX_Y do begin
        for i := 1 to MAX_X do begin
            read(swiat[i, j]);
            if ('0' <= swiat[i, j]) and (swiat[i, j] <= '3') then begin
                ile := ile + 1;
                wspx[ile] := i;
                wspy[ile] := j;
                case swiat[i, j] of
                    '0' : begin
                        dx[ile] := 1;
                        dy[ile] := -1
                    end;
                    '1' : begin
                        dx[ile] := 1;
                        dy[ile] := 1
                    end;
                    '2' : begin
                        dx[ile] := -1;
                        dy[ile] := 1
                    end;
                    '3' : begin
                        dx[ile] := -1;
                        dy[ile] := -1
                    end
                end;
                swiat[i, j] := '*'
            end
        end;
        readln
    end;
    for liczbaGeneracji := liczbaGeneracji downto 1 do begin
        for j := 1 to MAX_Y do begin
            for i := 1 to MAX_X do begin
                write(swiat[i, j]);
                if swiat[i, j] = '*' then
                    swiat[i, j] := ' '
            end;
            writeln
        end;
        i:=1;
        while i <= ile do begin
            nowex := wspx[i] + dx[i];
            nowey := wspy[i] + dy[i];
            if (nowex < 1) or (nowex > MAX_X) or (nowey < 1) or (nowey > MAX_Y) then begin
                wspx[i] := wspx[ile];
                wspy[i] := wspy[ile];
                dx[i] := dx[ile];
                dy[i] := dy[ile];
                ile := ile - 1
            end else begin
                case swiat[nowex, nowey] of
                    '+': begin
                        dx[i] := -dx[i];
                        dy[i] := -dy[i]
                    end;
                    '-':
                        dy[i] := -dy[i];
                    '|':
                        dx[i] := -dx[i];
                    ' ', '*': begin
                        wspx[i] := nowex;
                        wspy[i] := nowey
                    end
                end;
                swiat[wspx[i], wspy[i]] := '*';
                i := i + 1
            end
        end
    end
end.

Załącznik	Wielkość
wp10zad1.pas	1.98 KB
wp09zad1.pas	2.52 KB
wp08zad1.pas	1.76 KB
wp07zad1.pas	2.48 KB

Informatyka MIMUW