Laboratorium 8: Omówienie zadania zaliczeniowego 2

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

Rok 2010/2011, zadanie 2

Wprowadzenie

Maszyna jednopierścieniowa to abstrakcyjny model komputera. Rolę jej pamięci pełni struktura danych nazywana pierścieniem, przechowująca ciąg znaków, czyli słowo nad pewnym alfabetem. Z pierścieniem związany jest kursor wyznaczający aktualną pozycję. Kursor może się znajdować przed pierwszym znakiem, pomiędzy parą sąsiadujących znaków lub po ostatnim znaku. Znak, przed którym jest kursor, nazywamy znakiem aktualnym. Gdy pierścień jest niepusty a kursor znajduje się za ostatnim znakiem przyjmujemy, że znakiem aktualnym jest pierwszy znak pierścienia.

Maszyna wykonuje program będący zbiorem instrukcji. W każdej chwili pracy maszyna jest w jednym ze skończonego zbioru stanów reprezentowanych przez znaki. Instrukcja wyznaczona na podstawie aktualnego stanu i zawartości pierścienia wskazuje, którą z dwóch operacji na pierścieniu: wstawienia czy usunięcia znaku należy wykonać i do którego stanu przejść.

Postać programu maszyny jednopierścieniowej opisana jest gramatyką:

Program -> CiągInstrukcji
CiągInstrukcji -> CiągInstrukcji Instrukcja | Instrukcja
Instrukcja -> InstrukcjaUsunięcia | InstrukcjaWstawienia
InstrukcjaUsunięcia -> StanAktualny / ZnakUsuwany StanDocelowy
InstrukcjaWstawienia -> StanAktualny _ ZnakWstawiany StanDocelowy
StanAktualny -> Stan
StanDocelowy -> Stan
Stan -> znak
ZnakUsuwany -> Dana
ZnakWstawiany -> Dana
Dana -> znak

gdzie symbol końcowy znak reprezentuje dowolny znak, / to ukośnik a _ to podkreślenie.

W poprawnym programie dla każdej pary <StanAktualny, ZnakUsuwany> jest co najwyżej jedna instrukcja usunięcia a dla każdego stanu co najwyżej jedna instrukcja wstawienia.

Przyjmujemy, że początkowym stanem maszyny jest ten, od którego zaczyna się pierwsza instrukcja programu.

W chwili rozpoczęcia pracy maszyna znajduje się w stanie początkowym. Jej dane zapisane są w pierścieniu a kursor jest przed pierwszym znakiem. Maszyna wykonuje w pętli następujące czynności:

Jeśli pierścień danych nie jest pusty i dla aktualnego stanu jest instrukcja usunięcia aktualnego znaku, znak ten jest usuwany a maszyna przechodzi do stanu docelowego wskazanego w tej instrukcji. Kursor po wykonaniu instrukcji znajduje się na pozycji bezpośrednio za usuniętym znakiem.
Jeśli pierścień jest pusty lub dla aktualnego stanu nie ma instrukcji usunięcia aktualnego znaku, ale jest instrukcja wstawienia, znak określony w instrukcji jest wstawiany do pierścienia na pozycji wyznaczonej przez kursor a maszyna przechodzi do wskazanego w tej instrukcji stanu docelowego. Po wykonaniu instrukcji kursor znajduje się na pozycji bezpośrednio za wstawionym znakiem.
Jeśli maszyna nie może wykonać ani operacji usunięcia ani wstawienia, kończy pracę i wypisuje zawartość pierścienia, zaczynając od pierwszego znaku.

Obserwacje

Operacje maszyny jednopierścieniowej odpowiadają operacjom na tekście wykonywanym za pomocą edytora. Operacja wstawienia znaku daje efekt taki, jak naciśnięcie klawisza z tym znakiem. Operacja usunięcia znaku, jeśli kursor nie jest na końcu tekstu, działa tak, jak naciśnięcie klawisza Delete. Gdy kursor jest na końcu tekstu dostajemy efekt taki, jaki daje naciśnięcie Delete poprzedzone przeniesieniem kursora na początek tekstu.
Pozycja kursora w chwili zakończenia pracy maszyny nie ma wpływu na postać wyniku.

Polecenie

Napisz program który, mając w pierwszym wierszu wejścia tekstową reprezentację programu maszyny jednopierścieniowej, zasymuluje jej działanie na ciągu znaków zapisanym w drugim wierszu wejścia i wypisze na wyjście wiersz zawierający wynik obliczeń.

Przykłady

Dla danych:

h_hee_ell_lLL_loo_ox
World

program powinien skopiować na wyjście drugi wiersz wejścia, dopisując przed nim hello. Wynikiem powinno więc być:

helloWorld

Dla danych:

a_!bb/xcb/!fc_xbb/ydd_ybb/zee/xee/yee/zbe/!f
xxyzxyzyzzxxxzyz

program powinien wypisać na wyjście znajdujące się w drugim wierszu wejścia słowo nad alfabetem {x, y, z}, usuwając z niego kolejne segmenty zaczynające się od "z" i kończące się na najbliższym "z" lub na końcu słowa. Wynikiem powinno więc być:

xxyyxxx

Dla danych:

a_!bb/xcb/yfb/!tt_txc/xdd_xcf/ygg_yfc/yef/xee/!ae/xhh_xee/yii_yec/!jf/!jj/xjj/yjj_nx
yxxyxxyxyy

program powinien wypisać na wyjście "t", jeśli w słowie nad alfabetem {x, y} zapisanym w drugim wierszu wejścia liczba wystąpień "x" jest równa liczbie wystąpień "y", a n w przeciwnym przypadku. Wynikiem powinno więc być:

Uwagi

Do reprezentacji programu maszyny jednopierścieniowej można użyć tablicy dwuwymiarowej indeksowanej znakami reprezentującym stany i dane.
Wolno założyć, że program maszyny zapisany w pierwszym wierszu wejścia jest poprawny a jego długość nie przekracza maksymalnej długości napisu będącego wartością typu String.
Wolno założyć, że długość drugiego wiersza wejścia, w którym jest początkowa zawartość pierścienia, nie przekracza maksymalnej długości napisu będącego wartością typu String. Podczas pracy maszyny rozmiar pierścienia może jednak to ograniczenie przekroczyć. Gdyby w pierścieniu znalazło się więcej niż 10000 znaków, należy przerwać pracę maszyny i wypisać na wyjście jeden wiersz z komunikatem:przepelnienie pamieci
Ocena jakości rozwiązania, w którym koszty operacji wstawienia i usunięcia z pierścienia nie będą stałe, zostanie obniżona o 1 pkt.

Omawiając treść zadania byłoby dobrze przeanalizować ze studentami przynajmniej dwa pierwsze przykłady. Warto też dokładnie wyjaśnić operacje wstawiania i usuwania. Najlepiej zademonstrować to w edytorze tekstu wyświetlającym kursor w postaci pionowej kreski pomiędzy znakami, np. gedit.

Jedyną potrzebną do rozwiązania zadania konstrukcja Pascala, której jeszcze nie wprowadziliśmy, są tablice wielowymiarowe. Trzeba wyjaśnić studentom, co to jest i pokazać jakiś przykład. Na wszelki wypadek powiedzmy też, że indeksami w tablicy mogą być wartości typu Char. Chyba nie wszyscy są tego świadomi.

Jak zawsze, zaproponujmy studentom podzielenie pracy na kilka etapów, np.:

implementacja pierścienia z operacjami wstawiania, usuwania, wczytywania, wypisywania
budowa reprezentacji programu maszyny
symulacja działania maszyny

Sensownym pomysłem jest zrealizowanie w pierwszej wersji rozwiązania pierścienia z operacjami o koszcie liniowym. Osiąnięcie kosztu stałego nie jest łatwe i zapewne wielu studentów z tym sobie nie poradzi. Zwróćmy uwagę, że kara za nieefektywność jest w tym przypadku niewielka.

Rok 2010/2011, zadanie 2 - rozwiązanie

program wp10zad2;
 
const
    MAX_ROZMIAR = 1000;
    PIERWSZY = chr(0);
    OSTATNI = chr(255);
 
type
    Stan = Char;
    Dana = Char;
    Pierscien = record
        elementy : array [0 .. MAX_ROZMIAR] of Dana;
        aktualny, koniec, rozmiar, zaKursorem : Integer
    end;
 
var tekstProgramu : String;
    dane : Pierscien;
    poczatkowy : Stan;
    usuniecie : array [Stan, Dana] of Boolean;
    poUsunieciu : array [Stan, Dana] of Stan;
    wstawienie : array [Stan] of Boolean;
    wstawiana : array [Stan] of Dana;
    poWstawieniu : array [Stan] of Stan;
 
function aktualny(var p : Pierscien) : Dana;
begin
    aktualny := p.elementy[p.aktualny]
end;
 
function rozmiar(var p : Pierscien) : Integer;
begin
    rozmiar := p.rozmiar
end;
 
procedure wstaw(var p : Pierscien; c : Char);
begin
    if p.rozmiar = MAX_ROZMIAR then begin
        writeln('przepelnienie pamieci');
        halt
    end;
    p.elementy[p.koniec] := c;
    p.koniec := (p.koniec + 1) mod (MAX_ROZMIAR + 1);
    inc(p.rozmiar)
end;
 
procedure usun(var p : Pierscien);
begin
    assert(p.rozmiar > 0);
    p.aktualny := (p.aktualny + 1) mod (MAX_ROZMIAR + 1);
    p.zaKursorem := (p.zaKursorem - 1 + p.rozmiar) mod p.rozmiar;
    dec(p.rozmiar)
end;
 
procedure wczytaj(var p : Pierscien);
begin
    p.aktualny := 0;
    p.koniec := 0;
    while not eoln do begin
        assert(p.koniec < MAX_ROZMIAR);
        read(p.elementy[p.koniec]);
        p.koniec := p.koniec + 1
    end;
    p.rozmiar := p.koniec;
    p.zaKursorem := p.rozmiar
end;
 
procedure wypisz(var p : Pierscien);
var i, wypisane : Integer;
begin
    if p.rozmiar > 0 then begin
        wypisane := 0;
        i := p.zaKursorem mod p.rozmiar;
        while wypisane < p.rozmiar do begin
            write(p.elementy[(i + p.aktualny) mod (MAX_ROZMIAR + 1)]);
            inc(wypisane);
            i := (i + 1) mod p.rozmiar
        end
    end;
    writeln
end;
 
procedure zbuduj(m : String);
var i : Integer;
    s : Stan;
    d : Dana;
begin
    assert(m <> '');
    poczatkowy := m[1];
    for s := PIERWSZY to OSTATNI do begin
        wstawienie[s] := false;
        for d := PIERWSZY to OSTATNI do
            usuniecie[s, d] := false
    end;
    i := 1;
    while i <= Length(m) do begin
        assert(i + 3 <= length(m));
        if m[i + 1] = '/' then begin
            usuniecie[m[i], m[i + 2]] := true;
            poUsunieciu[m[i], m[i + 2]] := m[i + 3]
        end else begin
            assert(m[i + 1] = '_');
            wstawienie[m[i]] := true;
            wstawiana[m[i]] := m[i + 2];
            poWstawieniu[m[i]] := m[i + 3]
        end;
        i := i + 4
    end
end;
 
procedure wykonaj;
var s : Stan;
    d : Dana;
    dalej : Boolean;
begin
    s := poczatkowy;
    dalej := true;
    while dalej do begin
        dalej := false;
        if rozmiar(dane) > 0 then begin
            d := aktualny(dane);
            if usuniecie[s, d] then begin
                usun(dane);
                s := poUsunieciu[s, d];
                dalej := true
            end
        end;
        if not dalej and wstawienie[s] then begin
            wstaw(dane, wstawiana[s]);
            s := poWstawieniu[s];
            dalej := true
        end
    end
end;
 
begin
    readln(tekstProgramu);
    zbuduj(tekstProgramu);
    wczytaj(dane);
    wykonaj;
    wypisz(dane)
end.

Rok 2009/2010, zadanie 2

Wprowadzenie

Tematem zadania jest "Nieprzeciętna łamigłówka":

Dla zadanej całkowitej wartości k >= 1 zbuduj możliwie najdłuższą łamaną, która:

zaczyna się w środku pewnego okręgu
składa się z odcinków o długości równej promieniowi tego okręgu
kąty nachylenia odcinków łamanej do osi układu są wielokrotnością 2 * π / k
odcinki łamanej są wewnątrz okręgu (koniec odcinka może leżeć na okręgu)
żadne dwa odcinki łamanej nie przecinają się

Przyjmujemy tu, że odcinki przecinają się, jeśli mają choć jeden punkt wspólny, przy czym końców odcinka nie uznajemy za jego część.

Polecenie

Napisz program pomagający użytkownikowi w rozwiązaniu łamigłówki. Program powinien pobierać z wejścia nieujemne liczby całkowite i rysować kolejne odcinki łamanej, nachylone w stosunku do osi układu pod kątem będącym iloczynem wczytanej liczby i 2 * π / k.

Program powinien pomijać liczby, które spowodowałyby złamanie zasad łamigłówki.

Pracę należy zakończyć po wczytaniu liczby mniejszej od 0.

Wskazówki

Łamaną będziemy rysowali za pomocą programu Ghostscript.
Wartość parametru k łamigłówki powinna być określona stałą symboliczną zdefiniowaną w treści programu.
Można założyć, że maksymalną długością konstruowanej łamanej będzie 1000.
Algorytm badający przecięcie dwóch odcinków można przepisać z materiałów na "ważniaku". Znajduje się w ćwiczeniach do modułu nr 1 Wstępu do programowania. Trzeba go zmodyfikować, by końca odcinka nie traktował jak jego części.
Działania na wartościach typu Real zwykle nie dają dokładnego wyniku. Jeśli np. chcemy zbadać, czy dwie liczby rzeczywiste są równe, nie powinniśmy używać operatora porównania =, tylko sprawdzić, czy wartość bezwzględna różnicy tych liczb jest mała.
W pliku lamiglowka.ps jest przykładowy wynik działania programu (i jego użytkownika) dla k = 7.

Wskazówki do przekazania podczas zajęć laboratoryjnych

Proponujemy podzielenie pracy nad programem na kilka etapów:

program, który rysuje łamaną składającą się z odcinków od końca ostatniego odcinka do punktu, którego współrzędne wprowadza użytkownik
dorysowanie okręgu, w którym będą odcinki, oraz "ściągawki" w rogu strony. Rysując ściągawkę studenci wymyślą, jak zastosować funkcje "sin" i "cos"
pobieranie od użytkownika, zamiast współrzędnych punktu docelowego, liczby całlkowitej określającej, w sposób opisany w treści zadania, kąt nachylenia kolejnego odcinka
wprowadzenie blokady uniemożliwiającej wyjście poza okrąg
implementacja algorytmu badającego przecięcie dwóch odcinków
uzupełnienie programu rysującego odcinki o zapamiętywanie w tablicy współrzędnych punktów i połączenie go z algorytmem sprawdzającym przecięcie

Punkty będziemy tu reprezentować jako pary liczb rzeczywistych. Ładniej wyglądałoby z rekordami, ale studenci jeszcze ich nie znają.

Do badania przecięcia dwóch odcinków najlepiej zrobić najpierw oddzielny program pobierający z wejścia osiem liczb rzeczywistych, będących współrzędnymi końców dwóch odcinków i wypisujący informację, czy odcinki się przecinają. Punktem wyjścia będzie algorytm z "ważniaka", który zmodyfikujemy odpowiednio do warunków zadania.

Uwaga 1: to nie jest łatwe i trzeba naprawdę zrozumieć algorytm z ważniaka, by wiedzieć, co w nim poprawić. Pewnie nie wszystkim uda się to zrobić do końca dobrze. Niech studenci dokładnie przetestują swoje rozwiązanie.

Uwaga 2: wydaje mi się, że w algorytmie jest błąd - nie działa, gdy odcinki sa współliniowe i odcinek "pq" jest w środku odcinka "rs". Nam to akurat nie będzie przeszkadzało, bo wszystkie nasze odcinki są tej samej długości.

Studenci zaawansowani mogą zastanowić się, jak zautomatyzować rozwiązywanie łamigłówki. Jest szansa, ze wymyślą rekurencję.

Dane do testów, dla k=7, to np.:

0 3 4 1 6 4 1 4 6 1 4

(powinno dać się zrobić)

0 3 0

(ostatni odcinek nie jest dozwolony)

0 3 6

(ostatni odcinek nie jest dozwolony)

0 3 4 0

(ostatni odcinek nie jest dozwolony)

0 3 4 6 2 1 5 0

(ostatni odcinek nie jest dozwolony)

Warto też sprawdzić, czy program zachowuje się sensownie z innymi wartościami k (1, 2, 3).

Rok 2009/2010, zadanie 2 - rozwiązanie

program wp09zad2;
 
const
    SZEROKOSC_STRONY = 595;
    WYSOKOSC_STRONY = 842;
    SRODEK_SZEROKOSCI = SZEROKOSC_STRONY / 2;
    SRODEK_WYSOKOSCI = WYSOKOSC_STRONY / 2;
    PROMIEN = SZEROKOSC_STRONY / 2 - 10;
    LICZBA_KATOW = 7;
    JEDNOSTKA_KATA = 2 * PI / LICZBA_KATOW;
    PROMIEN_SCIAGAWKI = 30;
    X_SRODKA_SCIAGAWKI = SZEROKOSC_STRONY - PROMIEN_SCIAGAWKI - 10;
    Y_SRODKA_SCIAGAWKI = PROMIEN_SCIAGAWKI + 10;
    MAKSYMALNA_DLUGOSC_LAMANEJ = 1000;
    EPSILON = 0.00001;
 
type
    Punkt = record
        x, y : Real
    end;
    Lamana = record
        punkty : array [0 .. MAKSYMALNA_DLUGOSC_LAMANEJ] of Punkt;
        dlugosc : Integer
    end;
 
function max(a, b : Real) : Real;
begin
    if a < b then
        max := b
    else
        max := a
end;
 
function min(a, b : Real) : Real;
begin
    if a < b then
        min := a
    else
        min := b
end;
 
function wieksze(x, y : Real) : Boolean;
begin
    wieksze := x - y > EPSILON
end;
 
function rowne(x, y : Real) : Boolean;
begin
    rowne := abs(x - y) < EPSILON
end;
 
function M(p, q, r : Punkt) : Real;
{Definicja przepisana z wazniaka}
begin
    M := p.x * q.y + p.y * r.x + r.y * q.x - (r.x * q.y + q.x * p.y + r.y * p.x)
end;
 
function przeciecieRzutu(a, b, c, d : Real) : Boolean;
begin
    przeciecieRzutu := wieksze(min(b, d), max(a, c))
end;
 
function przecinajaSie(p, q, r, s : Punkt) : Boolean;
{Definicja przepisana z wazniaka, z poprawkami}
var Mp, Mq, Mr, Ms : Real;
begin
    Mp := M(r, s, p);
    Mq := M(r, s, q);
    Mr := M(p, q, r);
    Ms := M(p, q, s);
    if wieksze(Mp * Mq, 0) or wieksze(Mr * Ms, 0) then
        przecinajaSie := false
    else if wieksze(0, Mp * Mq) and wieksze(0, Mr * Ms) then
        przecinajaSie := true
    else if not rowne(Mp, 0) or not rowne(Mq, 0)
            or not rowne(Mr, 0) or not rowne(Ms, 0) then
        przecinajaSie := false
    else
        przecinajaSie :=
            przeciecieRzutu(min(p.x, q.x), max(p.x, q.x), min(r.x, s.x), max(r.x, s.x)) or
            przeciecieRzutu(min(p.y, q.y), max(p.y, q.y), min(r.y, s.y), max(r.y, s.y))
end;
 
function punktDozwolony(var aktualna : Lamana; p : Punkt) : Boolean;
var ok : Boolean;
    i : Integer;
begin
    if wieksze(sqr(p.x - SRODEK_SZEROKOSCI) + sqr(p.y - SRODEK_WYSOKOSCI),
               sqr(PROMIEN)) then
        punktDozwolony := false
    else begin
        ok := true;
        i := 1;
        while (i <= aktualna.dlugosc) and ok do
            if przecinajaSie(
                aktualna.punkty[i - 1], aktualna.punkty[i],
                aktualna.punkty[aktualna.dlugosc], p) then
                ok := false
            else
                i := i + 1;
        punktDozwolony := ok
    end
end;
 
procedure rysujPlansze;
var i : Integer;
begin
    writeln('%!PS');
    write(SRODEK_SZEROKOSCI, ' ', SRODEK_WYSOKOSCI, ' ', PROMIEN);
    writeln(' 0 360 arc closepath stroke');
    for i := 0 to LICZBA_KATOW - 1 do begin
        write(X_SRODKA_SCIAGAWKI, ' ', Y_SRODKA_SCIAGAWKI, ' moveto ');
        write(X_SRODKA_SCIAGAWKI + PROMIEN_SCIAGAWKI * sin(JEDNOSTKA_KATA * i), ' ');
        write(Y_SRODKA_SCIAGAWKI + PROMIEN_SCIAGAWKI * cos(JEDNOSTKA_KATA * i));
        writeln(' lineto stroke')
    end;
    flush(output)
end;
 
procedure rysujOdcinek(poczatek, koniec : punkt; p : Integer);
begin
    writeln('%Odcinek w kierunku ', p);
    write(poczatek.x, ' ', poczatek.y, ' moveto ');
    writeln(koniec.x, ' ', koniec.y, ' lineto stroke');
    flush(output)
end;
 
procedure obliczDocelowy(poczatek : Punkt; p : Integer; var koniec : Punkt);
begin
    koniec.x := poczatek.x + PROMIEN * sin(JEDNOSTKA_KATA * p);
    koniec.y := poczatek.y + PROMIEN * cos(JEDNOSTKA_KATA * p)
end;
 
procedure uzupelnijStrone(dlugosc : Integer);
begin
    writeln('/Courier findfont 100 scalefont setfont');
    writeln('10 20 moveto (', dlugosc, ') show');
    writeln('showpage');
    flush(output);
    readln
end;
 
procedure inicjuj(var aktualna : Lamana);
begin
    aktualna.punkty[0].x := SRODEK_SZEROKOSCI;
    aktualna.punkty[0].y := SRODEK_WYSOKOSCI;
    aktualna.dlugosc := 0
end;
 
procedure dodajPunkt(var aktualna : Lamana; docelowy : Punkt; p : Integer);
begin
    aktualna.dlugosc := aktualna.dlugosc + 1;
    aktualna.punkty[aktualna.dlugosc] := docelowy
end;
 
procedure rozwiaz;
var p : Integer;
    docelowy : Punkt;
    aktualna : Lamana;
begin
    inicjuj(aktualna);
    rysujPlansze;
    readln(p);
    while p >= 0 do begin
        obliczDocelowy(aktualna.punkty[aktualna.dlugosc], p, docelowy);
        if punktDozwolony(aktualna, docelowy) then begin
            rysujOdcinek(aktualna.punkty[aktualna.dlugosc], docelowy, p);
            dodajPunkt(aktualna, docelowy, p)
        end;
        readln(p)
    end;
    uzupelnijStrone(aktualna.dlugosc)
end;
 
begin
    rozwiaz
end.

Rok 2008/2009, zadanie 2

Wprowadzenie

"Saper" to jednoosobowa gra prowadzona na prostokątnej planszy. W chwili rozpoczęcia gry, wszystkie pola planszy są zasłonięte. Na pewnej liczbie losowo wybranych pól znajdują się "miny". Zadaniem grającego jest odsłonięcie wszystkich pól, na których nie ma min.

Gracz w kolejnych krokach wykonuje jedną z dwóch akcji:

odsłonięcie wskazanego pola: Jeśli jest na nim mina, kończymy grę. Jeśli miny nie ma, gracz otrzymuje informację, ile min z tym polem sąsiaduje. Jeśli na żadnym z ośmiu sąsiednich pól nie ma miny, pola te są również odsłaniane.
oznaczenie zasłoniętego pola: Gracz oznacza pola na których, jego zdaniem, są miny. Zabezpiecza je w ten sposób przed przypadkowym odsłonięciem.

Polecenie

Napisz program umożliwiający grę w Sapera. Program powinien wczytywać kolejne polecenia z wejścia i wypisywać aktualny stan planszy na wyjście. Może, choć nie musi, naśladować działanie programu, którego wyniki znajdują się w przykładach poniżej.

Przykład 1 (plansza 8 na 8, 10 min)

Tu demonstrujemy zachowanie programu w sytuacjach typowych.

Tekst po dwukropku, będący parą litera+liczba, opcjonalnie poprzedzoną znakiem '#', to polecenie wpisane przez gracza. Resztę tekstu wypisał program.

 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . . . . . . . |
4| . . . . . . . . |
3| . . . . . . . . |
2| . . . . . . . . |
1| . . . . . . . . |
 +-----------------+
   a b c d e f g h
1(10): a1
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . . . . . . . |
4| 1 2 . 1 1 3 . . |
3|   1 1 1   1 . . |
2|         1 1 . . |
1|         1 . . . |
 +-----------------+
   a b c d e f g h
2(10): #f1
Oznaczyles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . . . . . . . |
4| 1 2 . 1 1 3 . . |
3|   1 1 1   1 . . |
2|         1 1 . . |
1|         1 # . . |
 +-----------------+
   a b c d e f g h
3(9): #c4
Oznaczyles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . . . . . . . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 . . |
2|         1 1 . . |
1|         1 # . . |
 +-----------------+
   a b c d e f g h
4(8): c5
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 . . . . . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 . . |
2|         1 1 . . |
1|         1 # . . |
 +-----------------+
   a b c d e f g h
5(8): d5
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 . . . . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 . . |
2|         1 1 . . |
1|         1 # . . |
 +-----------------+
   a b c d e f g h
6(8): e5
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 . . . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 . . |
2|         1 1 . . |
1|         1 # . . |
 +-----------------+
   a b c d e f g h
7(8): g1
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 . . . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 . . |
2|         1 1 . . |
1|         1 # 1 . |
 +-----------------+
   a b c d e f g h
8(8): h1
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 . . . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
9(8): #f5
Oznaczyles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 # . . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
10(7): #g5
Oznaczyles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 # # . |
4| 1 2 # 1 1 3 . . |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
11(6): #g4
Oznaczyles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 # # . |
4| 1 2 # 1 1 3 # . |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
12(5): h4
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 # # . |
4| 1 2 # 1 1 3 # 2 |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
13(5): h5
Odsloniles pole
 +-----------------+
8| . . . . . . . . |
7| . . . . . . . . |
6| . . . . . . . . |
5| . . 2 2 2 # # 3 |
4| 1 2 # 1 1 3 # 2 |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
14(5): e8
Odsloniles pole
 +-----------------+
8|             2 . |
7|     1 1 1   3 . |
6| 1 1 1 . 2 2 4 . |
5| . . 2 2 2 # # 3 |
4| 1 2 # 1 1 3 # 2 |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
15(5): #h8
Oznaczyles pole
 +-----------------+
8|             2 # |
7|     1 1 1   3 . |
6| 1 1 1 . 2 2 4 . |
5| . . 2 2 2 # # 3 |
4| 1 2 # 1 1 3 # 2 |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
16(4): #h7
Oznaczyles pole
 +-----------------+
8|             2 # |
7|     1 1 1   3 # |
6| 1 1 1 . 2 2 4 . |
5| . . 2 2 2 # # 3 |
4| 1 2 # 1 1 3 # 2 |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
17(3): #h6
Oznaczyles pole
 +-----------------+
8|             2 # |
7|     1 1 1   3 # |
6| 1 1 1 . 2 2 4 # |
5| . . 2 2 2 # # 3 |
4| 1 2 # 1 1 3 # 2 |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 # 1   |
 +-----------------+
   a b c d e f g h
18(2): b5
Odsloniles wszystkie pola bez min. Wygrales !
 +-----------------+
8|             2 * |
7|     1 1 1   3 * |
6| 1 1 1 * 2 2 4 * |
5| * 2 2 2 2 * * 3 |
4| 1 2 * 1 1 3 * 2 |
3|   1 1 1   1 1 1 |
2|         1 1 1   |
1|         1 * 1   |
 +-----------------+
   a b c d e f g h

Przykład 2 (plansza 15 na 20, 50 min)

Tu demonstrujemy zachowanie programu w sytuacjach nietypowych.

 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
0| . . . . . . . . . . . . . . . . . . . . |
9| . . . . . . . . . . . . . . . . . . . . |
8| . . . . . . . . . . . . . . . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
1(50): z20
Niepoprawny ruch
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
0| . . . . . . . . . . . . . . . . . . . . |
9| . . . . . . . . . . . . . . . . . . . . |
8| . . . . . . . . . . . . . . . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
2(50): k9
Odsloniles pole
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . 1 1 2 . . . . . . . . . . |
1| . . . . . . . 1   1 2 . . . . . . . . . |
0| . . . . . . . 2 1   1 2 2 4 . . . . . . |
9| . . . . . . . . 1         3 . . . . . . |
8| . . . . . . . . 3 2 1 1 2 4 . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
3(50): j10
To pole jest odsloniete
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . 1 1 2 . . . . . . . . . . |
1| . . . . . . . 1   1 2 . . . . . . . . . |
0| . . . . . . . 2 1   1 2 2 4 . . . . . . |
9| . . . . . . . . 1         3 . . . . . . |
8| . . . . . . . . 3 2 1 1 2 4 . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
4(50): #j10
To pole jest odsloniete
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . 1 1 2 . . . . . . . . . . |
1| . . . . . . . 1   1 2 . . . . . . . . . |
0| . . . . . . . 2 1   1 2 2 4 . . . . . . |
9| . . . . . . . . 1         3 . . . . . . |
8| . . . . . . . . 3 2 1 1 2 4 . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
5(50): #a1
Oznaczyles pole
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . 1 1 2 . . . . . . . . . . |
1| . . . . . . . 1   1 2 . . . . . . . . . |
0| . . . . . . . 2 1   1 2 2 4 . . . . . . |
9| . . . . . . . . 1         3 . . . . . . |
8| . . . . . . . . 3 2 1 1 2 4 . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| # . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
6(49): #a1
Skasowales oznaczenie
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . 1 1 2 . . . . . . . . . . |
1| . . . . . . . 1   1 2 . . . . . . . . . |
0| . . . . . . . 2 1   1 2 2 4 . . . . . . |
9| . . . . . . . . 1         3 . . . . . . |
8| . . . . . . . . 3 2 1 1 2 4 . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
7(50): #h9
Oznaczyles pole
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . 1 1 2 . . . . . . . . . . |
1| . . . . . . . 1   1 2 . . . . . . . . . |
0| . . . . . . . 2 1   1 2 2 4 . . . . . . |
9| . . . . . . . # 1         3 . . . . . . |
8| . . . . . . . . 3 2 1 1 2 4 . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
8(49): h9
Pola oznaczonego nie mozna odslonic
 +-----------------------------------------+
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . 1 1 2 . . . . . . . . . . |
1| . . . . . . . 1   1 2 . . . . . . . . . |
0| . . . . . . . 2 1   1 2 2 4 . . . . . . |
9| . . . . . . . # 1         3 . . . . . . |
8| . . . . . . . . 3 2 1 1 2 4 . . . . . . |
7| . . . . . . . . . . . . . . . . . . . . |
6| . . . . . . . . . . . . . . . . . . . . |
5| . . . . . . . . . . . . . . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . . . . . . . . . . . . . . . |
2| . . . . . . . . . . . . . . . . . . . . |
1| . . . . . . . . . . . . . . . . . . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t
9(49): k12
Na tym polu jest mina. Przegrales !
 +-----------------------------------------+
5| . . . * . * * . . . . . * . . . . . . . |
4| . . . . . . . . . . . . . . . . . . . . |
3| . . . . . . * . . * . . . . . . . . . . |
2| . . . . . * . 1 1 2 * . * . . * * . . * |
1| . * . * . . . 1   1 2 * * . * . . . . * |
0| . . . * * . * 2 1   1 2 2 4 * . . . . . |
9| . . . . . . . * 1         3 * . * . . . |
8| . . . . . * . . 3 2 1 1 2 4 * . . . . . |
7| . . . . . . . . * * . . * * . . * * . . |
6| . . * . . . . . . . . . . . . * . . . . |
5| . . . . . . . . * . . * . . . . . . . . |
4| * * . . . . . . . . . . . . * . . . * . |
3| . . . . . . . . . . . . * . . . * . . * |
2| . . . . . * . . . * . . . . . . . * . . |
1| . . . . . . * . . . . . . * . . * . . . |
 +-----------------------------------------+
   a b c d e f g h i j k l m n o p q r s t

Uwagi

Rozmiar planszy oraz liczba min powinny być określone w kodzie programu za pomocą stałych symbolicznych.
Można przyjąć, że szerokość planszy nie przekroczy 26.
Można założyć, że polecenia wczytywane z wejścia będą miały poprawny format.
Odsłanianie pól najłatwiej jest zrealizować za pomocą rekurencji.
Funkcja chr() daje znak o kodzie przekazanym jej jako argument a funkcja ord() wykonuje operację przeciwną, czyli daje kod znaku będącego argumentem.

Rok 2008/2009, zadanie 2 - rozwiązanie

program wp08zad2;
 
const
    WYSOKOSC = 15;
    SZEROKOSC = 20;
    LICZBA_MIN = 50;
 
type
    StanPol = array [1 .. WYSOKOSC, 1 .. SZEROKOSC] of Boolean;
 
var mina, odsloniete, oznaczone : StanPol;
    sasiadujaceMiny : array [1 .. WYSOKOSC, 1 .. SZEROKOSC] of Integer;
    liczbaOdslonietych, liczbaFlag : Integer;
 
procedure wypelnij;
var i, j, k, x, y : Integer;
begin
    for i := 1 to WYSOKOSC do
        for j := 1 to SZEROKOSC do begin
            mina[i, j] := false;
            odsloniete[i, j] := false;
            oznaczone[i, j] := false;
            sasiadujaceMiny[i, j] := 0
        end;
    k := 1;
    while k <= LICZBA_MIN do begin
        i := random(WYSOKOSC) + 1;
        j := random(SZEROKOSC) + 1;
        if not mina[i, j] then begin
            mina[i, j] := true;
            for x := i - 1 to i + 1 do
                if x in [1 .. WYSOKOSC] then
                    for y := j - 1 to j + 1 do
                        if y in [1 .. SZEROKOSC] then
                            sasiadujaceMiny[x, y] := sasiadujaceMiny[x, y] + 1;
            k:=k+1
        end
    end;
    liczbaFlag := LICZBA_MIN;
    liczbaOdslonietych := 0
end;
 
procedure odslon(x, y : Integer);
var i, j : Integer;
begin
    if (x in [1 .. WYSOKOSC]) and (y in [1 .. SZEROKOSC]) then
        if not odsloniete[x, y] then begin
            liczbaOdslonietych := liczbaOdslonietych + 1;
            odsloniete[x, y] := true;
            if sasiadujaceMiny[x, y] = 0 then
                for i := x - 1 to x + 1 do
                    for j := y - 1 to y + 1 do
                        if (i <> x) or (j <> y) then
                            odslon(i, j)
        end
end;
 
procedure wypisz(pokazacMiny : Boolean);
var i, j : Integer;
    c : Char;
begin
    write(' +');
    for i := 1 to SZEROKOSC do
        write('--');
    writeln('-+');
    for i := WYSOKOSC downto 1 do begin
        write(i mod 10, '|');
        for j := 1 to SZEROKOSC do
            if pokazacMiny and mina[i, j] then
                write(' *')
            else
                if odsloniete[i, j] then
                    if sasiadujaceMiny[i, j] = 0 then
                        write('  ')
                    else
                        write(' ', chr(ord('0') + sasiadujaceMiny[i, j]))
                else
                    if oznaczone[i, j] then
                        write(' #')
                    else
                        write(' .');
        writeln(' |')
    end;
    write(' +');
    for i := 1 to SZEROKOSC do
        write('--');
    writeln('-+');
    write('  ');
    for c := 'a' to chr(ord('a') + SZEROKOSC - 1) do
        write(' ', c);
    writeln
end;
 
procedure graj;
var kc : Char;
    ruch, w, k : Integer;
    koniec, oznaczam : Boolean;
begin
    koniec:=false;
    ruch:=1;
    wypisz(false);
    while not koniec do begin
        write(ruch,'(',liczbaFlag,')',': ');
        ruch:=ruch+1;
        read(kc);
        oznaczam:=kc='#';
        if oznaczam then
            readln(kc,w)
        else
            readln(w);
        k:=ord(kc)-ord('a')+1;
        if (k in [1..SZEROKOSC]) and (w in [1..WYSOKOSC]) then
            if odsloniete[w,k] then
                writeln('To pole jest odsloniete')
            else if oznaczam then
                if oznaczone[w,k] then begin
                    liczbaFlag:=liczbaFlag+1;
                    oznaczone[w,k]:=false;
                    writeln('Skasowales oznaczenie')
                end else begin
                    liczbaFlag:=liczbaFlag-1;
                    oznaczone[w,k]:=true;
                    writeln('Oznaczyles pole')
                end
            else if oznaczone[w,k] then
                writeln('Pola oznaczonego nie mozna odslonic')
            else if mina[w,k] then begin
                writeln('Na tym polu jest mina. Przegrales !');
                koniec:=true
            end else begin
                odslon(w,k);
                if liczbaOdslonietych+LICZBA_MIN=WYSOKOSC*SZEROKOSC then begin
                    writeln('Odsloniles wszystkie pola bez min. Wygrales !');
                    koniec:=true
                end else
                    writeln('Odsloniles pole')
            end
        else
            writeln('Niepoprawny ruch');
        wypisz(koniec)
    end
end;
 
begin
    randomize;
    if SZEROKOSC > ord('z') - ord('a') + 1 then begin
        writeln('Plansza za szeroka');
        halt
    end;
    if LICZBA_MIN > (SZEROKOSC - 1) * (WYSOKOSC - 1) then begin
        writeln('Za duzo min');
        halt
    end;
    wypelnij;
    graj
end.

Rok 2007/2008, zadanie 2

Wprowadzenie

Często mamy potrzebę szybkiego przekazania komuś słownie numeru, np. kodu PIN, numeru telefonu, numeru konta.

Odczytanie lub zapamiętanie ciągu liter trwa znacznie krócej, niż tej samej długości ciągu cyfr dziesiętnych, o ile tylko ciąg liter wygląda jak słowo języka naturalnego. Cechę taką mają, między innymi, ciągi par liter, z których pierwsza jest spółgłoską a druga samogłoską, zakończone opcjonalną spółgłoską.

Jeśli, tworząc słowa tej postaci, ograniczymy się do liter alfabetu łacińskiego, będziemy mieli do dyspozycji 20 spółgłosek i 6 samogłosek.

Wymowa słów zawierających spółgłoski 'q', 'v' oraz 'x' może być trudna. Po ich odrzuceniu, do naszej dyspozycji pozostanie 17 spółgłosek:

b, c, d, f, g, h, j, k, l, m, n, p, r, s, t, w, z

i 6 samogłosek:

a, e, i, o, u, y

Możemy z nich utworzyć 17 * 6 = 102 pary spółgłoska-samogłoska. Z tego zbioru odrzucimy dwie pary, które trudno jest wypowiedzieć: "ji" oraz "jy". W rezultacie pozostanie nam 100 różnych par liter. Przy pomocy jednej pary możemy więc reprezentować ciąg dwóch cyfr dziesiętnych.

Chcąc ustalić numer reprezentowany przez zadane słowo, dzielimy je na grupy po dwie litery, z których pierwsza będzie spółgłoską, a druga samogłoską. Z każdej takiej grupy uzyskamy dwie cyfry numeru.

Dodatkowo, jeśli długość słowa jest nieparzysta, na końcu pozostanie nam jedna litera "nie do pary". Na jej podstawie wyznaczymy ostatnią cyfrę numeru.

Spółgłoskom przyporządkujemy, w kolejności alfabetycznej, liczby całkowite od 0 do 16, a samogłoskom liczby od 0 do 5.

Dla pary spółgłoska-samogłoska obliczymy wartość wyrażenia:

(numer spółgłoski) * 6 + (numer samogłoski)

Wartością będzie liczba od 0 do 101. Ponieważ ze zbioru dozwolonych par liter usunęliśmy "ji" oraz quot;jy", od uzyskanej z powyższego wzoru liczby:

odejmujemy 2, jeśli para liter w porządku leksykograficznym następuje po "jy"
odejmujemy 1, jeśli para liter w porządku leksykograficznym występuje pomiędzy "ji" a "jy"

Obliczona w ten sposób wartość wyznaczy dwie cyfry numeru. Pierwsza z nich będzie bardziej znaczącą cyfrą zapisu dziesiętnego tej wartości, a druga cyfra mniej znaczącą.

Jeśli na końcu słowa była litera "nie do pary", to musi to być spółgłoska z przedziału od 'b' do 'm'. Jej pozycja w ciągu spółgłosek wskaże ostatnią cyfrę numeru.

Przykład

Obliczymy numer reprezentowany przez słowo "beza". Dzielimy słowo na dwie pary liter: "be" i "za".

Ponieważ:

spółgłoska 'b' w ciągu spółgłosek ma numer 0
samogłoska 'e' w ciągu samogłosek ma numer 1
"be" w porządku leksykograficznym jest przed "ji"
0 * 6 + 1 = 1

pierwszymi dwiema cyframi bedzie "01".

Dla drugiej pary liter:

spółgłoska 'z' w ciągu spółgłosek ma numer 16
samogłoska 'a' w ciągu samogłosek ma numer 0
"za" w porządku leksykograficznym jest po "jy"
16 * 6 + 0 - 2 = 94

czyli kolejne dwie cyfry to 94.

Ustaliliśmy więc, że słowo beza reprezentuje numer 0194.

Gdybyśmy, dopisując na końcu słowa "beza" literę 'm' zrobili z niego bezam, uzyskalibyśmy reprezentację numeru 01949, gdyż 'm' w ciągu spółgłosek ma numer 9.

Polecenie

Napisz program, który dla danego jako parametr słowa, czyli ciągu liter, wypisze na wyjście odpowiadający mu numer - ciąg cyfr. Ten sam program, wywołany z argumentem będącym numerem, powinien wypisać na wyjście odpowiadające mu słowo.

Program powinien sensownie reagować na błędne dane.

Wskazówki

W rozwiązaniu zadania mogą się przydać standardowe funkcje Pascala:

ord(c): daje kod znaku c
chr(i): daje znak o kodzie i

oraz dostępne we Free Pascalu funkcje:

paramCount: daje liczbę argumentów, z jakimi program został wywołany
paramStr(i): daje napis przekazany jako i-ty argument programu

Rok 2007/2008, zadanie 2 - rozwiązanie

program wp07zad2;
 
var spolgloska : array [0 .. 16] of Char;
    samogloska : array [0 .. 5] of Char;
    wartosc : array ['a' .. 'z'] of Integer;
    pomijane1, pomijane2, i : Integer;
    s : String;
 
procedure piszLitery(x, y : Char);
var z : Integer;
begin
    z := ord(x) * 10 + ord(y) - ord('0') * 11;
    if z >= pomijane1 then
        z := z + 1;
    if z >= pomijane2 then
        z := z + 1;
    write(spolgloska[z div 6], samogloska[z mod 6])
end;
 
procedure piszCyfry(a, b : Char);
var z : Integer;
begin
    z := wartosc[a] * 6 + wartosc[b];
    if z > pomijane2 then
        z := z - 1;
    if z > pomijane1 then
        z := z - 1;
    write(z div 10, z mod 10)
end;
 
begin
    spolgloska := 'bcdfghjklmnprstwz';
    samogloska := 'aeiouy';
    for i := 0 to 16 do
        wartosc[spolgloska[i]] := i;
    for i := 0 to 5 do
        wartosc[samogloska[i]] := i;
    pomijane1 := wartosc['j'] * 6 + wartosc['i'];
    pomijane2 := wartosc['j'] * 6 + wartosc['y'];
    s := paramstr(1);
    if ('0' <= s[1]) and (s[1] <= '9') then begin
        for i := 1 to length(s) div 2 do
            piszLitery(s[2 * i - 1], s[2 * i]);
        if odd(length(s)) then
            write(spolgloska[ord(s[length(s)]) - ord('0')])
    end else begin
        for i := 1 to length(s) div 2 do
            piszCyfry(s[2 * i - 1], s[2 * i]);
        if odd(length(s)) then
            write(wartosc[s[length(s)]])
    end;
    writeln
end.

Załącznik	Wielkość
wp10zad2.pas	3.26 KB
wp09zad2.pas	4.67 KB
wp08zad2.pas	4.46 KB
wp07zad2.pas	1.4 KB

Informatyka MIMUW