Laboratorium

Laboratorium 1: Wprowadzenie do środowiska

Sprawy organizacyjne

Podstawowe informacje:

Laboratorium jest częścią zajęć ze Wstępu do programowania. Szczegółowe zasady zaliczania przedmiotu ogłasza wykładowca.
Obecność na zajęciach jest obowiązkowa.
Pierwszych pięć tygodni zajęć laboratoryjnych poświęcamy na zapoznanie się ze środowiskiem pracy programisty i opanowanie umiejętności programowania w języku C w stopniu podstawowym.
W dalszej części semestru studenci samodzielnie pracują nad rozwiązaniem czterech zadań zaliczeniowych. Za każde z nich można zdobyć maksymalnie 20 pkt. Zadanie czwarte jest zadaniem poprawkowym. Jego oceną można poprawić najsłabszą ocenę z zadań od 1 do 3. Łącznie można więc zdobyć maksymalnie 60 pkt. Wykładowca uwzględni je, wystawiając ostateczną ocenę z przedmiotu.
Pracujemy w środowisku systemu operacyjnego Linux kompilując programy za pomocą kompilatora gcc.

Czas trwania zajęć może nie wystarczyć do napisania programów zaliczeniowych. Studenci, którzy chcą programować w domu, mają dwie możliwości.

Najprostszym rozwiązaniem jest zdalna praca na koncie wydziałowym. Pod Windows można to robić za pomocą programu PuTTY. Przyda się też dołączony do niego program PSCP pozwalający na przesyłanie plików.
Osoby, które nie mają możliwości pracy zdalnej, np. z powodu braku dostępu do Internetu, mogą zainstalować kompilator gcc na swoim komputerze.

Nie gwarantujemy, że wszystko, co będziemy robili na zajęciach laboratoryjnych, da się powtórzyć pod Windows. Studenci, którzy chcą mieć w domu możliwie wierną kopię środowiska, w którym prowadzone są zajęcia, mogą rozważyć instalację Linuxa. Nie oznacza to konieczności rezygnacji z Windows - oba systemy mogą współistnieć na jednym komputerze. Uprzedzamy jednak - instalacja nowego systemu operacyjnego nie zawsze jest łatwa.

Rozpoczęcie i zakończenie pracy

Po uruchomieniu lub zresetowaniu komputera, na ekranie pojawi się menu, z którego wybieramy system operacyjny (Linux). Następnie, w oknie dialogowym wpisujemy login i hasło, by uzyskać dostęp do indywidualnego konta użytkownika. Konta te zostały założone dla każdego studenta przed rozpoczęciem zajęć. Loginy i hasła powinny być znane.

Pracę kończymy, wybierając z menu Programy polecenie Zakończ sesję i dalej Wyloguj, Uruchom ponownie lub Wyłącz.

Podstawowe pojęcia

Zaczniemy od wprowadzenia pojęć, którymi będziemy się posługiwali w dalszej części zajęć. Uprzedzamy: pewne kwestie będą przedstawiane w uproszczeniu.

plik

Plik to zestaw danych, zwykle stanowiący logiczną całość. Programy również przechowywane są w postaci plików.

system plików

System operacyjny organizuje pliki w system plików.

katalog

W systemie plików pliki grupowane są w katalogi.

drzewo katalogów

Katalogi tworzą strukturę drzewiastą nazywaną drzewem katalogów.

katalog główny

Korzeniem drzewa katalogów jest katalog główny.

katalog domowy

Każdy użytkownik ma w systemie plików swój własny katalog nazywany katalogiem domowym.

katalog aktualny

Podczas pracy z systemem plików dla każdego użytkownika jest określony katalog aktualny, czyli katalog, w którym użytkownik się znajduje.

ścieżka dostępu

Plik, z którego chcemy skorzystać wskazujemy, podając ścieżkę dostępu. Ścieżka składa się z ciągu nazw katalogów rozdzielonych znakami '/'. Jeśli ścieżka zaczyna się od '/', to opisuje drogę do pliku od katalogu głównego, wpp. od katalogu aktualnego.

W ścieżce dostępu może wystąpić '~' oznaczające katalog domowy użytkownika, '.' oznaczające katalog aktualny i '..' oznaczające katalog, w którym znajduje się katalog aktualny.

Operacje w systemie plików, posługiwanie się konsolą

Prosimy o otworzenie okna konsoli przez wybranie z menu Programy części Terminale i dalej Konsola.

Konsola to program wykonujący polecenia wprowadzane przez użytkownika. Przydadzą się nam:

ls

Wyświetla zawartość aktualnego katalogu. Z opcją -l podaje dodatkowe informacje o elementach katalogu, m. in. rozmiar pliku, prawa dostępu.

Polecenie ls można wywołać z argumentem wskazującym, o których elementach katalogu chcemy uzyskać informacje. W argumencie tym znak '?' zastępuje dowolny znak a '*' dowolny ciąg znaków. Np. polecenie ls -l *.c poda informacje o plikach, których nazwa ma rozszerzenie .c.

pwd

Podaje katalog aktualny.

cd nazwa

Zmienia katalog aktualny na katalog o podanej nazwie.

cp nazwa1 nazwa2

Tworzy kopię pliku nazwa1 nadając jej nazwę nazwa2.

mv nazwa1 nazwa2

Zmienia nazwę pliku nazwa1 na nazwa2.

rm nazwa

Usuwa plik nazwa.

mkdir nazwa

Tworzy katalog o nazwie nazwa.

rmdir nazwa

Usuwa katalog o nazwie nazwa.

touch nazwa

Zmienia datę ostatniej modyfikacji pliku o podanej nazwie. Jeśli plik nie istnieje, tworzy go.

cat nazwa

Wypisuje na wyjście zawartość pliku nazwa.

Argumentem polecenia cat może też być wiele nazw plików. Wypisywana jest wówczas zawartość każdego z nich.

echo napis

Wypisuje swój argument.

man polecenie

Podaje opis wskazanego polecenia.

Naciskanie strzałek w górę i w dół pozwala na przeglądanie historii wprowadzanych poleceń. Oszczędza to pracy, gdy chcemy ponownie wykonać polecenie. Pisanie poleceń ułatwia też klawisz tabulacji, którego naciśnięcie powoduje uzupełnienie nazwy pliku.

Prosimy o przećwiczenie opisanych powyżej poleceń.

Przygotowanie środowiska pracy programisty

Kompilacja to tworzenie programu wykonywalnego na podstawie kodu źródłowego. Narzędzie, które taką operację wykonuje, nazywamy kompilatorem. Na zajęciach laboratoryjnych ze Wstępu do programowania posługujemy się kompilatorem gcc.

Kompilator gcc będziemy uruchamiali w tzw. trybie wsadowym, np. za pomocą polecenia gcc nazwa.c, gdzie nazwa.c to nazwa pliku z kodem źródłowym.

Innym sposobem pracy z kompilatorem jest posłużenie się tzw. zintegrowanym środowiskiem programistycznym, będącym połączeniem kompilatora, edytora tekstu i innych narzędzi. Na razie nie będziemy z takich środowisk korzystali.

Praca programisty polega na wielokrotnym powtarzaniu cyklu "edycja kodu źródłowego - kompilacja programu - testowanie". By proces ten przebiegał sprawnie, warto otworzyć na ekranie dwa okna. Jednym z nich będzie okno konsoli, w którym programy kompilujemy i testujemy. W drugim oknie uruchamiamy edytor tekstu.

Na początek dobrym wyborem jest edytor KWrite, który można znaleźć w menu Programy i dalej Akcesoria, Edytory i KWrite. Ma on wszystkie niezbędne operacje edycyjne, podświetla składnię programów w C, potrafi numerować wiersze (trzeba wybrać odpowiednią opcję). Oczywiście w przyszłości można zmienić ten edytor na inny.

Edytowanie i kompilowanie programu

Prosimy o wpisanie w edytorze tekstu programu:

#include <stdio.h>
 
int main(void) {
    printf("Cześć !\n");
    return 0;
}

i zapisanie go w pliku o nazwie czesc.c.

Prosimy o jego samodzielne wpisanie a nie skopiowanie z okna przeglądarki do edytora tekstu.

Przechodzimy do okna konsoli i wpisujemy polecenia:

gcc czesc.c
ls -l

Jeśli nie było błędów, powstanie plik a.out. To program wykonywalny (w Linuxie pliki z programami wykonywalnymi nie mają rozszerzenia .exe).

Kompilator można też uruchomić poleceniem:

gcc czesc.c -o czesc

Program wykonywalny zostanie wówczas zapisany w pliku o nazwie czesc. Dalej będziemy zakładali taki właśnie sposób uruchomienia kompilatora.

Uruchamiamy program:

./czesc

Osobom, które dotąd korzystały z systemu Windows, dziwna może się wydawać konieczność poprzedzania nazwy programu znakami './' wskazującymi, że chodzi nam o program z katalogu aktualnego. Jest to spowodowane względami bezpieczeństwa. Gdyby system operacyjny domyślnie uruchamiał programy z aktualnego katalogu, byłoby możliwe podszycie się pod któryś z programów "standardowych" przez program pozostawiony w katalogu, w którym znalazł się użytkownik.

Zobaczymy, co się dzieje, gdy program jest błędny. Prosimy o usunięcie średnika po return 0 i ponowne skompilowanie programu. Dostaniemy komunikat:

czesc.c: In function ‘main’:
czesc.c:6:1: error: expected ‘;’ before ‘}’ token
 }
 ^

Poprawmy błąd i ponownie skompilujmy program.

Zadanie 1: Największa liczba błędów

Operacją edycyjną nazwiemy usunięcie jednego znaku lub wstawienie znaku do tekstu. Prosimy o znalezienie operacji edycyjnej na kodzie źródłowym zapisanym w pliku czesc.c, która spowoduje największą liczbę komunikatów o błędach.

Uruchamianie programu, standardowe wejście i wyjście

Prosimy o wpisanie poniższego programu:

#include <stdio.h>
 
int main(void) {
    int x;
 
    scanf("%d", &x);
    printf("%d\n", 2 * x);
    return 0;
}

i zapisanie go w pliku o nazwie dwarazy.c.

Kompilujemy program poleceniem:

gcc dwarazy.c -o dwarazy

i uruchamiamy za pomocą:

./dwarazy

a następnie wpisujemy jakąś liczbę całkowitą i naciskamy klawisz Enter.

Każdy program ma źródło danych nazywane standardowym wejściem i miejsce, w które kieruje wyniki, nazywane standardowym wyjściem. Domyślnie wejściem programu jest klawiatura a wyjściem okno konsoli.

Za pomocą znaku '>' można zmienić (przekierować) wyjście programu. Prosimy o uruchomienie:

./dwarazy > plik.txt

Wynik programu dwarazy trafi do pliku o nazwie plik.txt. Jego zawartość możemy obejrzeć za pomocą polecenia cat:

cat plik.txt

Przekierowanie za pomocą '>' wyniku programu do pliku, który już istnieje, spowoduje zamazanie jego zawartości. Jeśli chcemy tego uniknąć, możemy się posłużyć '>>', np.

./dwarazy >> plik.txt

Wynik programu zostanie wówczas dopisany na koniec pliku o podanej nazwie.

Wejście programu przekierowujemy za pomocą '<', np.

./dwarazy < plik.txt

W jednym poleceniu można też przekierować jednocześnie wejście i wyjście programu:

./dwarazy < plik.txt > inny.txt

Wyjście jednego programu można połączyć z wejściem innego za pomocą '|'. Prosimy o przetestowanie polecenia:

./dwarazy | ./dwarazy

a następnie:

./dwarazy | ./dwarazy | ./dwarazy | ./dwarazy

Prosimy też o uruchomienie:

echo 5 | ./dwarazy

Zadanie 2: Nieprawidłowy wynik programu

Jaka jest najmniejsza nieujemna liczba całkowita, dla której program dwarazy daje wynik niezgodny z oczekiwaniami ?

Praca samodzielna

Czas, który pozostanie do końca zajęć, można wykorzystać na pracę samodzielną. Zachęcamy zwłaszcza do zapoznania się z opcjami edytora KWrite i programu Midnight Commander, który można znaleźć w menu Programy, dalej Akcesoria i Menedżery plików, albo po prostu wpisać mc na konsoli.

Można też sprawdzić inne dostępne narzędzia, np. edytory tekstu. Być może znajdzie się tam taki, który będzie nam odpowiadał bardziej, niż KWrite. Warty polecenia jest np. edytor Kate.

Prosimy o uruchomienie przeglądarki internetowej, np. za pomocą polecenia Programy, Sieć, Przeglądarki WWW i dalej Iceweasel i zajrzenie na strony wazniak.mimuw.edu.pl, smurf.mimuw.edu.pl i moodle.mimuw.edu.pl.

Przypominamy o konieczności wylogowania się na zakończenie zajęć.

Laboratorium 2: Wprowadzenie do programowania w C

Planowanie obliczeń jako wprowadzenie do konstrukcji algorytmów

Rozważmy problem konstrukcji liczby przez ciąg dodawań (ang. addition chain) zaczynający się od liczby 1. Np. liczbę 6 możemy uzyskać wykonując:

1 + 1 -> 2
2 + 1 -> 3
3 + 1 -> 4
4 + 1 -> 5
5 + 1 -> 6

Powyższy zapis jest projektem. Do jego realizacji użyjemy pomocniczego programu plus.c:

#include <stdio.h>
 
int main(void) {
    int x, y;
 
    scanf("%d", &x);
    scanf("%d", &y);
    printf("%d\n", x + y);
    return 0;
}

Po jego kompilacji poleceniem gcc plus.c -o plus możemy zrealizować nasz projekt ciągiem poleceń:

echo 1 > jeden
cat jeden jeden  | ./plus > dwa
cat dwa jeden    | ./plus > trzy
cat trzy jeden   | ./plus > cztery
cat cztery jeden | ./plus > piec
cat piec jeden   | ./plus > szesc

Spróbujmy teraz znaleźć najkrótszy ciąg dodawań, w wyniku którego otrzymamy 6.

Oto przykładowe rozwiązanie:

cat jeden jeden | ./plus > dwa
cat dwa jeden   | ./plus > trzy
cat trzy trzy   | ./plus > szesc

Zadanie: Najkrótszy ciąg dodawań (ang. shortest addition chain)

Znajdź najkrótszy ciąg dodawań, który da w wyniku liczbę 15.

Wprowadzenie do programowania w C

Prosimy o wpisanie poniższego programu:

#include <stdio.h>
 
int main(void) {
    int jeden, dwa, trzy, szesc;
 
    jeden = 1;
    dwa = jeden + jeden;
    trzy = dwa + jeden;
    szesc = trzy + trzy;
    printf("%d\n", szesc);
    return 0;
}

i zapamiętanie go w pliku o nazwie dodawania.c.

Ten program jest zapisem rozwiązania problemu ciągu dodawań dającego wynik 6. W stosunku do poprzednich programów, nową konstrukcją jest tu przypisanie =.

W programie:

#include <stdio.h>
 
int main(void) {
    double a, b, c, x;
 
    scanf("%lf%lf%lf%lf", &a, &b, &c, &x);
    printf("%f\n", a * x * x + b * x + c);
    return 0;
}

nowymi konstrukcjami są:

typ double,
użycie funkcji scanf do wczytania wielu wartości.

Prosimy o przetestowanie programu, w tym na danych, które nie są całkowite (uwaga: przed częścią ułamkową umieszczamy kropkę, a nie przecinek).

Zmieniamy wywołanie printf na:

    printf("%15.10f\n", a * x * x + b * x + c);

i prosimy o przetestowanie.

Zapis 15.10 wskazuje, że funkcja printf ma wypisać wartość wyrażenia w 15 znakach, 10 z nich przeznaczając na część ułamkową.

W programie:

#include <stdio.h>
 
int main(void) {
    int x, y;
 
    scanf("%d", &x);
    scanf("%d", &y);
    if (x > y) {
        printf("%d\n", x);
    } else {
        printf("%d\n", y);
    }
    return 0;
}

nowym elementem jest instrukcja warunkowa if (...) ... else ....

W programie:

#include <stdio.h>
 
int main(void) {
    int x, ile;
 
    ile = 0;
    while (scanf("%d", &x) > 0 && x != 0) {
        ++ile;
    }
    printf("Było %d\n", ile);
    return 0;
}

nowym elementem jest pętla while (...) ..., sprawdzenie wyniku funkcji scanf i koniunkcja &&.

Zwracamy uwagę na konieczność inicjalizacji zmiennej ile. Bez tego miałaby wartość nieokreśloną.

Laboratorium 3: Samodzielne programowanie - tydzień pierwszy

Zaczynamy blok trzech zajęć poświęconych na samodzielne programowanie. Rozwiązania zadań należy zaprezentować prowadzącemu laboratorium. Ich oceny nie będą jednak miały wpływu na ostateczną ocenę z przedmiotu.

Tam, gdzie to możliwe, pracujemy nad programem metodą kolejnych rozszerzeń - wybieramy podproblem, piszemy jego kompletne, działające rozwiązanie i dopiero po jego przetestowaniu przechodzimy do pracy nad problemem szerszym.

Zadanie 1: Suma wyrazów ciągu arytmetycznego

Napisz program, który wczyta z wejścia dwie liczby rzeczywiste s i k oraz liczbę całkowitą n i wypisze na wyjście sumę n początkowych wyrazów ciągu arytmetycznego, którego pierwszym wyrazem jest s a krok wynosi k.

Zadanie 2: Mediana z trzech liczb

Napisz program, który wczyta z wejścia trzy liczby całkowite i wypisze na wyjście ich medianę (wartość środkową).

Zadanie 3: Choinka

Napisz program, który wczyta z wejścia liczbę n i wypisze na wyjście tekst składający się ze spacji i gwiazdek, przedstawiający choinkę o wysokości n mającą pień 3x3. Np. dla n = 6 program powinien wypisać:

     *
    ***
   *****
  *******
 *********
***********
    ***
    ***
    ***

Sugerujemy pracę z zastosowaniem "metody kolejnych rozszerzeń", pisząc kolejno:

program wypisujący wiersz zawierający 10 gwiazdek
program wczytujący z wejścia liczbę n i wypisujący wiersz zawierający n gwiazdek
program wczytujący z wejścia liczbę n i wypisujący n wierszy, w każdym po n gwiazdek (czyli kwadrat z gwiazdek)
program wczytujący z wejścia liczbę n i wypisujący trójkąt pod przekątną kwadratu z punktu (3), biegnącą od lewego górnego do prawego dolnego rogu
jak w punkcie (4), ale przekątna od lewego dolnego do prawego górnego rogu
program wczytujący liczbę n i wypisujący choinkę bez pnia, czyli sklejenie trójkątów z punktów (4) i (5)
pełną wersję zadania - punkt (6) z dodanym pniem

Jeśli uda się rozwiązać zadanie o choince w podstawowej wersji, można rozszerzyć program np. przez dodanie "ramki" dookoła obrazka choinki lub zmianę jej kształtu.

Laboratorium 4: Samodzielne programowanie - tydzień drugi

Do rozwiązania niektórych problemów programistycznych potrzebny jest tzw. generator liczb pseudolosowych, czyli narzędzie generujące "losowo wyglądający" ciąg liczb. W C mamy do dyspozycji, zadeklarowane w pliku nagłówkowym stdlib.h:

funkcję srand(), z parametrem typu unsigned int, której wywołanie powinno poprzedzać pierwsze użycie generatora liczb pseudolosowych w programie,
funkcję rand(), za pomocą której pobieramy od generatora kolejne pseudolosowe liczby całkowite od 0 do RAND_MAX.

Funkcja srand() ustala wartość początkową generowanego ciągu liczb pseudolosowych. Zwykle przekazujemy jej jako argument wynik funkcji time(), zadeklarowanej w pliku nagłówkowym time.h, wywołanej z argumentem NULL. Wielokrotne używanie jej w programie jest poważnym błędem. Gdyby kolejne wywołania nastąpiły krótko po sobie, generator liczb pseudolosowych byłby inicjowany tą samą wartością a więc po każdym wywołaniu srand() funkcja rand() dawałaby identyczny wynik. Zapiszmy np. program:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N_PROB 5
 
int main(void) {
    int i;
 
    srand((unsigned int) time(NULL));
    for (i = 0; i < N_PROB; ++i) {
        if ((double) rand() / (RAND_MAX + 1.0) < 0.5) {
            printf("orzeł\n");
        } else {
            printf("reszka\n");
        }
    }
    return 0;
}

i porównajmy jego wyniki z wynikami programu uzyskanego po przeniesieniu wywołania srand do wnętrza pętli.

Zadanie 1: Przybliżenie π metodą Monte Carlo

Przybliżenie π można obliczyć, losując ciąg punktów płaszczyzny znajdujących się w kwadracie o rozmiarze 1 na 1 i zliczając, ile z nich trafi we wpisaną w ten kwadrat ćwiartkę koła o promieniu 1. Na podstawie stosunku do liczby wszystkich punktów, liczby tych, które trafią w ćwiartkę koła, szacujemy stosunek pól obu figur i w ten sposób ustalamy przybliżenie liczby π.

Napisz program, który zrealizuje ten algorytm. Program powinien podać przybliżenia π uzyskane po N losowaniach punktów, dla N będących potęgami 10, aż do N=100000000 (sto milionów).

Proponujemy zacząć od wersji programu wykonującej obliczenie dla jednej, ustalonej liczby losowań (np. milion), a dopiero później przejść do rozwiązania właściwego zadania.

Zadanie 2: Histogram dla ciągu rzutów parą kostek

Napisz program, który zasymuluje ciąg 10000 rzutów parą kostek i przedstawi wyniki w formie histogramu częstości występowania poszczególnych sum oczek. Histogram, narysowany za pomocą spacji i gwiazdek, powinien mieć "pionowe" słupki. Słupek odpowiadający najczęściej występującej sumie oczek ma mieć 20 wierszy wysokości.

Pod każdym słupkiem należy wypisać odpowiadającą mu wartość procentową.

Proponujemy zacząć od wersji podającej wynik losowania w formie liczbowej, następnie jako histogram o słupkach "poziomych" i dopiero potem przejść do wersji ostatecznej.

Zadanie 3: Rozkład liczby całkowitej na iloczyn liczb pierwszych

Napisz program, który będzie wczytywał z wejścia liczby całkowite i wypisywał ich rozkłady na iloczyny liczb pierwszych. Np. dla liczby 5432 program ma wypisać:

5432 = 2 * 2 * 2 * 7 * 97

Program powinien zakończyć pracę, gdy kolejna liczba wczytana z wejścia będzie mniejsza niż 2.

Laboratorium 5: Samodzielne programowanie - tydzień trzeci

Zadanie 1: Problem Collatza/Ulama

Rozważamy ciągi liczb naturalnych rozpoczynające się od zadanej liczby, w których następnym wyrazem po wyrazie x jest x / 2, jeśli x jest parzyste, a 3 * x + 1 wpp.

Napisz program, który sprawdzi, dla jakiej liczby rozpoczynającej ciąg, nie przekraczającej 10000, wykonamy najwięcej kroków, zanim osiągniemy wartość 1.

Uwaga - choć 10000 mieści się w zakresie wartości typu int, licząc wyrazy ciągu Collatza możemy ten zakres przekroczyć. Zmienne, na których będą przechowywane wyrazy tego ciągu, powinny więc mieć typ long int.

Zadanie 2: Lotto

Napisz program, który przeprowadzi symulację losowania Lotto (wybieramy 6 liczb z 49) i wypełnienia 1000 kuponów, a następnie poinformuje, ile razy trafiono 3, ile razy 4 itd.

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

Laboratorium 7: Praca nad zadaniem zaliczeniowym 1. Postscript, rekursja

Posłużymy się GhostScriptem jak kalkulatorem, by przećwiczyć postfiksowy zapis wyrażeń. Przy okazji przedstawimy też podzbiór Postscriptu umożliwiający użycie go jak "prawdziwego" języka programowania.

Prosimy o uruchomienie programu Ghostscript poleceniem gs. Otworzy się okno z graficznym podglądem strony, a na konsoli będziemy mogli wprowadzać polecenia. Kończąc pracę, wpiszemy quit.

Zaczniemy od:

0 0 moveto 595 842 lineto stroke

rysującego przekątną strony, by pokazać, że interpreter działa.

Po tym wprowadzimy polecenie:

0 842 595 0 moveto lineto stroke

które narysuje drugą przekątną. Wyjaśnijmy, co tu się stało.

Prosimy o wpisanie ciągu liczb:

Po wprowadzeniu każdej z nich, w tekście zachęty wyświetli się informacja o liczbie wartości na stosie. Po ostatniej liczbie wprowadzimy polecenie:

stack

które wyświetli aktualną zawartość stosu, nie zmieniając jej.

Następnie wpiszemy:

add sub mul div =

i ręcznie prześledzimy ciąg obliczeń. = zdejmuje i wyświetla wartość z czubka stosu a pozostałe polecenia wykonują odpowiednie operacje arytmetyczne.

Prosimy o przetłumaczenie jakiegoś przykładu wyrażenia w zapisie infiksowym (z nawiasami) na zapis posfiksowy i sprawdzenie w Ghostscripcie, czy wynik wychodzi zgodny z oczekiwaniami.

Następnie przechodzimy do prezentacji PostScriptu jako języka programowania. Zaczniemy od pętli for:

1 2 10 {=} for

Polecenie for ma cztery argumenty - wartość startową, krok, wartość końcową i kod treści pętli. Treść pętli jest wykonywana z wartościa "zmiennej sterującej" na czubku stosu. Powyższy przykład wypisze więc nieparzyste liczby od 1 to 10.

By to przećwiczyć, jeszcze jeden przykład, liczący silnię z 10:

1 2 1 10 {mul} for =

Pętle oczywiście można zagnieżdżać. Oto przykład rysujący odcinki między parami punktów na dolnej i górnej krawędzi strony:

0 35 595 {
  0 35 595 {0 moveto dup 842 lineto stroke} for
  pop
} for

Przed jego wykonaniem warto oczyścić okno podglądu strony poprzez showpage.

W przykładzie mamy dwa nowe polecenia: dup powielające wartość na czubku stosu i pop zdejmujące wartość z czubka stosu.

Kolejny przykład wypisuje tekstowo choinkę (bez pnia). Mamy tu prostszą formę pętli - "repeat":

0 1 20 {
  dup 20 exch sub {( ) print} repeat {(**) print} repeat (*\n) print
} for

repeat wykonuje podany na czubku stosu kod liczbę razy wskazaną wartością pod czubkiem stosu. Mamy tu też użycie polecenia exch zamieniającego miejscami dwie wartości z czubka stosu i print wypisującego napis.

W kolejnym przykładzie pokażemy, jak można definiować odpowiedniki Pascalowych procedur/funkcji:

/Pionowa {dup 0 moveto 842 lineto stroke} def

/Pionowa jest tu nazwą, którą wiążemy z podanym kodem za pomocą polecenia def. Dostajemy w ten sposób procedurę, w tym przypadku jednoparametrową, rysującą dla zadanej współrzędnej x pionową kreskę przez całą stronę. Możemy ją wywołać np. poleceniem:

100 Pionowa

albo:

200 5 400 {Pionowa} for

Kolejny przykład, tym razem z funkcją:

/Silnia {dup 1 gt {dup 1 sub Silnia mul} if} def

Jest tu polecenie gt sprawdzające, czy między dwiema wartościami zachodzi relacja >, oraz if dostające na czubku stosu kod i wykonujące go, jeśli pod czubkiem stosu jest wartość logiczna "prawda".

Przykład uruchomimy poleceniem:

5 Silnia =

Jeszcze jedna funkcja rekurencyjna:

/Fib {dup 1 gt {dup 1 sub Fib exch 2 sub Fib add} if} def

uruchamiana np. tak:

0 1 10 {Fib =} for

Żonglowanie wartościami na stosie bywa niewygodne i łatwo się pomylić. Alternatywą jest posłużenie się zmiennymi, którym nadajemy wartość znanym już polecenien def. Wpiszmy:

/NWD {
  /a exch def
  /b exch def
  {a b eq {exit} if a b sub dup 0 gt {/a} {/b} ifelse exch abs def} loop
  a
} def

i przetestujmy:

234 432 NWD =

W tym przykładzie jest kilka nowych poleceń - eq badające równość, ifelse wykonujące jeden z dwóch fragmentów kodu w zależności od prawdziwości warunku, abs liczące wartość bezwzględną, loop realizujące potencjalnie nieskończoną pętlę i exit przerywające pętlę.

Następny przykład rysuje odcinki od środka strony do punktów na okręgu:

/szerokosc 595 def
/wysokosc 842 def
/NaSrodek {szerokosc 2 div wysokosc 2 div moveto} def
0 5 360 {dup sin 250 mul exch cos 250 mul NaSrodek rlineto} for stroke

Tym razem za pomocą def zdefiniowaliśmy nie tylko pomocniczą procedurę, ale i dwie stałe. Korzystamy tu też z sin i cos.

W kolejnym przykładzie - implementacji sita Eratostenesa - posłużymy się tablicą:

/n 100 def
/t n 1 add array def
2 1 n sqrt {dup dup mul exch n {t exch 1 put} for} for
2 1 n {dup t exch get 1 ne {=} {pop} ifelse} for

array tworzy tablicę o rozmiarze podanym na czubku stosu. Tablice w PostScripcie są indeksowane od 0, a wartością początkową poszczególnych elementów jest null. Wartość z tablicy odczytujemy za pomocą get, które na czubku stosu dostaje indeks a pod nim tablicę. Zapis do tablicy realizuje put z trzema argumentami (w kolejności od czubka stosu): wartość, indeks i tablica.

Mamy tu też sqrt, czyli pierwiastek kwadratowy i ne sprawdzające, czy wartości są różne.

W ostatnim przykładzie skorzystamy z generatora liczb pseudolosowych i wprowadzimy do rysunku kolor:

/Losowa {rand 2 31 exp div} def
/LosowyPunkt {Losowa szerokosc mul Losowa wysokosc mul} def
10 setlinewidth
1000 {
  Losowa Losowa Losowa setrgbcolor
  LosowyPunkt moveto LosowyPunkt lineto stroke
} repeat

rand daje losową liczbę całkowitą od 0 do 2^31-1, exp to potęgowanie, setlinewidth ustala szerokość kreski w punktach (domyślnie jest 1) a setrgbcolor wskazuje aktualny kolor na podstawie trzech liczb rzeczywistych z przedziału [0 .. 1] określających składową czerwoną, zieloną i niebieską.

Przejdźmy do kolejnego programu przykładowego (cesaro.pas):

program cesaro;
 
const
    SZEROKOSC_STRONY = 595;
    WYSOKOSC_STRONY = 842;
    MARGINES = 5;
    DLUGOSC_BOKU = SZEROKOSC_STRONY - 2 * MARGINES;
    ZMIANA_KATA = PI / 2.1;
    PODZIAL_DLUGOSCI = 2 * (1 + cos(ZMIANA_KATA));
    N = 5;
 
procedure r(dlugosc, kat : Real; krok : Integer);
begin
    if krok = N then
        writeln(dlugosc * cos(kat), ' ', dlugosc * sin(kat), ' rlineto')
    else begin
        r(dlugosc / PODZIAL_DLUGOSCI, kat, krok + 1);
        r(dlugosc / PODZIAL_DLUGOSCI, kat + ZMIANA_KATA, krok + 1);
        r(dlugosc / PODZIAL_DLUGOSCI, kat - ZMIANA_KATA, krok + 1);
        r(dlugosc / PODZIAL_DLUGOSCI, kat, krok + 1)
    end
end;
 
begin
    writeln('%!PS');
    {writeln('[2] 0 setdash');}
    writeln(MARGINES, ' ', (WYSOKOSC_STRONY - DLUGOSC_BOKU) / 2, ' moveto');
    r(DLUGOSC_BOKU, 0, 0);
    r(DLUGOSC_BOKU, PI / 2, 0);
    r(DLUGOSC_BOKU, PI, 0);
    r(DLUGOSC_BOKU, 3 * PI / 2, 0);
    writeln('stroke showpage')
end.

Kompilujemy go i uruchamiamy, przekierowując wynik do pliku wynik.ps, a następnie otwieramy ten plik programem Ghostscriptem.

Program ten rysuje fraktal Cesaro. Zmieniając wartość stałej N na 0, 1, 2 itd. powinniśmy zrozumieć rekurencyjny proces budowy krzywej. Wartość stałej "ZMIANA_KATA" można modyfikować w zakresie [O, π / 2]. W szczególności, dla π / 3 dostaniemy "cztery-trzecie" płatka (a właściwie antypłatka) Kocha.

Przykład korzysta z polecenia rlineto ("r" od "relative"), które jest odpowiednikiem lineto, ale z argumentami wskazującymi wektor, a nie współrzędne docelowe. Do kompletu w Postscripcie jest też rmoveto.

Dodatkowo, korzystamy tu też z faktu, że w skład rysowanej "ścieżki" może wchodzić więcej niż jeden odcinek. Kolejne polecenia lineto czy rlineto rysują odcinki od miejsca, w którym zakończył się odcinek poprzedni.

Odkomentujmy instrukcję writeln('[2] 0 setdash'). Powoduje ona, że linia rysowania staje się przerywana. Pierwszy argument to tablica określająca cykliczną sekwencję kresek i przerw. W tym wypadku będzie kreska długości dwóch punktów, następnie dwa punkty przerwy itd. Drugi argument mówi, w którym miejscu tej sekwencji zaczynamy - 0 oznacza, że od początku.

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

Laboratorium 9: Praca nad zadaniem zaliczeniowym 2. Reprezentacja liczb

Ćwiczenie 1

Napisz program, który zmiennej typu Real nada wartość 0.1, a następnie pomnoży ją przez 21 i odejmie 2. W rezultacie na zmiennej powinno się znów znaleźć 0.1, co sprawdzimy wypisując jej wartość. By uniknąć trudności z interpretacją notacji wykładniczej, użyjemy modyfikatora : 40 : 15 operacji writeln:

program jednadziesiata1;
 
var x : Real;
 
begin
    x := 0.1;
    x := 21 * x - 2;
    writeln(x : 40 : 15)
end.

Po kompilacji i uruchomieniu programu dostaniemy wynik:

                       0.100000000000000

czyli dokładnie to, czego się spodziewaliśmy.

Prosimy o dopisanie do programu jeszcze jednej operacji writeln(), wypisującej wynik porównania wartości zmiennej x z 0.1:

program jednadziesiata2;
 
var x : Real;
 
begin
    x := 0.1;
    x := 21 * x - 2;
    writeln(x = 0.1);
    writeln(x : 40 : 15)
end.

Otrzymamy następujący wynik:

FALSE
                       0.100000000000000

Okazuje się więc, że wynik obliczenia nie jest równy wartości 0.1, choć jest jej tak bliski, że na 15 miejscach po kropce nie widać różnicy.

Zobaczmy, jakie są konsekwencje tej różnicy. Instrukcję aktualizującą wartość zmiennej x umieśćmy w pętli for wykonującej 30 obrotów (writeln() wypisujące wartość logiczną można już usunąć):

program jednadziesiata3;
 
var x : Real;
    i : Integer;
 
begin
    x := 0.1;
    for i := 1 to 30 do
        x := 21 * x - 2;
    writeln(x : 40 : 15)
end.

W wyniku dostaniemy coś, co jednej dziesiątej nie przypomina ani trochę:

 25760784001056300000000.000000000000000

By dokładnie zobaczyć, co się dzieje, przenieśmy writeln() do pętli:

program jednadziesiata4;
 
var x : Real;
    i : Integer;
 
begin
    x := 0.1;
    for i := 1 to 30 do begin
        x := 21 * x - 2;
        writeln(x : 40 : 15)
    end
end.

Dostaniemy wynik:

                       0.100000000000000
                       0.100000000000002
                       0.100000000000051
                       0.100000000001080
                       0.100000000022671
                       0.100000000476098
                       0.100000009998050
                       0.100000209959047
                       0.100004409139979
                       0.100092591939550
                       0.101944430730551
                       0.140833045341563
                       0.957493952172825
                      18.107372995629300
                     378.254832908216000
                    7941.351491072530000
                  166766.381312523000000
                 3502092.007562990000000
                73543930.158822700000000
              1544422531.335280000000000
             32432873156.040800000000000
            681090336274.857000000000000
          14302897061770.000000000000000
         300360838297168.000000000000000
        6307577604240520.000000000000000
      132459129689051000.000000000000000
     2781641723470070000.000000000000000
    58414476192871500000.000000000000000
  1226704000050300000000.000000000000000
 25760784001056300000000.000000000000000

Mamy więc wyjaśnienie zagadki. W każdym kolejnym kroku dostajemy błąd bezwględny 21 razy większy od poprzedniego. W rezultacie już po kilkunastu obrotach pętli na zmiennej x znajdzie się wartość zupełnie bezsensowna.

Ćwiczenie 2

Rozważmy następujący program:

program jedynka;
 
var x : array [1 .. 8] of Real;
    i, j : Integer;
 
begin
    for i := 1 to 8 do
        x[i] := 1.0;
    for j := 1 to 20 do begin
        x[1] := x[1] - 0.1; x[1] := x[1] - 0.8;
        x[2] := x[2] - 0.2; x[2] := x[2] - 0.7;
        x[3] := x[3] - 0.3; x[3] := x[3] - 0.6;
        x[4] := x[4] - 0.4; x[4] := x[4] - 0.5;
        x[5] := x[5] - 0.5; x[5] := x[5] - 0.4;
        x[6] := x[6] - 0.6; x[6] := x[6] - 0.3;
        x[7] := x[7] - 0.7; x[7] := x[7] - 0.2;
        x[8] := x[8] - 0.8; x[8] := x[8] - 0.1;
        for i := 1 to 8 do
            x[i] := 10 * x[i]
    end;
    for i := 1 to 8 do
        writeln(x[i] : 40 : 15)
end.

Łatwo zauważyć, że kolejne obroty "dużej" pętli for powinny pozostawić na każdej z ośmiu pozycji w tablicy x zastaną tam 1.

Uruchamiamy program. Wynikiem będzie:

                    2468.162276944790000
                    4935.324553889580000
                   -4933.324553889580000
                   -2466.162276944790000
                       1.000000000000000
                    2468.162276944790000
                   -1232.581138472400000
                       1.000000000000000

Widać, jak nieprzewidywalne mogą być wyniki obliczeń na danych w reprezentacji zmiennopozycyjnej. W zależności od doboru wartości odejmowanych od elementów tablicy, dostajemy sześć różnych wyników.

Powyższe ćwiczenia pokazują, że specyfika arytmetyki zmiennopozycyjnej ma wpływ na nasze programy nie tylko wtedy, gdy operujemy na wartościach bardzo małych, bardzo dużych, lub wykonujemy złożone obliczenia.

Podkreślamy, że zademonstrowane tu problemy nie są związane z konkretnym językiem programowania, ale z reprezentacją liczb. Po przetłumaczeniu przykładów z Pascala na C++ czy Javę zobaczylibyśmy to samo zjawisko.

Ćwiczenie 3

Posłużymy się programem pomocniczym, demonstrującym reprezentację binarną liczb. Oto treść (reprezentacja.pas):

program reprezentacja;
 
const
    NAJWIEKSZY_ROZMIAR = 256;
    LICZBA_TYPOW = 14;
    NAZWA : array [1 .. LICZBA_TYPOW] of String = (
        'byte',          'cardinal',       'double',          'extended',
        'int64',         'integer',        'longint',         'longword',
        'qword',         'real',           'shortint',        'single',
        'smallint',      'word');
    ROZMIAR : array [1 .. LICZBA_TYPOW] of Integer = (
        SizeOf(Byte),     SizeOf(Cardinal), SizeOf(Double),   SizeOf(Extended),
        SizeOf(Int64),    SizeOf(Integer),  SizeOf(LongInt),  SizeOf(Longword),
        SizeOf(QWord),    SizeOf(Real),     SizeOf(ShortInt), SizeOf(Single),
        SizeOf(SmallInt), SizeOf(Word));
 
var wartosc : record case Integer of
        1  : (byte          : Byte);
        2  : (cardinal      : Cardinal);
        3  : (double        : Double);
        4  : (extended      : Extended);
        5  : (int64         : Int64);
        6  : (integer       : Integer);
        7  : (longint       : LongInt);
        8  : (longword      : LongWord);
        9  : (qword         : QWord);
        10 : (real          : Real);
        11 : (shortint      : ShortInt);
        12 : (single        : Single);
        13 : (smallint      : SmallInt);
        14 : (word          : Word);
        15 : (bajtyWartosci : array [1 .. NAJWIEKSZY_ROZMIAR] of Byte)
    end;
    i, j, l, s, p : Integer;
    x             : Byte;
    argument      : String;
 
begin
    if paramCount <> 1 then
        writeln('Program wywolujemy z jednym argumentem - nazwa typu')
    else begin
        argument := lowerCase(paramStr(1));
        l := 1;
        p := LICZBA_TYPOW;
        while l < p do begin
            s := (l + p) div 2;
            if argument <= NAZWA[s] then
                p := s
            else
                l := s + 1
        end;
        if argument <> NAZWA[l] then
            writeln('Nieprawidlowa nazwa typu: "', paramStr(1), '"')
        else begin
            case l of
                1  : readln(wartosc.byte);
                2  : readln(wartosc.cardinal);
                3  : readln(wartosc.double);
                4  : readln(wartosc.extended);
                5  : readln(wartosc.int64);
                6  : readln(wartosc.integer);
                7  : readln(wartosc.longint);
                8  : readln(wartosc.longword);
                9  : readln(wartosc.qword);
                10 : readln(wartosc.real);
                11 : readln(wartosc.shortint);
                12 : readln(wartosc.single);
                13 : readln(wartosc.smallint);
                14 : readln(wartosc.word);
            end;
            for i := 1 to ROZMIAR[l] do begin
                x := wartosc.bajtyWartosci[i];
                for j := 1 to 8 do begin
                    write(x div 128);
                    x := 2 * (x mod 128)
                end;
                write(' ')
            end;
            writeln
        end
    end
end.

Program ten wywołujemy z jednym argumentem - nazwą wbudowanego typu, a następnie podajemy na standardowym wejściu tekstowy zapis wartości tego typu. Program wypisuje reprezentację tej wartości w postaci ciągu bajtów, z których każdy rozpisany jest na poszczególne bity. Bity są uporządkowane w kolejności od najbardziej znaczących, a bajty w takiej, jaką mają w pamięci.

Program rozpoznaje czternaście typów, w tym dziesięć całkowitych:

Byte
Cardinal
Int64
Integer
LongInt
LongWord
QWord
ShortInt
SmallInt
Word

i cztery rzeczywiste:

Double
Extended
Real
Single

By dostać się do poszczególnych bajtów reprezentacji wartości liczbowych, program korzysta z rekordu z wariantami bez pola znacznikowego.

Zacznijmy od ustalenia, czy komputer, na którym pracujemy, jest "małym indianinem" czy "dużym indianinem" a więc czy bajty wartości liczbowych są uporządkowane w pamięci w kolejności od najmniej znaczących czy od najbardziej znaczących.

Odpowiedź:

Jeśli pracujemy na komputerze o procesorze z rodziny x86 to od najmniej znaczących.

Następnie zbadajmy reprezentację wartości typów Byte, Word i Integer.

Rozpoznanie sposobu reprezentacji wartości typu Real jest trudniejsze. Mamy tu do czynienia z implementacją standardu IEEE 754:

wartość typu Real jest zapisana na 64 bitach
najbardziej znaczący bit najbardziej znaczącego (czyli ostatniego) bajtu to bit znaku
11 kolejnych bitów zawiera cechę, ale nie w U2, tylko jako liczbę nieujemną powstałą po dodaniu do prawdziwej wartości liczby 1023 - np. cecha o wartości 1 jest reprezentowana przez 1024
pozostałe 52 bity to mantysa znormalizowana do przedziału [1, 2), przy czym najbardziej znaczący jej bit, ten przed kropką binarną, jest ukryty.

Laboratorium 10: Omówienie zadania zaliczeniowego 3

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

Rok 2010/2011, zadanie 3

Wprowadzenie

Gra Hurra jest rozgrywana za pomocą białych i czarnych pionów na kwadratowej planszy składającej się z 8 rzędów po 8 pól w każdym. Na polu planszy na raz może się znajdować co najwyżej jeden pion.

W grze bierze udział dwóch graczy, nazywanych dalej Białym i Czarnym, od koloru pionów do nich należących. Gracze siedzą po przeciwnych stronach planszy.

Przed rozpoczęciem gry ustala się, ile każdy z graczy będzie miał pionów i jakie będą ich początkowe pozycje na planszy. Początkową pozycją piona białego nie może być pole należące do rzędu, przy którym siedzi gracz Czarny a początkową pozycją piona czarnego nie może być pole należące do rzędu, przy którym siedzi gracz Biały.

Gracze wykonują na przemian po jednym ruchu pionem, który wybierają spośród znajdujących się na planszy własnych pionów. Dozwolonymi ruchami są:

przesunięcie piona o jedno pole "do przodu", czyli w kierunku rzędu, przy którym siedzi przeciwnik. Ruch ten jest możliwy jeśli pole, na którym ma się znaleźć przesuwany pion, jest puste.
bicie piona przeciwnika znajdującego się na polu "o jeden do przodu po skosie" względem pola, z którego wykonujemy ruch. Zbity pion jest usuwany z planszy.

Jako pierwszy ruch wykonuje gracz Biały.

Gracz, który postawi swojego piona w rzędzie, przy którym siedzi przeciwnik, wygrywa. Jeśli gracz, który w danej chwili ma wykonać ruch, nie ma żadnego legalnego ruchu, jego przeciwnik wygrywa.

Obserwacje

Gra Hurra nigdy nie kończy się remisem.
Każdy z graczy przesuwa swoje piony tylko w jednym kierunku a ruchy są obowiązkowe, więc liczba ruchów podczas gry jest ograniczona.
Łączna liczba pionów obu graczy nie może być większa niż rozmiar planszy.
Ruchy pionów w Hurra są takie, jak w szachach, ale nie ma bicia w przelocie ani prawa wykonania pierwszego ruchu pionem o dwa pola do przodu.

Polecenie

Napisz program, który wczyta z wejścia opis początkowego ustawienia pionów dla gry Hurra i wskaże ruchy gracza Białego prowadzące do jego zwycięstwa, przy bezbłędnej grze obu graczy.

Format danych

Dane programu to 8 wierszy tekstu, po 8 znaków w każdym. Poszczególne wiersze reprezentują zawartość kolejnych rzędów planszy. Pierwszy wiersz odpowiada rzędowi, przy którym siedzi gracz Czarny, ostatni rzędowi, przy którym siedzi gracz Biały.

Znaki wierszy tekstu wejściowego opisują zawartość poszczególnych pól:

'-' to pole puste
'b' to pole, na którym jest pion biały
'c' to pole, na którym jest pion czarny

Format wyniku

Wynik programu to opis planszy wczytanej z wejścia, w którym znaki 'b' reprezentujące piony białe zastąpiono liczbami od 0 do 7. W binarnym zapisie wartości tej liczby na trzech bitach ABC, A to bit najbardziej znaczący a C to bit najmniej znaczący, poszczególne bity odpowiadają ruchom pionem:

bit A to bicie "w lewo"
bit B to ruch "do przodu"
bit C to bicie "w prawo".

Bit odpowiadający danemu ruchowi ma wartość 1 gdy ruch ten jest legalny i prowadzi do zwycięstwa gracza Białego.

Przykłady

Dla danych:

--c-ccc-
bbbbbbbb
--------
--------
--------
--------
--------
--------

program powinien wypisać:

--c-ccc-
23071546
--------
--------
--------
--------
--------
--------
Dla danych:

--------
-c------
--------
--c-----
-b------
b------c
--------
------b-

program powinien wypisać:

--------
-c------
--------
--c-----
-1------
0------c
--------
------0-
Dla danych:

--------
--------
-c------
--------
-c-c----
--b-----
--------
---b----

program powinien wypisać:

--------
--------
-c------
--------
-c-c----
--0-----
--------
---0----

Uwagi

Wolno założyć, że dane są poprawne.
Nieefektywność rozwiązania może mieć wpływ na jego ocenę. Z 10 zestawów danych, na których programy przetestujemy, 3 będą wymagały wykonania dużej liczby obliczeń. Poprawne ale nieefektywne rozwiązanie, które przekroczy przydzielony limit czasu, dostanie 0 punktów za test na tych danych.

Rok 2010/2011, zadanie 3 - rozwiązanie

program wp10zad3;
 
const
    ROZMIAR = 8;
    MAX_PIONOW = ROZMIAR * ROZMIAR;
    ZNAK_BIALEGO = 'b';
    ZNAK_CZARNEGO = 'c';
    ZNAK_PUSTEGO = '-';
    BIALY = -1;
    PUSTE = 0;
    CZARNY = 1;
 
type
    Gracz = BIALY .. CZARNY;
    PozycjaNaPlanszy = 0 .. ROZMIAR * (ROZMIAR + 2) - 1;
    NumerPiona = -MAX_PIONOW .. MAX_PIONOW;
    Kierunek = -1 .. 1;
 
var plansza : array [PozycjaNaPlanszy] of NumerPiona;
    pozycje : array [NumerPiona] of PozycjaNaPlanszy;
    ostatni : array [Gracz] of NumerPiona;
 
procedure wczytaj;
var i, j, aktualna : Integer;
    c : Char;
    kto : Gracz;
begin
    for i := BIALY to CZARNY do
        ostatni[i] := 0;
    aktualna := 1;
    for i := 1 to ROZMIAR do begin
        plansza[aktualna - 1] := PUSTE;
        for j := 1 to ROZMIAR do begin
            read(c);
            kto := ord(c = ZNAK_CZARNEGO) - ord(c = ZNAK_BIALEGO);
            assert((kto = PUSTE) = (c = ZNAK_PUSTEGO));
            assert((kto <> BIALY) or (i <> 1));
            assert((kto <> CZARNY) or (i <> ROZMIAR));
            inc(ostatni[kto], kto);
            plansza[aktualna] := ostatni[kto];
            pozycje[plansza[aktualna]] := aktualna;
            inc(aktualna)
        end;
        assert(eoln);
        readln;
        plansza[aktualna] := PUSTE;
        inc(aktualna, 2)
    end;
    assert(eof)
end;
 
function wygraRuchem(kto : Gracz; czym: NumerPiona; jak : Kierunek;
                     zmianaRzedu : Integer; cel : Integer) : Boolean;
var docelowe : Integer;
    skad, pozycjaOstatniego : PozycjaNaPlanszy;
    ostatniPrzeciwnika, naDocelowym, pionPrzeciwnika : NumerPiona;
    przeciwnikMozeWygrac : Boolean;
    ruchPrzeciwnika : Kierunek;
begin
    wygraRuchem := false;
    skad := pozycje[czym];
    docelowe := skad + zmianaRzedu + jak;
    naDocelowym := plansza[docelowe];
    if (jak = 0) and (naDocelowym = PUSTE) or
            (jak <> 0) and (naDocelowym * czym < 0) then
        if docelowe div (ROZMIAR + 2) = cel then
            wygraRuchem := true
        else begin
            plansza[skad] := PUSTE;
            pozycje[czym] := docelowe;
            if jak <> 0 then begin
                ostatniPrzeciwnika := ostatni[-kto];
                pozycjaOstatniego := pozycje[ostatniPrzeciwnika];
                plansza[pozycjaOstatniego] := naDocelowym;
                pozycje[naDocelowym] := pozycjaOstatniego;
                Dec(ostatni[-kto], -kto)
            end;
            plansza[docelowe] := czym;
            ruchPrzeciwnika := -1;
            pionPrzeciwnika := ostatni[-kto];
            przeciwnikMozeWygrac := false;
            while not przeciwnikMozeWygrac and (pionPrzeciwnika <> 0) do begin
                przeciwnikMozeWygrac := wygraRuchem(-kto, pionPrzeciwnika,
                    ruchPrzeciwnika, -zmianaRzedu, 7 - cel);
                ruchPrzeciwnika := (ruchPrzeciwnika + 2) mod 3 - 1;
                if ruchPrzeciwnika = -1 then
                    inc(pionPrzeciwnika, kto)
            end;
            wygraRuchem := not przeciwnikMozeWygrac;
            if jak <> 0 then begin
                inc(ostatni[-kto], -kto);
                plansza[pozycjaOstatniego] := ostatniPrzeciwnika;
                pozycje[naDocelowym] := docelowe
            end;
            plansza[docelowe] := naDocelowym;
            pozycje[czym] := skad;
            plansza[skad] := czym
        end
end;
 
procedure wypisz;
var i, j, k, aktualna : Integer;
    pion : NumerPiona;
    kod : 0 .. 7;
begin
    aktualna := 1;
    for i := 1 to ROZMIAR do begin
        for j := 1 to ROZMIAR do begin
            pion := plansza[aktualna];
            inc(aktualna);
            if pion > 0 then
                write(ZNAK_CZARNEGO)
            else if pion = 0 then
                write(ZNAK_PUSTEGO)
            else begin
                kod := 0;
                for k := -1 to 1 do
                    kod := 2 * kod + ord(wygraRuchem(BIALY, pion, k,
                                                     -(ROZMIAR + 2), 0));
                write(kod)
            end
        end;
        inc(aktualna, 2);
        writeln
    end
end;
 
begin
    wczytaj;
    wypisz
end.

Rok 2009/2010, zadanie 3

Wprowadzenie

Tematem zadania jest "Labirynt choinkowy", który składa się z trójkątnych komórek ułożonych w nieparzystą liczbę poziomów. Na pierwszym poziomie jest jedna komórka. Każdy następny poziom to zwierciadlane odbicie poprzedniego względem osi zawierającej podstawę środkowej jego komórki, z
dwiema komórkami dodanymi po bokach.

Rozwiązaniem labiryntu jest ścieżka prowadząca od komórki na pierwszym poziomie do pnia choinki, do którego jest przejście przez dolną ścianę środkowej komórki ostatniego poziomu.

Rekurencyjny algorytm budowy losowego labiryntu wybiera losowo jedną z komórek i "odwiedza" ją. Odwiedzając komórkę, dopóki ma ona nieodwiedzonych sąsiadów, wybiera losowo jednego z nich i odwiedza go, przebijając wcześniej ścianę dzielącą obie komórki.

Algorytm ten tworzy tzw. "labirynt doskonały", czyli taki, w którym dla każdej pary komórek jest dokładnie jedna ścieżka łącząca je, nie przechodząca przez żadną z komórek więcej niż raz.

Polecenie

Napisz program, który zbuduje za pomocą opisanego wyżej algorytmu losowy labirynt choinkowy o 61 poziomach i rozwiąże go. Wynikiem programu ma być tekst w PostScripcie opisujący dwie strony. Na pierwszej znajdzie się rysunek labiryntu, a na drugiej ten sam labirynt z rozwiązaniem zaznaczonym przerywaną kreską.

Wskazówki

Rekurencyjny algorytm szukający ścieżki w labiryncie jest opisany w materiałach ze Wstępu do programowania na "ważniaku", w ćwiczeniach do modułu "Rekursja".

Przykładowy wynik działania programu jest w pliku:

==> labirynt.ps

Informacje uzupełniające (do przekazania podczas zajęć laboratoryjnych)

W ramach przygotowania do pracy nad zadaniem można rozważyć poniższy program w języku Malina (patrz zadanie nr 1):

wxaybab{cwwxwxbx}yc

Po jego analizie okaże się, że wczytuje on nieujemną liczbę całkowitą i wypisuje jej kwadrat. Kwadrat n liczymy tu jako sumę n początkowych nieujemnych liczb nieparzystych. Obserwacja, że tak można, przyda się przy wyborze reprezentacji danych w zadaniu zaliczeniowym.

Jest to zadanie na funkcje, procedury, rekurencję i trochę geometrii. Mamy tu też nietrywialny problem reprezentacji danych. Można się posłużyć tablicą jednowymiarową, zapisując w niej labirynt kolejno poziomami. Wariant alternatywny, chyba łatwiejszy do zrozumienia, ale bardziej kłopotliwy w realizacji, to użycie tablicy kwadratowej, w której komórki z poziomu n znajdą się na pozycjach o co najmniej jednym z indeksów równym n. Można też posłużyć się tablicą prostokątną i zapisać
poziomy labiryntu w kolejnych wierszach.

Poza tym, trzeba zdecydować, czy stan ściany pomiędzy dwiema komórkami ma być pamiętany w obu komórkach, czy tylko w jednej.

Proponujemy rozpoczęcie pracy od rysowania labiryntu. Działanie można sprawdzić na "pełnym" labiryncie (ze wszystkimi ścianami) i na labiryncie, z którego losowo usunęliśmy niektóre ściany. Kolejnym krokiem będzie realizacja algorytmu tworzącego "labirynt doskonały", oraz znalezienie ścieżki.

Warto wiedzieć, że to, co robi algorytm budujący labirynt, w terminologii teorii grafów nazywamy konstrukcją drzewa rozpinającego. Oprócz opisanego w treści zadania, istnieją inne algorytmy rozwiązujące ten problem.

Rok 2009/2010, zadanie 3 - rozwiązanie

program wp09zad3;
 
const
    SZEROKOSC_STRONY = 595;
    WYSOKOSC_STRONY = 842;
    MARGINES_POZIOMY = 20;
    SRODEK_SZEROKOSCI = SZEROKOSC_STRONY / 2;
    SZEROKOSC_LABIRYNTU = SZEROKOSC_STRONY - 2 * MARGINES_POZIOMY;
    WYSOKOSC_LABIRYNTU = SZEROKOSC_LABIRYNTU * sqrt(3) / 2;
    MARGINES_PIONOWY = (WYSOKOSC_STRONY - WYSOKOSC_LABIRYNTU)  / 2;
    LICZBA_POZIOMOW = 61;
    BOK_KOMORKI = SZEROKOSC_LABIRYNTU / LICZBA_POZIOMOW;
    WYSOKOSC_KOMORKI = WYSOKOSC_LABIRYNTU / LICZBA_POZIOMOW;
    ODLEGLOSC_SRODKOW = WYSOKOSC_KOMORKI * 2 / 3;
    LICZBA_KOMOREK = sqr(LICZBA_POZIOMOW);
    INDEKS_WYJSCIA = LICZBA_KOMOREK - LICZBA_POZIOMOW;
    SZEROKOSC_PNIA = 30;
    WYSOKOSC_PNIA = 40;
    LICZBA_KIERUNKOW = 3;
    LEWO = 0;
    GORA_DOL = 1;
    PRAWO = 2;
 
type
    Kierunek = LEWO .. PRAWO;
    Komorka = record
        jestSciana : array [Kierunek] of Boolean;
        znacznik : Boolean
    end;
 
var
    odwiedzona : Boolean;
    komorki : array [0 .. LICZBA_KOMOREK - 1] of Komorka;
 
function indeks(poziom, numer : Integer) : Integer;
begin
    indeks := sqr(poziom) + numer
end;
 
procedure poziomNumer(indeks : Integer; var poziom, numer : Integer);
begin
    poziom := trunc(sqrt(indeks));
    numer := indeks - sqr(poziom)
end;
 
procedure moveto(x, y : Real);
begin
    writeln(x, ' ', y, ' moveto')
end;
 
procedure rmoveto(x, y : Real);
begin
    writeln(x, ' ', y, ' rmoveto')
end;
 
procedure rlineto(x, y : Real);
begin
    writeln(x, ' ', y, ' rlineto')
end;
 
procedure rysujParzystaKomorke(poziom, numer : Integer);
begin
    moveto(SRODEK_SZEROKOSCI - (poziom - numer) * BOK_KOMORKI / 2,
           WYSOKOSC_STRONY - MARGINES_PIONOWY - poziom * WYSOKOSC_KOMORKI);
    if komorki[indeks(poziom, numer)].jestSciana[LEWO] then
        rlineto(- BOK_KOMORKI / 2, - WYSOKOSC_KOMORKI)
    else
        rmoveto(- BOK_KOMORKI / 2, - WYSOKOSC_KOMORKI);
    if komorki[indeks(poziom, numer)].jestSciana[GORA_DOL] then
        rlineto(BOK_KOMORKI, 0)
    else
        rmoveto(BOK_KOMORKI, 0);
    if komorki[indeks(poziom, numer)].jestSciana[PRAWO] then
        rlineto(- BOK_KOMORKI / 2, WYSOKOSC_KOMORKI)
end;
 
procedure rysujLabirynt;
var i, j : Integer;
begin
    moveto(SRODEK_SZEROKOSCI - SZEROKOSC_PNIA / 2, MARGINES_PIONOWY);
    rlineto(0, - WYSOKOSC_PNIA);
    rlineto(SZEROKOSC_PNIA, 0);
    rlineto(0, WYSOKOSC_PNIA);
    for i := 0 to LICZBA_POZIOMOW - 1 do
        for j := 0 to i do
            rysujParzystaKomorke(i, 2 * j);
    writeln('stroke')
end;
 
function nieodwiedzonaKomorka(i, j : Integer) : Boolean;
begin
    if (i < 0) or (i > LICZBA_POZIOMOW - 1) or (j < 0) or (j > 2 * i) then
        nieodwiedzonaKomorka := false
    else
        nieodwiedzonaKomorka := komorki[indeks(i, j)].znacznik <> odwiedzona
end;
 
procedure sasiad(x, y : Integer; k : Kierunek; var a, b : Integer);
begin
    case k of
        LEWO : begin
            a := x;
            b := y - 1
        end;
        GORA_DOL :
            if odd(y) then begin
                a := x - 1;
                b := y - 1
            end else begin
                a := x + 1;
                b := y + 1
            end;
        PRAWO : begin
            a := x;
            b := y + 1
        end
    end
end;
 
function przeciwny(k : Kierunek) : Kierunek;
begin
    przeciwny := LICZBA_KIERUNKOW - 1 - k
end;
 
procedure przebijajSciany(x, y : Integer);
var i, pozycjaWybranego, a, b : Integer;
    s, wybrany : Kierunek;
    doSprawdzenia : array [0 .. LICZBA_KIERUNKOW - 1] of Kierunek;
begin
    komorki[indeks(x, y)].znacznik := odwiedzona;
    for s := LEWO to PRAWO do
        doSprawdzenia[s] := s;
    for i := 0 to LICZBA_KIERUNKOW - 1 do begin
        pozycjaWybranego := i + random(LICZBA_KIERUNKOW - i);
        wybrany := doSprawdzenia[pozycjaWybranego];
        doSprawdzenia[pozycjaWybranego] := doSprawdzenia[i];
        sasiad(x, y, wybrany, a, b);
        if nieodwiedzonaKomorka(a, b) then begin
            komorki[indeks(x, y)].jestSciana[wybrany] := false;
            komorki[indeks(a, b)].jestSciana[przeciwny(wybrany)] := false;
            przebijajSciany(a, b)
        end
    end
end;
 
procedure stworzLabirynt;
var i, x, y : Integer;
    k : Kierunek;
begin
    for i := 0 to LICZBA_KOMOREK-1 do begin
        for k := LEWO to PRAWO do
            komorki[i].jestSciana[k] := true;
        komorki[i].znacznik := false
    end;
    odwiedzona := true;
    poziomNumer(random(LICZBA_KOMOREK), x, y);
    przebijajSciany(x, y);
    komorki[INDEKS_WYJSCIA].jestSciana[GORA_DOL] := false
end;
 
procedure zacznijRysowanieDrogi;
begin
    moveto(SRODEK_SZEROKOSCI, MARGINES_PIONOWY - WYSOKOSC_PNIA / 2);
    rlineto(0, WYSOKOSC_PNIA / 2 + ODLEGLOSC_SRODKOW / 2)
end;
 
procedure rysujKrok(odbicie : Integer; k : Kierunek);
begin
    rlineto(ODLEGLOSC_SRODKOW * cos(PI * (4 * k - 1) / 6),
            odbicie * ODLEGLOSC_SRODKOW * sin(PI * (4 * k - 1) / 6))
end;
 
function jestRozwiazanie(x, y : Integer) : Boolean;
var znalezione : Boolean;
    k, a, b : Integer;
begin
    if not nieodwiedzonaKomorka(x, y) then
        jestRozwiazanie := false
    else begin
        komorki[indeks(x, y)].znacznik := odwiedzona;
        if indeks(x, y) = INDEKS_WYJSCIA then begin
            zacznijRysowanieDrogi;
            jestRozwiazanie := true
        end else begin
            znalezione := false;
            k := LEWO;
            while (k <= PRAWO) and not znalezione do begin
                if not komorki[indeks(x, y)].jestSciana[k] then begin
                    sasiad(x, y, k, a, b);
                    if jestRozwiazanie(a, b) then begin
                        rysujKrok((b mod 2) * 2 - 1, k);
                        znalezione := true
                    end
                end;
                k := k + 1
            end;
            jestRozwiazanie := znalezione
        end
    end
end;
 
procedure rozwiazLabirynt;
begin
    odwiedzona := not odwiedzona;
    writeln('[2] 0 setdash');
    if not jestRozwiazanie(0, 0) then
        writeln('% Blad algorytmu budujacego labirynt');
    writeln('stroke')
end;
 
begin
    randomize;
    writeln('%!PS');
    stworzLabirynt;
    rysujLabirynt;
    writeln('showpage');
    rysujLabirynt;
    rozwiazLabirynt;
    writeln('showpage')
end.

Rok 2008/2009, zadanie 3

Wprowadzenie

Powiemy, że znak X występuje w kontekście napisu S, jeśli S bezpośrednio poprzedza X. Np. w tekście:

ALA_MA_KOTA_ALE_NIE_MA_MYSZY

w kontekście napisu A_ występują znaki M, K i A, w kontekście AL występują znaki A oraz E, w kontekście OT jest tylko znak A, a w kontekście
ZY nie występuje żaden znak.

Polecenie

Napisz program, który wywołany poleceniem:

./wp08lab_zad3 K N

gdzie K i N to nieujemne liczby całkowite, wczyta z wejścia tekst i wypisze na wyjście K jego początkowych znaków. Każdy następny wypisany znak wybierzemy losowo spośród znaków, które w tekście wejściowym wystąpiły w kontekście K ostatnio wypisanych
znaków. Prace należy zakończyć po wypisaniu N znaków, a także w przypadku, gdyby w kontekście ostatnio wypisanych znaków w tekście wejściowym nie było żadnego znaku.

Jeśli na wejściu jest mniej niż K znaków, program ma tylko skopiować tekst wejściowy na wyjście.