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.

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:

  1. program wypisujący wiersz zawierający 10 gwiazdek

  2. program wczytujący z wejścia liczbę n i wypisujący wiersz zawierający n gwiazdek

  3. program wczytujący z wejścia liczbę n i wypisujący n wierszy, w każdym po n gwiazdek (czyli kwadrat z gwiazdek)

  4. 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

  5. jak w punkcie (4), ale przekątna od lewego dolnego do prawego górnego rogu

  6. program wczytujący liczbę n i wypisujący choinkę bez pnia, czyli sklejenie trójkątów z punktów (4) i (5)

  7. 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:








ZałącznikWielkość
wp10zad1.pas1.98 KB
wp09zad1.pas2.52 KB
wp08zad1.pas1.76 KB
wp07zad1.pas2.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:

9
7
5
3
1

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, &pi; / 2]. W szczególności, dla &pi; / 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:








ZałącznikWielkość
wp10zad2.pas3.26 KB
wp09zad2.pas4.67 KB
wp08zad2.pas4.46 KB
wp07zad2.pas1.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.

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:








ZałącznikWielkość
wp10zad3.pas4.05 KB
wp09zad3.pas6.07 KB
wp08zad3.pas2.42 KB
wp07zad3.pas2.68 KB

Laboratorium 11: Praca nad zadaniem zaliczeniowym 3. Gramatyki, drzewa

Ćwiczenie 1

Uruchom poniższy program symulujący wyprowadzenie słowa z gramatyki bezkontekstowej.

{**
 * Program symulujacy wyprowadzenie slowa za pomoca gramatyki bezkontekstowej.
 *
 * Obsluguje gramatyki w postaci normalnej Chomsky'ego, czyli takie, ktorych
 * produkcje maja po prawej stronie albo dwa symbole pomocnicze albo jeden
 * koncowy. Za symbole pomocnicze uznaje wielkie litery a za koncowe male
 * litery.
 *
 * Program wczytuje z wejscia ciag wierszy z produkcjami gramatyki, zakonczony
 * wierszem pustym. Miedzy lewa a prawa strona oczekuje znakow '->'.
 * Przyjmuje, ze aksjomatem jest symbol po lewej stronie pierwszej produkcji.
 * Po wczytaniu gramatyki, symuluje wyprowadzenie slowa, dajac uzytkownikowi
 * mozliwosc wyboru produkcji dla pierwszego od lewej symbolu pomocniczego.
 * Produkcje wskazywane sa przez wpisanie prawej strony.
 *
 * Poprawnosc danych jest sprawdzana. W przypadku wykrycia bledu, na wyjscie
 * diagnostyczne wypisywany jest komunikat a wiersz danych pobierany jest
 * ponownie.
 *
 * autor: Artur Zaroda <zaroda@mimuw.edu.pl>
 * wersja: 2.0
 * data: 12 listopada 2014
 *}
program wyprowadzenie;
 
const
    {* Maksymalna dlugosc wyprowadzanego slowa *}
    MAX_ROZMIAR = 1000;
 
type
    {* Symbole pomocnicze *}
    Pomocniczy = 'A' .. 'Z';
 
    {* Symbole koncowe *}
    Koncowy = 'a' .. 'z';
 
    {**
     * Reprezentacja gramatyki.
     *
     * "aksjomat" to symbol poczatkowy
     *
     * "naPomocnicze" jest reprezentacja produkcji z symbolami pomocniczymi po
     * prawej stronie. "naPomocnicze[A, B, C]" to prawda, gdy istnieje
     * produkcja A->BC
     *
     * "naKoncowy" jest reprezentacja produkcji z symbolem koncowym.
     * "naKoncowy[A, x]" to prawda, gdy istnieje produkcja A->x
     *}
    Gramatyka = record
        aksjomat : Pomocniczy;
        naPomocnicze : array [Pomocniczy, Pomocniczy, Pomocniczy] of Boolean;
        naKoncowy : array [Pomocniczy, Koncowy] of Boolean
    end;
 
    {**
     * Reprezentacja wyprowadzanego slowa, zlozonego z symboli pomocniczych
     * i koncowych.
     *
     * "ileKoncowych" do liczba symboli koncowych
     *
     * "ilePomocniczych" to liczba symboli pomocniczych
     *
     * "symbole" to tablica, w ktorej pierwszych "ileKoncowych" pozycji
     * zajmuja symbole koncowe a ostatnich "ilePomocniczych" symbole
     * pomocnicze
     *}
    Slowo = record
        ileKoncowych, ilePomocniczych : Integer;
        symbole : array [1 .. MAX_ROZMIAR] of Char
    end;
 
{* Sprawdza, czy znak "c" reprezentuje symbol pomocniczy *}
function jestPomocniczym(c : Char) : Boolean;
begin
    jestPomocniczym := (low(Pomocniczy) <= c) and (c <= high(Pomocniczy))
end;
 
{* Sprawdza, czy znak "c" reprezentuje symbol koncowy *}
function jestKoncowym(c : Char) : Boolean;
begin
    jestKoncowym := (low(Koncowy) <= c) and (c <= high(Koncowy))
end;
 
{* Wypisuje na wyjscie diagnostyczne komunikat "k" o bledzie w danych "s" *}
procedure wypiszKomunikat(const k, s : String);
begin
    writeln(stderr, k, ': ''', s, '''')
end;
 
{**
 * Wczytuje z wejscia gramatyke i zapisuje na "g".
 *
 * W przypadku wykrycia bledu, prosi uzytkownika o ponowne wpisanie produkcji.
 *}
procedure wczytajGramatyke(var g : Gramatyka);
var p, q, r : Pomocniczy;
    k : Koncowy;
    s : String;
    pierwsza, ok : Boolean;
begin
    with g do begin
        { czyscimy tablice produkcji }
        for p := low(Pomocniczy) to high(Pomocniczy) do begin
            for q := low(Pomocniczy) to high(Pomocniczy) do
                for r := low(Pomocniczy) to high(Pomocniczy) do
                    naPomocnicze[p, q, r] := false;
            for k := low(Koncowy) to high(Koncowy) do
                naKoncowy[p, k] := false
        end;
        readln(s);
        pierwsza := true;
        while (length(s) <> 0) or pierwsza do begin
            { nie pozwalamy na opuszczenie petli, jesli nie bylo zadnej
              produkcji, bo nie wiedzielibysmy, co jest aksjomatem }
            ok := false;
            if length(s) = 0 then
                wypiszKomunikat('Oczekiwany niepusty wiersz, a nie', s)
            else if (length(s) <> 4) and (length(s) <> 5) then
                wypiszKomunikat('Nieprawidlowa dlugosc produkcji', s)
            else if not jestPomocniczym(s[1]) then
                wypiszKomunikat('Bledny symbol po lewej stronie produkcji', s)
            else if (s[2] <> '-') or (s[3] <> '>') then
                wypiszKomunikat('Brak strzalki w produkcji', s)
            else if length(s) = 4 then
                if not jestKoncowym(s[4]) then
                    wypiszKomunikat('Oczekiwany symbol koncowy w produkcji', s)
                else
                    ok := true
            else if not jestPomocniczym(s[4]) or not jestPomocniczym(s[5]) then
                wypiszKomunikat('Oczekiwane symbole pomocnicze w produkcji', s)
            else
                ok := true;
            if ok then begin
                if pierwsza then begin
                    aksjomat := s[1]; { ten symbol uznajemy za poczatkowy }
                    pierwsza := false
                end;
                if length(s) = 4 then
                    naKoncowy[s[1], s[4]] := true
                else begin
                    assert(length(s) = 5);
                    naPomocnicze[s[1], s[4], s[5]] := true
                end
            end;
            readln(s)
        end
    end
end;
 
{* Do slowa "s" dopisuje symbol koncowy "k" *}
procedure dodajKoncowy(var s : Slowo; k : Koncowy);
begin
    with s do begin
        assert(ilePomocniczych + ileKoncowych <= MAX_ROZMIAR);
        inc(ileKoncowych);
        symbole[ileKoncowych] := k
    end
end;
 
{* Ze slowa "s" usuwa pierwszy symbol pomocniczy i zapisuje na "p" *}
procedure usunPomocniczy(var s : Slowo; var p : Pomocniczy);
begin
    with s do begin
        assert(ilePomocniczych > 0);
        dec(ilePomocniczych);
        p := symbole[high(symbole) - ilePomocniczych]
    end
end;
 
{* Do slowa "s" dopisuje symbol "p" jako pierwszy z pomocniczych *}
procedure dodajPomocniczy(var s : Slowo; p : Pomocniczy);
begin
    with s do begin
        assert(ilePomocniczych + ileKoncowych <= MAX_ROZMIAR);
        symbole[high(symbole) - ilePomocniczych] := p; { pomocnicze na koncu }
        inc(ilePomocniczych)
    end
end;
 
{* Wypisuje produkcje dla symbolu "a" w gramatyce "g" *}
procedure wypiszOpcje(a : Pomocniczy; const g : Gramatyka);
var p, q : Pomocniczy;
    k : Koncowy;
    pierwszyRaz : Boolean;
begin
    with g do begin
        write('(', a, '->');
        pierwszyRaz := true; { jeszcze nie bylo zadnej produkcji }
        for p := low(Pomocniczy) to high(Pomocniczy) do
            for q := low(Pomocniczy) to high(Pomocniczy) do
                if naPomocnicze[a, p, q] then begin
                    if pierwszyRaz then
                        pierwszyRaz := false
                    else
                        write('|');
                    write(p, q)
                end;
        for k := low(Koncowy) to high(Koncowy) do
            if naKoncowy[a, k] then begin
                if pierwszyRaz then
                    pierwszyRaz := false
                else
                    write('|');
                write(k)
            end;
        write('): ')
    end
end;
 
{* Wypisuje slowo "s" *}
procedure wypiszSlowo(const s : Slowo);
var i : Integer;
begin
    with s do begin
        for i := 1 to ileKoncowych do
            write(symbole[i]);
        for i := high(symbole) - ilePomocniczych + 1 to high(symbole) do
            write(symbole[i]);
        writeln
    end
end;
 
{* Tworzy slowo puste *}
procedure inicjujPuste(var s : Slowo);
begin
    s.ilePomocniczych := 0;
    s.ileKoncowych := 0
end;
 
{*
 * W slowie "s" stosuje produkcje o prawej stronie "p".
 *
 * Przed wywolaniem procedury, pierwszy od lewej symbol pomocniczy zostal juz
 * usuniety ze slowa "s".
 *}
procedure zastosujProdukcje(var s : Slowo; const p : String);
begin
    if length(p) = 1 then
        dodajKoncowy(s, p[1])
    else begin
        assert(length(p) = 2);
        dodajPomocniczy(s, p[2]);
        dodajPomocniczy(s, p[1])
    end
end;
 
{* Sprawdza, czy w slowie "s" sa same symbole koncowe *}
function brakPomocniczych(const s : Slowo) : Boolean;
begin
    brakPomocniczych := (s.ilePomocniczych = 0)
end;
 
{**
 * Wczytuje z wejscia prawa strone produkcji gramatyki "g" dla symbolu "a"
 * i zapisuje na "p".
 *
 * W przypadku wykrycia bledu, prosi uzytkownika o ponowne wprowadzenie
 * produkcji.
 *}
procedure wybierzProdukcje(var p : String; a : Pomocniczy;
        const g : Gramatyka);
var ok : Boolean;
    s : String;
begin
    ok := false;
    repeat
        wypiszOpcje(a, g);
        readln(s);
        if (length(s) <> 1) and (length(s) <> 2) then
            wypiszKomunikat('Nieprawidlowa dlugosc produkcji', s)
        else if length(s) = 1 then
            if not jestKoncowym(s[1]) then
                wypiszKomunikat('To nie jest symbol koncowy', s)
            else if not g.naKoncowy[a, s[1]] then
                wypiszKomunikat('Brak produkcji z prawa strona', s)
            else
                ok := true
        else if not jestPomocniczym(s[1]) or not jestPomocniczym(s[2]) then
            wypiszKomunikat('Powinny byc dwa symbole pomocnicze', s)
        else if not g.naPomocnicze[a, s[1], s[2]] then
            wypiszKomunikat('Brak produkcji z prawa strona', s)
        else
            ok := true
    until ok;
    p := s
end;
 
{* Wczytuje gramatyke i symuluje wyprowadzenie slowa *}
procedure glowna;
var wybor : String;
    symulowana : Gramatyka;
    wyprowadzane : Slowo;
    aktualny : Pomocniczy;
begin
    wczytajGramatyke(symulowana);
    inicjujPuste(wyprowadzane);
    dodajPomocniczy(wyprowadzane, symulowana.aksjomat);
    wypiszSlowo(wyprowadzane);
    while not brakPomocniczych(wyprowadzane) do begin
        usunPomocniczy(wyprowadzane, aktualny);
        wybierzProdukcje(wybor, aktualny, symulowana);
        zastosujProdukcje(wyprowadzane, wybor);
        wypiszSlowo(wyprowadzane)
    end
end;
 
begin
    glowna
end.

Rozważ i spróbuj wprowadzić zmiany, dzięki którym program ten będzie obsługiwał szerszą klasę gramatyk bezkontekstowych.

Ćwiczenie 2

Dany jest program wczytujący z wejścia i wypisujący na wyjście prefiksową reprezentację drzewa binarnego znaków innych niż '-'.

program znaki;
 
const
    PUSTE = '-';
 
type
    Drzewo = ^Wezel;
    Wezel  = record
        w : Char;
        lsyn, psyn : Drzewo
    end;
 
var d : Drzewo;
 
procedure wczytaj(var d : Drzewo);
var c : Char;
begin
    assert(not eoln);
    read(c);
    if c = PUSTE then
        d := nil
    else begin
        new(d);
        d^.w := c;
        wczytaj(d^.lsyn);
        wczytaj(d^.psyn)
    end
end;
 
procedure wypisz(d : Drzewo);
begin
    if d = nil then
        write(PUSTE)
    else begin
        write(d^.w);
        wypisz(d^.lsyn);
        wypisz(d^.psyn)
    end
end;
 
procedure usun(d : Drzewo);
begin
    if d <> nil then begin
        usun(d^.lsyn);
        usun(d^.psyn);
        dispose(d)
    end
end;
 
begin
    wczytaj(d);
    assert(Eoln);
    readln;
    wypisz(d);
    writeln;
    usun(d)
end.
  1. Uruchom i przetestuj program.
  2. Uzupełnij go o procedurę lub funkcję będącą rozwiązaniem jednego z zadań na drzewa binarne z ćwiczeń. Napisz np. procedurę usuwającą z drzewa binarnego wszystkie liście.

Laboratorium 12: Omówienie zadania zaliczeniowego 4

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








ZałącznikWielkość
wp10zad4.pas3.81 KB
wp09zad4.pas4.71 KB
wp08zad4.pas6.38 KB
wp07zad4.pas4.04 KB

Laboratorium 13: Praca nad zadaniem zaliczeniowym 4. Pliki

Ćwiczenie 1

Dany jest program przekształcający plik binarny na tekstowy i na odwrót.

program bttb;
 
var ile : Integer;
    kod : Word;
 
procedure komunikat;
begin
    writeln('Program przeksztalcajacy binaria na tekst i tekst na binaria');
    writeln('Sposob wywolania:');
    writeln('  bttb -bt PlikDanychBinarnych PlikWynikuTekstowego IleWWierszu');
    writeln('lub:');
    writeln('  bttb -tb PlikDanychTekstowych PlikWynikuBinarnego');
    halt
end;
 
procedure binariaNaTekst(s1, s2 : String; ile : Integer);
var f : file of Byte;
    g : Text;
    b : Byte;
    wAktualnym, i : Integer;
begin
    assign(f, s1);
    assign(g, s2);
    reset(f);
    rewrite(g);
    wAktualnym := 0;
    while not eof(f) do begin
        read(f, b);
        for i := 1 to 8 do begin
            write(g, b div 128);
            b := 2 * (b mod 128)
        end;
        wAktualnym := wAktualnym + 1;
        if wAktualnym = ile then begin
            writeln(g);
            wAktualnym := 0
        end else
            write(g, ' ')
    end;
    if wAktualnym > 0 then
        writeln(g);
    close(g);
    close(f)
end;
 
procedure tekstNaBinaria(s1, s2 : String);
var f : Text;
    g : file of Byte;
    byloBitow : Integer;
    aktualnyBajt : Byte;
    c : Char;
begin
    assign(f, s1);
    assign(g, s2);
    reset(f);
    rewrite(g);
    byloBitow := 0;
    aktualnyBajt := 0;
    while not eof(f) do
        if eoln(f) then
            readln(f)
        else begin
            read(f, c);
            if (c = '0') or (c = '1') then begin
                aktualnyBajt := 2 * aktualnyBajt;
                if c = '1' then
                    aktualnyBajt := aktualnyBajt + 1;
                byloBitow := byloBitow + 1;
                if byloBitow = 8 then begin
                    write(g, aktualnyBajt);
                    aktualnyBajt := 0;
                    byloBitow := 0
                end
            end
        end;
    if byloBitow <> 0 then
        writeln('Niepoprawny plik danych');
    close(g);
    close(f)
end;
 
begin
    if paramCount = 0 then
        komunikat;
    if paramStr(1) = '-bt' then begin
        if paramCount <> 4 then
            komunikat;
        ile := 1;
        val(paramStr(4), ile, kod);
        if (kod <> 0) or (ile <= 0) then
            komunikat;
        binariaNaTekst(paramStr(2), paramStr(3), ile)
    end else if paramStr(1) = '-tb' then begin
        if paramCount <> 3 then
            komunikat;
        tekstNaBinaria(paramStr(2), paramStr(3))
    end else
        komunikat
end.

  1. Uruchom go i przetestuj.
  2. Zmodyfikuj program, dodając nowe opcje zmieniające obsługiwany format pliku tekstowego. Można np. rozszerzyć go o obsługę wartości bajtów w zapisie dziesiętnym lub szesnastkowym.

Ćwiczenie 2

Napisz program kompresujący i program dekompresujący plik binarny metodą RLE (run-lenght encoding, kodowanie długości serii).