Laboratorium 12: Omówienie zadania zaliczeniowego 4

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

Rok 2010/2011, zadanie 4

Wprowadzenie

Lilistą nazwiemy listę, której elementami są lilisty. Rozmiarem lilisty jest suma jej długości i rozmiarów jej elementów. Tekstową reprezentacją lilisty jest sklejenie reprezentacji wszystkich jej elementów, po ujęciu każdego z nich w nawiasy okrągłe.

Wzorzec lilisty jest słowem języka o gramatyce:

Wzorzec -> CiągElementów
CiągElementów -> &#949; | Element CiągElementów
Element -> Zmienna | Lista
Lista -> ( CiągElementów )
Zmienna -> a | ... | z

Wzorzec opisuje, być może nieskończony, zbiór lilist mających podobną strukturę. Oznaczone małymi literami zmienne reprezentują dowolną lilistę. Jeśli zmienna występuje wielokrotnie, w miejscu każdego jej wystąpienia musi być ta sama lilista.

W zbiorze lilist opisanych zadanym wzorcem jest lilista najmniejsza (o najmniejszym rozmiarze). Znajdziemy ją, zastępując wszystkie zmienne lilistami pustymi.

Można udowodnić, że dla każdej pary wzorców opisujących zbiory lilist mające niepuste przecięcie istnieje wzorzec, który to przecięcie opisuje. Proces jego poszukiwania nazywamy uzgadnianiem wzorców (używa sie też terminu "unifikacja"). Próba uzgodnienia kończy się porażką jeśli zbiory te mają puste przecięcie.

Jedną z metod uzgadniania jest algorytm Robinsona. Dopóki oba wzorce nie są identyczne znajduje on parę różnych elementów E1 i E2 występujących w obu wzorcach na odpowiadających sobie pozycjach a następnie:

jeśli E1 i E2 są listami różnej długości kończy pracę - wzorce nie są uzgadnialne
jeśli E1 i E2 to listy równej długości, próbuje uzgodnić wszystkie pary elementów wystepujących w obu listach na odpowiadających sobie pozycjach
jeśli E1 jest zmienną a E2 nie i jeśli E1 występuje w E2 kończy pracę - wzorce nie są uzgadnialne
jeśli E2 jest zmienną a E1 nie i jeśli E2 występuje w E1 kończy pracę - wzorce nie są uzgadnialne
jeśli E1 jest zmienną i nie zachodzi przypadek (3) podstawia, w obu wzorcach, E2 w miejsce wszystkich wystąpień E1
jeśli E2 jest zmienną i nie zachodzi przypadek (4) podstawia, w obu wzorcach, E1 w miejsce wszystkich wystąpień E2

Obserwacje

Lilistę możemy reprezentować np. za pomocą wartości typu zdefiniowanego następująco:

type
    WezelLilisty = record
        w : Lilista;
        nast : Lilista
    end;
    Lilista = ^WezelLilisty;

Poprawna lilista jest strukturą acykliczną, czyli nie istnieje ścieżka złożona ze wskaźników pamiętanych w polach w i nast, która łączy węzeł z sobą samym.

Polecenie

Napisz program który, mając na wejściu zapis ciągu par wzorców, dla każdej z nich podejmie próbę uzgodnienia i wskaże najmniejszą lilistę pasującą do obu wzorców lub stwierdzi, że wzorce nie są uzgadnialne.

Przyjmij, że wystąpienia tej samej zmiennej w obu wzorcach z pary oznaczają tą samą wartość a wystąpienia w różnych parach mogą reprezentować różne wartości.

Format danych

Na wejściu programu znajdzie się 2 * K wierszy (wartość K >= 0 nie jest nam znana), z których każdy będzie zawierał jeden wzorzec.

Format wyniku

Program powinien wypisać K wierszy. W i-tym wierszu, dla każdego i od 1 do K, ma być informacja o wyniku próby uzgodnienia pary wzorców występujących na wejściu w wierszach 2 * i - 1 oraz 2 * i. Jeśli wzorce są uzgadnialne, należy wypisać najmniejszą lilistę ze zbioru opisanego wzorcem będącym wynikiem uzgodnienia, w przeciwnym przypadku wypisujemy słowo nie.

Przykłady

Dla danych:

()b(a)c
aacd

program powinien wypisać:

()()(())(())
Dla danych:

xz
((v))x
()
x
x()
((v))x

program powinien wypisać:

((()))((()))
()
nie
Dla danych:

a
(()((a)))
bac
(())ab
abc
de

program powinien wypisać:

nie
(())()(())
nie

Uwagi

Wolno założyć poprawność danych.
Długość tekstowej reprezentacji wzorca lilisty może przekroczyć maksymalną długość wartości typu String.
Analizę zadania warto zacząć od przykładów, w których zmienne występują wyłącznie na najwyższym poziomie struktury, czyli poza nawiasami.
Do rozwiązania zadania może się przydać bezagrumentowa funkcja eoln(), która odpowiada na pytanie, czy w danej chwili na wejściu jest koniec wiersza oraz bezargumentowa funkcja eof() odpowiadająca na pytanie, czy dane na wejściu już się skończyły. Obie funkcje są dostępne w standardzie Pascala.
W tym zadaniu złożoność zrealizowanego algorytmu nie będzie podlegała ocenie. Choć istnieją znacznie bardziej efektywne metody, za rozwiązanie o wykładniczym koszcie pamięciowym i czasowym można uzyskać ocenę maksymalną.
Jest to zadanie "na wskaźniki" i jednocześnie wprowadzenie do tematu drzew. Choć treść mówi o listach, posługujemy się tu tak naprawdę drzewiastą reprezentacją tzw. termów zbudowanych za pomocą jednego dwuargumentowego symbolu funkcyjnego i jednej stałej.

Rok 2010/2011, zadanie 4 - rozwiązanie

{**
 * Przykladowe rozwiazanie zadania dzialajace w czasie prawie liniowym.
 *}
program wp10zad4;
 
const
    PIERWSZA = 'a';
    OSTATNIA = 'z';
 
type
    Kolor = (BIALY, SZARY, CZARNY);
    Lilista = ^WezelLilisty;
    WezelLilisty = record
        glowa, ogon, reprezentant : Lilista;
        ranga : Integer;
        znacznik : Kolor        
    end;
 
var l1, l2, mojNil : Lilista;
    zmienne : array [PIERWSZA .. OSTATNIA] of Lilista;
    c : Char;
 
function nowy(glowa, ogon : Lilista) : Lilista;
var wynik : Lilista;
begin
    new(wynik);
    wynik^.glowa := glowa;
    wynik^.ogon := ogon;
    wynik^.reprezentant := wynik;
    wynik^.ranga := 0;
    wynik^.znacznik := BIALY;
    nowy := wynik
end;
 
function jestZmienna(l : Lilista) : Boolean;
begin
    jestZmienna := ((l^.glowa = nil) and (l^.ogon = mojNil))
end;
 
function jestNiepusta(l : Lilista) : Boolean;
begin
    jestNiepusta := (l^.glowa <> nil)
end;
 
procedure znajdz(var l : Lilista);
begin
    if l <> l^.reprezentant then begin
        znajdz(l^.reprezentant);
        l := l^.reprezentant
    end
end;
 
procedure polacz(l1, l2 : Lilista);
begin
    if l1^.ranga < l2^.ranga then
        l1^.reprezentant := l2
    else begin
        l2^.reprezentant := l1;
        if l1^.ranga = l2^.ranga then
            inc(l1^.ranga)
    end
end;
 
function wczytaj : Lilista;
var w : Lilista;
    c : Char;
begin
    if eoln then
        wczytaj := mojNil
    else begin
        read(c);
        if c = ')' then
            wczytaj := mojNil
        else begin
            if c in [PIERWSZA .. OSTATNIA] then begin
                if zmienne[c] = nil then
                    zmienne[c] := nowy(nil, mojNil);
                w := zmienne[c]
            end else begin
                assert(c = '(');
                w := wczytaj()
            end;
            wczytaj := nowy(w, wczytaj())
        end
    end
end;
 
procedure wypisz(l : Lilista);
begin
    znajdz(l);
    if jestNiepusta(l) then begin
        write('(');
        wypisz(l^.glowa);
        write(')');
        wypisz(l^.ogon)
    end
end;
 
procedure usun(l : Lilista);
begin
    if jestNiepusta(l) then begin
        usun(l^.glowa);
        usun(l^.ogon);
        dispose(l)
    end
end;
 
function jestCykl(l : Lilista) : Boolean;
begin
    znajdz(l);
    if jestNiepusta(l) and (l^.znacznik = BIALY) then begin
        l^.znacznik := SZARY;
        if jestCykl(l^.glowa) then
            jestCykl := true
        else
            jestCykl := jestCykl(l^.ogon);
        l^.znacznik := CZARNY
   end else
       jestCykl := (l^.znacznik = SZARY)
end;
 
function prawieUzgadnialne(l1, l2 : Lilista) : Boolean;
begin
    znajdz(l1);
    znajdz(l2);
    if l1 = l2 then
        prawieUzgadnialne := true
    else if jestZmienna(l1) or jestZmienna(l2) then begin
        prawieUzgadnialne := true;
        if jestZmienna(l1) then
            l1^.reprezentant := l2
        else
            l2^.reprezentant := l1
    end else if jestNiepusta(l1) and jestNiepusta(l2) then begin
        if not prawieUzgadnialne(l1^.glowa, l2^.glowa) then
            prawieUzgadnialne := false
        else
            prawieUzgadnialne := prawieUzgadnialne(l1^.ogon, l2^.ogon);
        polacz(l1, l2)
    end else
        prawieUzgadnialne := false
end;
 
begin
    while not eof do begin
        mojNil := nowy(nil, nil);
        for c := PIERWSZA to OSTATNIA do
            zmienne[c] := nil;
        l1 := wczytaj;
        readln;
        l2 := wczytaj;
        readln;
        if prawieUzgadnialne(l1, l2) then
            if not jestCykl(l1) then begin
                wypisz(l1);
                writeln
            end else
                writeln('nie')
        else
            writeln('nie');
        usun(l1);
        usun(l2);
        for c := PIERWSZA to OSTATNIA do
            if zmienne[c] <> nil then
                dispose(zmienne[c]);
        dispose(mojNil)
    end
end.

Rok 2009/2010, zadanie 4

Wprowadzenie

W treści zadania będziemy się posługiwali następującymi terminami:

obiekt: dana znajdująca się w pamięci dynamicznej programu (w Pascalu to dane utworzone za pomocą operacji new())
zmienna statyczna: zmienna zadeklarowana w programie (w Pascalu to zmienne globalne, zmienne lokalne procedur i funkcji)
zmienna dynamiczna: zmienna obiektu (w Pascalu to np. pola rekordu utworzonego operacją new())
obiekt żywy: obiekt, do którego program ma jeszcze dostęp
obiekt martwy: obiekt, który nie jest żywy (w Pascalu pozostawienie w pamięci obiektu martwego jest błędem)

Realizacje niektórych języków programowania mają wbudowany algorytm automatycznego zarządzania pamięcią, tzw. "odśmiecacz", który wykrywa obiekty martwe i zwalnia pamięć przez nie zajmowaną. Odśmiecacz jest uruchamiany np. wtedy, gdy obiekty wypełnią całą pamięć dynamiczną programu.

Oto przykład takiego algorytmu:

umieść w puli obiektów żywych te, które są wartościami zmiennych statycznych
dopóki w puli obiektów żywych jest taki, który na swojej zmiennej ma obiekt nie będący w puli żywych, przenieś wartość tej zmiennej do puli żywych
pamięć zajmowana przez obiekty, które nie znalazły się w puli żywych, uznaj za wolną

Polecenie

Napisz program, który wczyta z wejścia zapis ciągu operacji tworzenia obiektu oraz przypisania i wykona je.

Program będzie miał jeden argument - nieujemną liczbę całkowitą określającą maksymalną liczbę obiektów, które na raz mogą pozostawać w pamięci dynamicznej. Gdy liczba obiektów w pamięci dynamicznej będzie maksymalną, a kolejną operacją okaże się utworzenie obiektu, należy uruchomić algorytm odśmiecania.

Operacje wykonywane przez program będą korzystały z 26 zmiennych statycznych, których nazwy są małymi literami, oraz obiektów, z których każdy ma dwie zmienne dynamiczne o nazwach ob1 i ob2. Wartością zmiennej może być obiekt, lub brak obiektu (nil). Początkową wartością każdej zmiennej jest brak obiektu.

Znaczenie operacji jest takie, jak w Pascalu, a ich postać określa gramatyka:

Operacja -> new(Zmienna) | Zmienna:=Zmienna
Zmienna -> ZmiennaStatyczna | ZmiennaDynamiczna
ZmiennaStatyczna -> a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
ZmiennaDynamiczna -> ZmiennaStatyczna^.ob1 | ZmiennaStatyczna^.ob2

Program, po każdym odśmiecaniu, powinien wypisać wiersz postaci:

Operacja ...: odsmiecono ...

gdzie po słowie Operacja jest numer wykonywanej operacji liczony od 1, a po słowie odsmiecono liczba wykrytych martwych obiektów.

Jeśli zdarzy się, że utworzenie nowego obiektu nie będzie możliwe, bo pamięć dynamiczna będzie w całości wypełniona, a odśmiecacz nie znajdzie żadnego obiektu martwego, program powinien wypisać:

Operacja ...: brak miejsca w pamieci

i zakończyć działanie.

Dodatkowo, próba sięgnięcia do zmiennej dynamicznej obiektu, który nie istnieje, powinna spowodować zakończenie programu z komunikatem:

Operacja ...: brak obiektu

Przykłady

Program wywołany z argumentem 4 dla danych:

new(a)
new(b)
new(c)
new(d)
new(e)

powinien wypisać:

Operacja 5: odsmiecono 0
Operacja 5: brak miejsca w pamieci

dla danych:

new(a^.ob1)

powinien wypisać:

Operacja 1: brak obiektu

dla danych:

new(a)
a^.ob1:=a
a^.ob2:=a^.ob1
new(b)
new(b^.ob2)
c:=b^.ob2
c^.ob1:=b
new(c)
d:=c
a:=z
b:=z
c:=z
new(e)
new(e^.ob1)
f:=e^.ob1
new(f^.ob2)
d:=z
new(e)
f^.ob2:=e
new(e^.ob1)

powinien wypisać:

Operacja 13: odsmiecono 3
Operacja 18: odsmiecono 1
Operacja 20: odsmiecono 2

Uwagi i wskazówki

Można założyć, że dane na wejściu programu są poprawne składniowo, a zapis każdej operacji zajmie jeden wiersz i nie wystąpią w nim spacje.
Wartość argumentu wywołania programu można obliczyć procedurą val().
Rozmiar pamięci dynamicznej jest określony w chwili wywołania programu, więc pamięć na obiekty trzeba rezerwować za pomocą Pascalowej operacji new().
Po zakończeniu odśmiecania, pamięci po obiektach martwych nie trzeba zwalniać. Obiekty takie można gromadzić i wykorzystywać ponownie przy wykonaniu operacji utworzenia obiektu. To pozwoli uniknąć wielokrotnego powtarzania operacji dispose() i new().
Warto zwrócić uwagę na pewną subtelność. Obiekt, który jest wartością zmiennej "e", nie jest odśmiecany, gdy odśmiecacz uruchamiamy podczas wykonania operacji new(e). Jest tak dlatego, że w chwili tworzenia nowego obiektu poprzednia wartość zmiennej nie jest jeszcze martwa.
Treść zadania nie wskazuje, jakiej struktury danych należy użyć. Jeśli nie zależy nam na efektywności, możemy posłużyć się nawet listą prostą.
Efektywność rozwiązania może mieć wpływ na jego ocenę.

Rok 2009/2010, zadanie 4 - rozwiązanie

(*
Rozwiazanie korzysta z cyklicznej listy dwukierunkowej z atrapą.
*)
program wp09zad4;
 
type
    Obiekt = ^Wezel;
    Wezel = record
        znacznik : boolean;
        ob : array ['1' .. '2'] of Obiekt;
        nast, poprz : Obiekt
    end;
    Pula = Obiekt;
 
var zmienna : array ['a' .. 'z'] of Obiekt;
    wolne, przydzielone : Pula;
    nr, rozmiarHeapu, liczbaObiektow : Integer;
    oznaczony : Boolean;
 
procedure wyczysc(var p : Pula);
begin
    new(p);
    p^.nast := p;
    p^.poprz := p
end;
 
function jestPusta(p : Pula) : Boolean;
begin
    jestPusta := (p^.nast = p)
end;
 
procedure wyjmij(var p : Pula; co : Obiekt);
begin
    co^.poprz^.nast := co^.nast;
    co^.nast^.poprz := co^.poprz
end;
 
procedure dodajNaKoniec(var p : Pula; co : Obiekt);
begin
    co^.nast := p;
    co^.poprz := p^.poprz;
    p^.poprz^.nast := co;
    p^.poprz := co
end;
 
procedure usun(p : Pula);
begin
    p^.poprz^.nast := nil;
    while p^.nast <> nil do begin
        p := p^.nast;
        dispose(p^.poprz)
    end;
    dispose(p)
end;
 
procedure naPoczatek(p : Pula; var co : Obiekt);
begin
    co := p^.nast
end;
 
procedure naNastepny(p : Pula; var co : Obiekt);
begin
    co := co^.nast
end;
 
function naKoncu(p : Pula; co : Obiekt) : Boolean;
begin
    naKoncu := p = co
end;
 
procedure ustawZnacznik(co : Obiekt);
begin
    co^.znacznik := oznaczony
end;
 
function jestOznaczony(co : Obiekt) : Boolean;
begin
    jestOznaczony := (co^.znacznik = oznaczony)
end;
 
procedure kasujZnaczniki(var p : Pula);
begin
    oznaczony := not oznaczony
end;
 
procedure usunZnacznik(co : Obiekt);
begin
    co^.znacznik := not oznaczony
end;
 
procedure inicjalizuj;
var c : Char;
    kodBledu : Word;
begin
    oznaczony := false;
    for c := 'a' to 'z' do
        zmienna[c] := nil;
    wyczysc(wolne);
    wyczysc(przydzielone);
    if paramCount <> 1 then begin
        writeln('Program oczekuje jednego argumentu');
        halt
    end;
    val(paramStr(1), rozmiarHeapu, kodBledu);
    if kodBledu <> 0 then begin
        writeln('Niepoprawny argument "', paramStr(1), '"');
        halt
    end;
    liczbaObiektow := 0
end;
 
procedure posprzataj;
begin
    usun(wolne);
    usun(przydzielone)
end;
 
procedure bladWykonania(komunikat : String);
begin
    writeln('Operacja ', nr, ': ', komunikat);
    posprzataj;
    halt
end;
 
procedure odsmiec;
var c : Char;
    aktualny : Obiekt;
    zywe : Pula;
    liczbaZywych : Integer;
 
    procedure obsluz(co : Obiekt);
    begin
        if co <> nil then
            if not jestOznaczony(co) then begin
                wyjmij(przydzielone, co);
                dodajNaKoniec(zywe, co);
                ustawZnacznik(co);
                liczbaZywych := liczbaZywych + 1
            end
    end;
 
begin
    zywe := wolne;
    liczbaZywych := 0;
    for c := 'a' to 'z' do
        obsluz(zmienna[c]);
    naPoczatek(zywe, aktualny);
    while not naKoncu(zywe, aktualny) do begin
        obsluz(aktualny^.ob['1']);
        obsluz(aktualny^.ob['2']);
        naNastepny(zywe, aktualny)
    end;
    wolne := przydzielone;
    przydzielone := zywe;
    kasujZnaczniki(zywe);
    writeln('Operacja ', nr, ': odsmiecono ', rozmiarHeapu - liczbaZywych)
end;
 
function przydzielObiekt : Obiekt;
var wynik : Obiekt;
begin
    if liczbaObiektow < rozmiarHeapu then begin
        new(wynik);
        liczbaObiektow := liczbaObiektow + 1
    end else begin
        if jestPusta(wolne) then
            odsmiec;
        if jestPusta(wolne) then
            bladWykonania('brak miejsca w pamieci');
        naPoczatek(wolne, wynik);
        wyjmij(wolne, wynik)
    end;
    usunZnacznik(wynik);
    wynik^.ob['1'] := nil;
    wynik^.ob['2'] := nil;
    dodajNaKoniec(przydzielone, wynik);
    przydzielObiekt := wynik
end;
 
procedure wykonaj;
var s : String;
    i : Integer;
begin
    nr := 0;
    readln(s);
    while s <> '' do begin
        nr := nr + 1;
        for i := 2 to length(s) do
            if s[i] = '^' then
                if zmienna[s[i - 1]] = nil then
                    bladWykonania('brak obiektu');
        case length(s) of
            6  : {new(?)}
                zmienna[s[5]] := przydzielObiekt;
            11 : {new(?^.ob?)}
                zmienna[s[5]]^.ob[s[10]] := przydzielObiekt;
            4  : {?:=?}
                zmienna[s[1]] := zmienna[s[4]];
            9 : {?^.ob?:=? lub ?:=?^.ob?}
                if s[2] = ':' then
                    zmienna[s[1]] := zmienna[s[4]]^.ob[s[9]]
                else
                    zmienna[s[1]]^.ob[s[6]] := zmienna[s[9]];
            14 : {?^.ob?:=?^.ob?}
                zmienna[s[1]]^.ob[s[6]] := zmienna[s[9]]^.ob[s[14]];
            else
                bladWykonania('niepoprawna skladnia')
        end;
        readln(s)
    end
end;
 
begin
    inicjalizuj;
    wykonaj;
    posprzataj
end.

Rok 2008/2009, zadanie 4

Wprowadzenie

Tematem zadania są drzewa i ich obiegi oraz składnia i semantyka języków programowania.

Program w języku np0 składa się z programu głównego oraz definicji bezparametrowych funkcji, których nazwy są dużymi literami.

Tekstowy zapis programu rozpoczyna się od treści programu głównego, po której następuje, być może pusty, ciąg par: nazwa funkcji oraz jej treść.

Treść programu głównego i treści funkcji są wyrażeniami zbudowanymi z operacji mających zero, jeden lub dwa argumenty. Każda operacja jest reprezentowana przez jeden znak. Wyrażenie jest więc drzewem binarnym znaków, w którym węzły operacji bezargumentowych to liście, operacje jednoargumentowe mają tylko jedno (lewe) poddrzewo niepuste a dwuargumentowe mają oba poddrzewa niepuste.

Tekstowy zapis wyrażenia będzie prefiksowy - najpierw podamy znak operacji w korzeniu, następnie lewe poddrzewo (o ile nie jest puste) i prawe poddrzewo (jeśli nie puste).

Wszystkie wartości, którymi posługujemy się w języku np0, są liczbami całkowitymi. Przechowujemy je w pamięci programu, która składa się z 26 zmiennych o nazwach, będących małymi literami i jednej tablicy
nieograniczonego rozmiaru.

Do elementów tablicy odwołujemy się za pomocą indeksu, który jest dowolną liczbą całkowitą (nie koniecznie nieujemną). Jeśli element tablicy o zadanym indeksie jeszcze nie istnieje, jest tworzony w chwili odwołania
się do niego.

Wartości początkowe wszystkich komórek pamięci, zarówno zmiennych jak i elementów tablicy, są równe 0.

Wykonanie programu w języku np0 oznacza obliczenie wyrażenia, które jest treścią programu głównego. Wartość będąca wynikiem tego obliczenia jest ignorowana.

Poniżej znajduje się spis operacji języka np0 pogrupowanych wg liczby argumentów.

Operacje bezargumentowe:

' ': wartość 32
'@': wartość 10
'0' .. '9': wartości od 0 do 9
'a' .. 'z': odwołanie do zmiennej o podanej nazwie. Może wystąpić w miejscu, w którym oczekujemy wartości, a także jako argument operacji wpisującej wartość do komórki pamięci (operacje '(', '{', '[', ']', ':')
'A' .. 'Z': wynik funkcji o podanej nazwie, czyli wartość wyrażenia będącego jej treścią. Jeśli funkcja o tej nazwie nie została zdefiniowana, jej wywołanie kończy pracę programu

Operacje jednoargumentowe:

'(': wczytuje z wejścia znak, wpisuje jego kod do komórki pamięci, będącej argumentem i zwraca go jako wynik. Jeśli na wejściu jest koniec danych, zamiast kodu znaku wpisuje i zwraca -1
'{': wczytuje z wejścia liczbę całkowitą, wpisuje jej wartość do komórki pamięci, będącej argumentem i zwraca ja jako wynik
')': wypisuje znak, którego kod jest wartością argumentu i zwraca ten kod jako wynik
'}': wypisuje liczbę, będącą wartością argumentu i zwraca ją jako wynik
'$': odwołanie do elementu tablicy o indeksie będącym wartością argumentu. Może wystąpić w miejscu, w którym oczekujemy wartości, a także jako argument operacji wpisującej wartość do komórki pamięci (operacje '(', '{', '[', ']', ':')
'[': zwraca wartość komórki pamięci reprezentowanej przez argument i zwiększa ją o 1 (zwraca wartość, jaką miała przed zwiększeniem)
']': zmniejsza o jeden wartość komórki pamięci reprezentowanej przez argument i zwraca ją jako wynik (zwraca wartość, jaką komórka uzyskała po zmniejszeniu)
'!': zwraca 1, jeśli wartością argumentu jest 0 lub 0, jeśli wartością argumentu nie jest 0

Operacje dwuargumentowe (jeśli liczymy oba argumenty, to robimy to w kolejności: najpierw lewy, później prawy):

'+': liczy sumę wartości lewego i prawego argumentu
'-': liczy różnicę wartości lewego i prawego argumentu
'*': liczy iloczyn wartości lewego i prawego argumentu
'/': liczy iloraz wartości lewego i prawego argumentu
'%': liczy resztę z dzielenia wartości lewego i prawego argumentu
'<': jeśli wartość lewego argumentu jest mniejsza od prawego, daje 1, wpp. 0
'>': jeśli wartość lewego argumentu jest większa od prawego, daje 1, wpp. 0
'=': jeśli wartość lewego argumentu jest równa wartości prawego, daje 1, wpp. 0
'#': zwraca wartość 10 * arg1 + arg2, gdzie arg1 to wartość lewego argumentu a arg2 to wartość prawego
':': przypisanie do komórki pamięci reprezentowanej przez lewy argument wartości prawego argumentu. Daje przypisywaną wartość.
';': daje wartość prawego argumentu (ale liczy także lewy)
',': daje wartość lewego argumentu (ale liczy także prawy)
'&': jeśli wartością lewego argumentu jest 0, daje ją, jeśli nie, liczy i daje wartość prawego argumentu
'|': jeśli wartością lewego argumentu nie jest 0, daje ją, jeśli jest 0, liczy i daje wartość prawego argumentu
'\': daje wartość lewego argumentu. Dodatkowo, jeśli było nią 0, liczy prawy argument, ale ignoruje jego wartość
'?': ma dwa warianty, w zależności od postaci prawego argumentu. Jeśli prawym argumentem jest ',', to liczy swój lewy argument i, jeśli jego wartość jest niezerowa, liczy i daje wartość lewego argumentu ',', a wpp. liczy i daje wartość prawego argumentu ','. Jeśli prawym argumentem nie jest ',', to daje wartość lewego argumentu. Dodatkowo, jeśli była niezerowa, liczy prawy argument, ale ignoruje jego wartość
'^': w pętli, dopóki wartość lewego argumentu jest niezerowa, liczy prawy argument (jak w pętli while). Daje wynik ostatniego obliczenia prawego argumentu, lub 0, jeśli nie był on liczony ani razu
'~': w pętli liczy lewy argument a następnie prawy, dopóki obliczenie prawego daje wartość 0 (jak w pętli repeat-until). Daje wynik ostatniego obliczenia lewego argumentu

Polecenie

Napisz interpreter języka np0, czyli program, który wykona program w języku np0 przekazany mu jako argument.

Przykłady

Program wywołany poleceniem:

./zad4 ');)+))+)-)#72373@'

powinien wypisać na wyjście:

HELLO

Program wywołany poleceniem:

./zad4 '~}*]ii!+i)@'

powinien wypisać na wyjście:

Program wywołany poleceniem:

./zad4 '^+1(c)c'

powinien skopiować tekst wejściowy na wyjście.

Program wywołany poleceniem:

./zad4 '~;:k9;^]k}%+wk2)@=[w7'

powinien wypisać na wyjście:

Program wywołany poleceniem:

./zad4 ';^{$p[p^p), }$]p'

powinien wczytać z wejścia ciąg liczb zakończony zerem i wypisać te liczby na wyjście w kolejności odwróconej.

Program wywołany poleceniem:

./zad4 ';;:f{x^]x:f*fx}f'

powinien wczytać z wejścia liczbę całkowitą i wypisać na wyjście jej silnię.

Program wywołany poleceniem:

./zad4 ';{x}FF?]x,*+1xF1'

powinien zrobić to, co program z poprzedniego przykładu.

Program wywołany poleceniem:

./zad4 ';}{x;)#61;:p2;^>xp?%xp,[p:x/x,}p)#42}x'

powinien wczytać z wejścia liczbę całkowitą i wypisać na wyjście jej rozkład na czynniki pierwsze.

Wskazówka

Do rozwiązania zadania przyda się instrukcja case.

Rok 2008/2009, zadanie 4 - rozwiązanie

program wp08zad4;
 
type DrzewoZnakow = ^WezelDrzewaZnakow;
     WezelDrzewaZnakow = record
         w : Char;
         lsyn, psyn : DrzewoZnakow
     end;
     DrzewoLiczb = ^WezelDrzewaLiczb;
     WezelDrzewaLiczb = record
         w : Integer;
         lsyn, psyn : DrzewoLiczb
     end;
 
var glowny : DrzewoZnakow;
    funkcja : array ['A'..'Z'] of DrzewoZnakow;
    zmienna : array ['a'..'z'] of Integer;
    nieujemne, ujemne : DrzewoLiczb;
    i : Integer;
    s : String;
    c : Char;
 
procedure test(b : Boolean; s : String);
begin
    if not b then begin
        writeln(s);
        halt
    end
end;
 
function szukaj(var p : DrzewoLiczb; adres : Integer) : DrzewoLiczb;
begin
    if p = nil then begin
        new(p);
        p^.w := 0;
        p^.lsyn := nil;
        p^.psyn := nil
    end;
    if adres = 0 then
        szukaj := p
    else if adres mod 2 = 0 then
        szukaj := szukaj(p^.lsyn, adres div 2)
    else
        szukaj := szukaj(p^.psyn, adres div 2)
end;
 
function komorka(adres : Integer) : DrzewoLiczb;
begin
    if adres >= 0 then
        komorka := szukaj(nieujemne, adres)
    else
        komorka := szukaj(ujemne, -adres)
end;
 
procedure wczytaj(var d : DrzewoZnakow);
begin
    test(i <= length(s), 'Nieoczekiwany koniec programu');
    new(d);
    d^.w := s[i];
    d^.lsyn := nil;
    d^.psyn := nil;
    i := i + 1;
    if not (d^.w in [' ', '@', 'a' .. 'z', 'A' .. 'Z', '0' .. '9']) then begin
        wczytaj(d^.lsyn);
        if not (d^.w in ['(', ')', '{', '}', '[', ']', '!', '$']) then
            wczytaj(d^.psyn)
    end;
    if d^.w in [':', '(', '{', '[', ']'] then
        test(d^.lsyn^.w in ['$', 'a' .. 'z'], 'Niepoprawna l-wartosc')
end;
 
function wartosc(d : DrzewoZnakow) : Integer; forward;
 
procedure przypisz(d : DrzewoZnakow; i : Integer);
var x : DrzewoLiczb;
begin
    if d^.w = '$' then begin
        x := komorka(wartosc(d^.lsyn));
        x^.w := i
    end else
        zmienna[d^.w] := i
end;
 
function wartosc(d : DrzewoZnakow) : Integer;
var arg, arg2 : Integer;
    c : Char;
    x : DrzewoLiczb;
begin
    if d = nil then
        halt
    else
        case d^.w of
            ' ':
                wartosc := 32;
            '@':
                wartosc := 10;
            '0'..'9':
                wartosc := ord(d^.w) - ord('0');
            'a'..'z':
                wartosc := zmienna[d^.w];
            'A'..'Z':
                wartosc := wartosc(funkcja[d^.w]);
            ':': begin
                arg := wartosc(d^.psyn);
                przypisz(d^.lsyn, arg);
                wartosc := arg
            end;
            '(': begin
                if eof then
                    arg := -1
                else begin
                    read(c);
                    arg := ord(c)
                end;
                przypisz(d^.lsyn, arg);
                wartosc := arg
            end;
            '{': begin
                read(arg);
                przypisz(d^.lsyn, arg);
                wartosc := arg
            end;
            '^': begin
                wartosc := 0;
                while wartosc(d^.lsyn) <> 0 do
                    wartosc := wartosc(d^.psyn)
            end;
            '~':
                repeat
                    wartosc := wartosc(d^.lsyn)
                until wartosc(d^.psyn) <> 0;
        else
            arg := wartosc(d^.lsyn);
            case d^.w of
                '!':
                    wartosc := 1 - ord(arg <> 0);
                ')': begin
                    write(chr(arg));
                    wartosc := arg
                end;
                '}': begin
                    write(arg);
                    wartosc := arg
                end;
                '$': begin
                    x := komorka(arg);
                    wartosc := x^.w
                end;
                '[': begin
                    przypisz(d^.lsyn, arg + 1);
                    wartosc := arg
                end;
                ']': begin
                    przypisz(d^.lsyn, arg - 1);
                    wartosc := arg - 1
                end;
                '&':
                    if arg = 0 then
                        wartosc := 0
                    else
                        wartosc := wartosc(d^.psyn);
                '|':
                    if arg <> 0 then
                        wartosc := arg
                    else
                        wartosc := wartosc(d^.psyn);
                '?':
                    if d^.psyn^.w = ',' then
                        if arg <> 0 then
                            wartosc := wartosc(d^.psyn^.lsyn)
                        else
                            wartosc := wartosc(d^.psyn^.psyn)
                    else begin
                        wartosc := arg;
                        if arg <> 0 then
                            arg := wartosc(d^.psyn)
                    end;
                '\': begin
                    wartosc:=arg;
                    if arg = 0 then
                        arg := wartosc(d^.psyn)
                end;
            else
                arg2 := wartosc(d^.psyn);
                case d^.w of
                    '+':
                        wartosc := arg + arg2;
                    '-':
                        wartosc := arg - arg2;
                    '*':
                        wartosc := arg * arg2;
                    '/':
                        wartosc := arg div arg2;
                    '%':
                        wartosc := arg mod arg2;
                    '<':
                        wartosc := ord(arg < arg2);
                    '>':
                        wartosc := ord(arg > arg2);
                    '=':
                        wartosc := ord(arg = arg2);
                    '#':
                        wartosc := 10 * arg + arg2;
                    ';':
                        wartosc := arg2;
                    ',':
                        wartosc := arg;
                else
                    test(false, 'Niepoprawne drzewo programu')
                end
            end
        end
end;
 
begin
    test(paramCount = 1, 'Program oczekuje jednego argumentu');
    s := paramStr(1);
    i := 1;
    for c := 'A' to 'Z' do
        funkcja[c] := nil;
    wczytaj(glowny);
    while i < length(s) do begin
        test(s[i] in ['A' .. 'Z'], 'Niepoprawna nazwa funkcji');
        i := i + 1;
        wczytaj(funkcja[s[i - 1]])
    end;
    for c := 'a' to 'z' do
        zmienna[c] := 0;
    nieujemne := nil;
    ujemne := nil;
    i := wartosc(glowny)
end.

Rok 2007/2008, zadanie 4

Polecenie

Napisz program grający w grę planszową o nazwie "Zadanie 4". Program wczyta z wejścia informacje o graczach i planszy. Będą tam kolejno:

imiona graczy - niepuste napisy, każdy w oddzielnym wierszu
jeden wiersz pusty
wiersz opisu planszy z ciągiem znaków określających rodzaje poszczególnych pól, zakończonym kropką

Imiona graczy nie będą długie, więc mogą być przechowywane na zmiennych typu String. Liczba graczy oraz rozmiar planszy mogą być dowolnie duże - program nie powinien ich w żaden sposób ograniczać.

Można założyć, że liczba pól na planszy jest niezerowa.

Podczas pracy program będzie symulował rzuty sześcienną kostką. Liczbę oczek, będącą wynikiem rzutu, obliczymy jako wartość wyrażenia 1 + random(6).

Program rozpocznie grę umieszczając wszystkich graczy przed pierwszym polem planszy. W dalszej części opisu miejsce to będziemy nazywali polem startowym. Następnie program będzie wykonywał za każdego gracza, zgodnie z kolejnością graczy zapisaną na wejściu, rzut kostką i ruch o określoną liczbę pól do przodu. Jeśli np. wynikiem rzutu kostką będzie 3, program powinien przesunąć aktualnego gracza o trzy pola do
przodu. Po wykonaniu ruchu za ostatniego gracza wracamy do pierwszego itd.

Po umieszczeniu gracza na polu docelowym należy postąpić odpowiednio do rodzaju tego pola. Oto opisy rodzajów pól planszy i odpowiadające im oznaczenia literowe:

c: "Uczestników gry reprezentujesz za pomocą listy cyklicznej, której węzły przechowują imię gracza i wskaźnik na pole, na którym gracz się znajduje; przesuwasz się o 5 pól do przodu."
d: "Planszę reprezentujesz za pomocą listy dwukierunkowej, której węzły przechowują numer pola, oznaczenie rodzaju oraz informację, który gracz na tym polu się znajduje; przesuwasz się o 10 pól do przodu."
e: "Zbudowałeś reprezentację planszy, pozwalającą na wykonanie ruchu gracza w czasie stałym, niezależnym od odległości, na jaką gracz ma się przemieścić; teleportujesz się o 10 pól do przodu."
o: "Twój program nakłada ograniczenie na liczbę graczy lub rozmiar planszy; wracasz na pole startowe."
p: "Pies zjadł ci dyskietkę z programem; cofasz się o 10 pól."
r: "Zrozumiałeś rekurencję. Rzucasz kostką jeszcze raz i wykonujesz kolejny ruch."
t: "Wysłałeś program nie testując go; cofasz się o 20 pól."
u: "Twój program nie usuwa utworzonych struktur danych; cofasz się o 5 pól."
z: (pole zwykłe, nie powoduje dalszego przemieszczania gracza)

Jeśli na polu zwykłym, na którym ma się znaleźć gracz, ktoś już jest, ten ktoś jest przenoszony na pole startowe.

Gdyby wykonanie ruchu zgodnie z rodzajem pola miało przenieść gracza przed pierwsze pole planszy, umieszczamy go na polu startowym.

Przejście gracza za ostatnie pole planszy powoduje zakończenie przez niego gry.

Symulacja gry kończy się, gdy grę zakończy ostatni gracz. Kończymy także po wykonaniu tysiąca przesunięć graczy.

Podczas gry program wypisuje w kolejnych wierszach na standardowym wyjściu komunikaty o przesunięciach graczy. Mają one postać zgodną z poniższymi przykładami (uwaga: pola planszy numerujemy od 1):

Jan wchodzi na pole numer 5

Jan wraca na pole startowe

Jan konczy gre

Komunikat taki należy wypisać za każdym razem, gdy gracz wejdzie na pole planszy. Ponieważ wejścia na niektóre pola powodują dalsze przesunięcie gracza, czasem wykonując jeden ruch za gracza program wypisze kilka komunikatów.

Przykład

Np. dla danych:

Jan
Katarzyna
Piotr
 
zzzcdzruzerpzzuzzzuzzteozz.

i ciągu rzutów kostką:

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

program powinien wypisać:

Jan wchodzi na pole numer 1
Katarzyna wchodzi na pole numer 3
Piotr wchodzi na pole numer 4
Piotr wchodzi na pole numer 9
Jan wchodzi na pole numer 4
Jan wchodzi na pole numer 9
Piotr wraca na pole startowe
Katarzyna wchodzi na pole numer 6
Piotr wchodzi na pole numer 5
Piotr wchodzi na pole numer 15
Piotr wchodzi na pole numer 10
Piotr wchodzi na pole numer 20
Jan wchodzi na pole numer 15
Jan wchodzi na pole numer 10
Jan wchodzi na pole numer 20
Piotr wraca na pole startowe
Katarzyna wchodzi na pole numer 8
Katarzyna wchodzi na pole numer 3
Piotr wchodzi na pole numer 5
Piotr wchodzi na pole numer 15
Piotr wchodzi na pole numer 10
Piotr wchodzi na pole numer 20
Jan wraca na pole startowe
Jan wchodzi na pole numer 1
Katarzyna wchodzi na pole numer 8
Katarzyna wchodzi na pole numer 3
Piotr wchodzi na pole numer 26
Jan wchodzi na pole numer 2
Katarzyna wchodzi na pole numer 6
Piotr konczy gre
Jan wchodzi na pole numer 5
Jan wchodzi na pole numer 15
Jan wchodzi na pole numer 10
Jan wchodzi na pole numer 20
Katarzyna wchodzi na pole numer 7
Katarzyna wchodzi na pole numer 11
Katarzyna wchodzi na pole numer 16
Jan wchodzi na pole numer 26
Katarzyna wchodzi na pole numer 20
Jan konczy gre
Katarzyna wchodzi na pole numer 22
Katarzyna wchodzi na pole numer 2
Katarzyna wchodzi na pole numer 4
Katarzyna wchodzi na pole numer 9
Katarzyna wchodzi na pole numer 11
Katarzyna wchodzi na pole numer 15
Katarzyna wchodzi na pole numer 10
Katarzyna wchodzi na pole numer 20
Katarzyna wchodzi na pole numer 25
Katarzyna konczy gre

Rok 2007/2008, zadanie 4 - rozwiązanie

program wp07zad4;
 
const
    SCIANY = 6;
    ILE_MAX = 1000;
 
type
    Plansza = ^Pole;
    Gracze = ^Gracz;
    Pole = record
        co : Char;
        kto : Gracze;
        nr : Integer;
        nast, poprz : Plansza
    end;
    Gracz = record
        imie : String;
        gdzie : Plansza;
        nast : Gracze
    end;
 
var aktualny, poprzedni : Gracze;
    start, pom : Plansza;
    dozwolone : Integer;
 
procedure wczytaj;
var atrapa, ostatni : Gracze;
    ostp : Plansza;
    s : String;
    i : Integer;
begin
    new(start);
    start^.nr := 0;
    start^.co := ' ';
    start^.kto := nil;
    start^.poprz := nil;
    new(atrapa);
    atrapa^.nast := nil;
    ostatni := atrapa;
    readln(s);
    while s <> '' do begin
        new(ostatni^.nast);
        ostatni := ostatni^.nast;
        ostatni^.gdzie := start;
        ostatni^.imie := s;
        readln(s)
    end;
    ostatni^.nast := atrapa^.nast;
    poprzedni := ostatni;
    aktualny := atrapa^.nast;
    dispose(atrapa);
    ostp := start;
    i := 1;
    repeat
        new(ostp^.nast);
        ostp^.nast^.poprz := ostp;
        ostp := ostp^.nast;
        ostp^.nr := i;
        i := i + 1;
        read(ostp^.co);
        ostp^.kto := nil
    until ostp^.co = '.';
    ostp^.nast := nil
end;
 
procedure usunAktualnego;
begin
    if aktualny = poprzedni then begin
        dispose(aktualny);
        aktualny := nil;
        poprzedni := nil
    end else begin
        poprzedni^.nast := aktualny^.nast;
        dispose(aktualny);
        aktualny := poprzedni^.nast
    end;
end;
 
procedure ruchAktualnego(k : Integer);
begin
    if dozwolone > 0 then begin
        dozwolone := dozwolone - 1;
        aktualny^.gdzie^.kto := nil;
        if k > 0 then
            while (k <> 0) and (aktualny^.gdzie^.nast <> nil) do begin
                k := k - 1;
                aktualny^.gdzie := aktualny^.gdzie^.nast
            end
        else
            while (k <> 0) and (aktualny^.gdzie^.poprz <> nil) do begin
                k := k + 1;
                aktualny^.gdzie := aktualny^.gdzie^.poprz
            end;
        if aktualny^.gdzie^.co = '.' then begin
            writeln(aktualny^.imie, ' konczy gre');
            usunAktualnego
        end else begin
            if aktualny^.gdzie^.co = ' ' then begin
                writeln(aktualny^.imie, ' wraca na pole startowe');
                poprzedni := aktualny;
                aktualny := aktualny^.nast
            end else begin
                writeln(aktualny^.imie, ' wchodzi na pole numer ', aktualny^.gdzie^.nr);
                case aktualny^.gdzie^.co of
                    'z' : begin
                        if aktualny^.gdzie^.kto <> nil then begin
                            if dozwolone > 0 then begin
                                dozwolone := dozwolone - 1;
                                writeln(aktualny^.gdzie^.kto^.imie, ' wraca na pole startowe')
                            end;
                            aktualny^.gdzie^.kto^.gdzie := start
                        end;
                        aktualny^.gdzie^.kto := aktualny;
                        poprzedni := aktualny;
                        aktualny := aktualny^.nast
                    end;
                    'o' :
                        ruchAktualnego(-aktualny^.gdzie^.nr);
                    'p' :
                        ruchAktualnego(-10);
                    'c' :
                        ruchAktualnego(5);
                    'd', 'e' :
                        ruchAktualnego(10);
                    'r' :
                        ruchAktualnego(1 + random(SCIANY));
                    't' :
                        ruchAktualnego(-20);
                    'u' :
                        ruchAktualnego(-5)
                end
            end
        end
    end
end;
 
begin
    randomize;
    wczytaj;
    dozwolone := ILE_MAX;
    while (aktualny <> nil) and (dozwolone > 0) do
        ruchAktualnego(1 + random(SCIANY));
    while aktualny <> nil do
        usunAktualnego;
    while start <> nil do begin
        pom := start;
        start := start^.nast;
        dispose(pom)
    end
end.

Załącznik	Wielkość
wp10zad4.pas	3.81 KB
wp09zad4.pas	4.71 KB
wp08zad4.pas	6.38 KB
wp07zad4.pas	4.04 KB

Informatyka MIMUW