Wstęp do programowania - podejście imperatywne

Opis

Podstawowy przedmiot pierwszego roku studiów, mający zapoznać studentów z pojęciami algorytmu i programu oraz nauczyć ich projektowania, zapisywania, dowodzenia poprawności i uwzględniania złożoności algorytmów. Prezentacja technik programistycznych i struktur danych wykorzystywanych w programowaniu w małej i średniej skali.

Sylabus

Autor

Zawartość

Literatura

  1. S.Alagić, M.Arbib, Projektowanie programów poprawnych i dobrze zbudowanych, Wydawnictwa Naukowo - Techniczne 1982
  2. L. Banachowski, A.Kreczmar, Elementy analizy algorytmów, Wydawnictwa Naukowo - Techniczne 1987
  3. T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wprowadzenie do algorytmiki, Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
  4. D.E.Knuth, Sztuka programowania komputerów tom 3, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.
  5. N.Wirth, Wstęp do programowania systematycznego, Wydawnictwa Naukowo - Techniczne 1999.
  6. N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.

Materiały elektroniczne

  1. Wstęp do algorytmów (Ćwiczenia: prostokąty i odcinki)
  2. Wprowadzenie do programowania (Ćwiczenia: tablice)
  3. Gramatyki – definiowanie składni i semantyki wyrażeń (Ćwiczenia)
  4. Reprezentacja liczb (Ćwiczenia)
  5. Składnia i semantyka instrukcji (Ćwiczenia: wyszukiwanie binarne)
  6. Dowodzenie poprawności programów (Ćwiczenia)
  7. Pliki (Ćwiczenia)
  8. Pamięć dynamiczna (Ćwiczenia: wskaźniki)
  9. Procedury i funkcje (Ćwiczenia: procedury i funkcje)
  10. Rekursja (Ćwiczenia)

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

Wykłady

Wykład 01: Wprowadzenie do algorytmiki

O co chodzi w algorytmice? Jak rozumieć należy język programowania?

ZałącznikWielkość
Algorytmika1.pdf248.81 KB

Wykład 02. Wprowadzenie do algorytmiki (2)

ZałącznikWielkość
Algorytmika2.pdf535.92 KB

Wykład 03. Wprowadzenie do algorytmiki (3)

ZałącznikWielkość
Algorytmika3.pdf129.27 KB

Wykład 04-05: Historia

ZałącznikWielkość
Historia-2010.pdf4.6 MB

Wykład 06: Gramatyki (1)

ZałącznikWielkość
Gramatyki1.pdf208.84 KB

Wykład 07: Gramatyki(2) Instrukcje Pascala

ZałącznikWielkość
Gramatyki-2.pdf181.61 KB

Wykład 08: Częściowa poprawność

ZałącznikWielkość
PoprawnoscHoare.pdf145.2 KB

Wykład 09: Całkowita poprawność

ZałącznikWielkość
CalkowitaPoprawnosc.pdf142.06 KB

Wykład 10: Procedury i funkcje

ZałącznikWielkość
Procedury11.pdf141.25 KB

Wykład 11: Rekursja

ZałącznikWielkość
WP-Rekursja.pdf129.39 KB

Wykład 12: Dodatki pascalowe

ZałącznikWielkość
Dodatki1.pdf164.79 KB

Wykład 13-14: Reprezentacje binarne

ZałącznikWielkość
Binaria2010(2).pdf145.59 KB

Wykład 15: Wskaźniki

ZałącznikWielkość
Wskazniki.pdf140.52 KB

Wykład 16: Listy

ZałącznikWielkość
Listy.pdf135.13 KB

Wykład 17-18: Stosy i kolejki

ZałącznikWielkość
Stosy-Kolejki.pdf133.61 KB

Wykład 19: DFS i BFS

ZałącznikWielkość
DFS-BFS.pdf190.47 KB

Wykład 20: Drzewa

ZałącznikWielkość
Drzewa.pdf125.08 KB

Wykład 21: Drzewa BST

ZałącznikWielkość
DrzewaBST.pdf162.66 KB

Wykład 22: Dziel i rządź

ZałącznikWielkość
Dziel-Rzadz.pdf130.08 KB

Wykład 23: Pliki

ZałącznikWielkość
Pliki1.pdf171.9 KB

Ćwiczenia

Ćwiczenia 01: wstęp

Zadanie o przecinających się prostokątach - na płaszczyźnie dane są dwa prostokąty o bokach prostopadlych do osi. Wyznacz ich przecięcie.

Wskazówki do rozwiązania:

Zastanówmy, czym może być rozwiązanie. Odpowiedź zależy od tego, czy prostokąty są otwarte, czy domknięte. Ustalmy dla ułatwienia, że otwarte. Wtedy są możliwe dwa typy wyników: zbiór pusty lub prostokąt o bokach prostopadłych do osi.

Kolejne pytanie: jak reprezentować dane i wyniki. Dane, to dla każdego prostokąta 4 liczby rzeczywiste (albo całkowite, jeśli chcemy to robić na kratkach) reprezentujące współrzędne wierzchołków przy przekątnej. Wygodnie jest od razu ustalić, że chodzi o konkretną przekątną, np. tę która idzie w prawo w górę.

Zatem zadanie przyjmuje taką treść: Danych jest 8 liczb rzeczywistych: a1,b1,a2,b2,a3,b3,a4,b4. Punkty o współrzędnych (a1,b1) i (a2,b2) są wierzchołkami prostokąta P1, zaś (a3,b3), (a4,b4) prostokąta P2, przy czym a1 < a2, b1 < b2, a3 < a4, b3 < b4.

Ćwiczenia 02: Flaga polska

Dziś - zadanie o fladze polskiej.

Treść: Danych jest M urn, numerowanych od 1 do M, każda zawierająca żeton biały lub czerwony. Robot ma za zadanie tak poprzestawiać urny z żetonami, aby wśród kolejnych urn najpierw były te, które mają czerwone żetony, a potem te, które mają białe żetony. Do dyspozycji ma dwie funkcje:

  • Kol(i) określającą kolor żetonu w i-tej urnie
  • Z(i,j) zamieniającą urnę i-tą z j-tą.

Uwaga: robot może się zepsuć, jeśli każe się mu sięgnąć poza zakres 1..n lub zamienić urnę i-tą z i-tą.

Ćwiczenia 03: Zadanie o fladze holenderskiej

Tym razem mamy w N urnach żetony 3 kolorów: czerwone, białe i niebieskie i chcemy je poprzestawiać tak, aby końcowo były ułożone w tej właśnie kolejności.

Wskazówka: Postaraj się zachować następujący niezmiennik: \( N(c,b,n)=\forall 1\le k < c: Kol(k)=czerwony \land \forall c \le k \le b: Kol(k)=biały \land \forall n < k \le N: Kol(k)=niebieski \land 1\le c \le b \le n+1 \le N+1 \).

Ćwiczenia 04: Sortowanka

Tym razem sortowanie danych małego rozmiaru: 0,1,2,3,4,5 elementów. Postaraj się to zrobić optymalnie, czyli za pomocą najmniejszej możliwej liczby porównań. Kolejno są to liczby 0,0,1,3,5,7, przy czym posortowanie 5 elementów za pomocą 7 porównań należy uznać za sukces.

Ćwiczenia 05: Zadanie o najdłuższym plateau

Znajdź najdłuższy segment stały w tablicy. Rozważ dwa warianty: tablica posortowana i nieposortowana.

Ćwiczenia 06: Arytmetyka dużych liczb

Dziś mnożenie i dzielenie dużych liczb. Podobnie jak na poprzednich ćwiczeniach liczby trzymamy w tablicach indeksowanych od 0 do n-1 i w przypadku przepełnienia wyniku sygnalizujemy to.

Dla dużych liczb x zapisanych w tablicy typu liczba=array [0..N-1] of Integer robimy procedury i funkcje
1. function Zero(const x:liczba):Boolean; sprawdzająca zerowość liczby x
2. function Większe(const x,y:liczba):Boolean; sprawdzająca czy x>y
3. procedure Dodaj(var x:Integer; const y:liczba); dodającą do liczby x wartość y
4. procedure Odejmij(var x:Integer; const y:liczba); odejmującą od liczby x wartość y

Ćwiczenia 07: Mnożenie i dzielenie z resztą dużych liczb

Dziś Iloczyn i - jesli się da - dzielenie z resztą. Tak jak na poprzednich zajęciach sygnalizujemy przepełnienie, jeśli wystąpi.

Ćwiczenia 08: Zadanie o segmencie z największą sumą elementów

Napisz funkcję znajdującą w zadanej tablicy A typu array[1..N] of integer, N > 0, maksymalną sumę segmentu (spójnego fragmentu tablicy). Przyjmujemy, że segment pusty ma sumę 0.

Ćwiczenia 09: Gramatyki (1)

Na ćwiczeniach nr 9 zaczynamy zadania z gramatyk. Podaj gramatykę generującą

  1. Wszystkie słowa w \( \in {a,b}*\) t. że #(a,w)<>#(b,w)
  2. Wszystkie słowa w \(\in {a,b}* \)poza abababb .
  3. Języki typu \(a^n b^k c^m\) takie, że n,k,m spełniają jakieś
    równania/nierówności liniowe np

    • n+k=m
    • n+m=k
    • n+m=k+1
    • n+m<>k
    • n+2m=k+2
      itp.
  4. Język nawiasów kwadratowych i okrągłych; kwadratowych nie można umieszczać wewnątrz okrągłych.
  5. Wyrażenia boolowskie

Ćwiczenia 10: Gramatyki (2)

W poniższych zadaniach należy napisać gramatykę generującą
  1. Wszystkie słowa w \in {a,b}* t. ze #(a,w)<>#(b,w)
  2. Wszystkie słowa w \in {a,b}* poza abababb.
  3. Języki typu a^n b^k c^m takie, że n,k,m spełniają poniższe równania/nierówności liniowe
    4. n+k=m n+m=k n+m=k+1 n+m<>k n+2m=k+2
  4. Język nawiasów kwadratowych i okrągłych; kwadratowych nie można umieszczać wewnątrz okrągłych.
  5. wyrażenia arytmetyczne z prawostronnie łącznym potęgowaniem, czyli że np.
    6. x*y^z^v parsuje się jako x*(y^(z^v))

Ćwiczenia 11: Gramatyki(3)

Wygeneruj słowa nad alfabetem {a,b}

1. o parzystej liczbie a
Na przykład taka jednoznaczna:
S ::= aBaS | bS | e
B ::= bB | e

2. gdzie żadne dwa a nie występują obok siebie
Na przykład taka jednoznaczna:
S ::= aB | B
B:= e | bS

3. gdzie nigdzie więcej niż dwa a nie może wystąpić koło siebie
Na przykład taka (jednoznaczna):
S::= aaB | aB | B
B ::= e | bS
Uzasadnienie: wprowadzamy nowy "symbol" aa, który nie może wystąpić koło a.

4. gdzie żadne słowo nie jest postaci \(a^nb^na^n \)

Ćwiczenia 12: Wyszukiwanie binarne (1)

Dzisiaj liczymy entier z pierwiastka, czyli dla danego n>=0 szukamy takiej liczby k, żeby \(k*k<=n\), ale \((k+1)*(k+1)>n\). Napisz program obliczający sufit i podłogę z pierwiastka z n, \(n \in N ,n > 0\) (oczywiście bez operacji pierwiastek).

Ćwiczenia 13:Wyszukiwanie binarne (2)

Zadanie 1
Oblicz ile jest wystąpień x w posortowanej tablicy A.

Wskazówka: da się to zrobić w czasie logarytmicznym.

Zadanie 2
Znajdź maksimum w ciągu bitonicznym, czyli takim, że istnieje 1<=k<=n takie, że dla każdego 1 < j<=k A[j-1] < A[j] oraz dla każdego k < j <=n A[j-1] > A[j]. Uwaga: ciąg bitoniczny może być ciągiem rosnącym (lub malejącym) i wtedy największy element jest w A[n] (odpowiednio A[1]).

Zadanie 3.
Pokaż, że nie da się znaleźć w czasie logarytmicznym maksimum w ciągu słabo bitonicznym, czyli takim, że wszystkie nierówności są nieostre.

Zadanie 4
Tablicę posortowaną rosnąco przesunięto cyklicznie w prawo o k. Wyznacz najmniejsze k, które mogło spowodować takie przesunięcie (dla k >= n oczywiście przesunięcie się zacykla mod n).

Ćwiczenia 14: Zadanie o dwóch medianach

Zadanie o dwóch medianach. Tej samej długości tablice A i B:array[1..n] of Integer są posortowane rosnąco i zawierają rozłączne wartości. Ze względu na to, że łączna liczba elementów jest parzysta, możemy dwa środkowe co do wartości elementy spośród nich uznać za mediany: małą m i dużą M. Wyznacz je. (chodzi o element n-ty i n+1-wszy co do wartości w obu tablicach łącznie).

Oczywiście chodzi o to, żeby zrobić to w czasie logarytmicznym.

Ćwiczenia 15: Przesunięcie cykliczne tablicy

Przesuń tablicę o k elementów w prawo. (Zadanie nr 9 z Wazniaka, ćwiczenia nr 2: tablice)

Ćwiczenia 16: Wieże Hanoi

Na wykładzie były wieże Hanoi. Proponuję zrobić takie zadania wariantowe:

1. Wieże Hanoi z zabronionym przejściem między wieżą 1 i 2.

2. Wieże Hanoi z zabronionym przejściem między wieżą 1-->2, 2-->3, 3-->1, czyli można tylko w jednym kierunku przenosić krążki

3. Wieże Hanoi z zabronionym przejściem między wieżą 1-->3 oraz 3-->1, czyli wieża 1 i 3 mają kontakt jedynie z 2 i wszelki transfer między nimi musi odbywać się przez pośrednika.

4. Wieże Hanoi ogólne z informacją z której wieży na którą można przenosić zadaną za pomocą logicznej tablicy dasie[i,j] dla i,j=1,2,3.

Ćwiczenia 22: (Listy 2)

Zadanie 1

Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy l, aż pozostanie w niej tylko jeden element. Liczenie rozpoczynamy od elementu wskazywanego przez l.

Dodatkowe warianty:

  • który z kolei wyleci interesujący nas numer j?
  • jaki numer bedzie m-ty od końca? (podstawowe zadanie jest dla m=1)

Zadanie 2

Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).

Zadanie 3

Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.

Zadanie 4

Napisz funkcję która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.

Ćwiczenia 22: Listy (2)

Zadanie 1

Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy l, aż pozostanie w niej tylko jeden element. Liczenie rozpoczynamy od elementu wskazywanego przez l.

Zadanie 2

Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).

Zadanie 3

Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.

Zadanie 4

Napisz funkcję która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.

Ćwiczenie 17: Rekursja (2)

Zadanie główne

Napisz procedurę, która wypisze dla zadanej liczby n jej wszystkie rozkłady na sumy liczb naturalnych większych od zera ustawionych w kolejności nierosnącej.
Np. dla n = 3:
3 = 3
3 = 2+1
3 = 1+1+1

Wskazówka 1
Użyj dodatkowej tablicy do przechowywania początków rozkładów. Uważaj, aby nie kopiować tej tablicy przy każdym wywołaniu rekurencyjnym!

Wskazówka 2
Funkcja rekurencyjna powinna mieć parametr wskazujący jak duże składniki mogą być użyte do rozkładu pozostałej liczby.

Zadanie 2

Analogicznie, tylko że interesuje nas liczba podziałów na sumy składników będących liczbami Fibonacciego. Można oczywiscie zawczasu stablicować sobie liczby Fibonacciego. To będzie rzecz jasna prosta modyfikacja podanego rozwiązania.

Zadanie 3

Analogicznie, tylko że liczby Fibonacciego muszą być różne.

Ćwiczenia 18: Binaria (1)

Zaczynamy od reprezentacji liczb całkowitych. Przyjmijmy jako podstawowe jednobajtowe liczby w kodzie U2. Zadania:

1. Znajdź reprezentację binarną w U2 liczb (przykładowo:)
0 00000000
4 00000100
-4 11111100
-1 11111111
127 01111111
-127 10000001
-128 10000000

2. Jaką liczbę reprezentują (przykładowo)
00000101 5
01010101 85
10101010 -86 (jak się doda do poprzedniej to wyjdzie -1)

3. Liczby wymierne: znajdź reprezentację okresową liczb
1/128 0.0000001(0)
3/128 0.0000011(0)
1/7 0.(001)
3/11 0.(0100010111)
7/13 0.(1000010011101)

4. Liczby w kodzie binarnym o podstawie (-2)
Znajdź reprezentację w tym kodzie liczb z przedziału (-20..20):
+ -
0 0
1 1 11
2 110 10
3 111 1101
4 100 1100
5 101 1111
6 11010 1110
7 11011 1001
8 11000 1000
9 11001 1011
10 11110 1010
11 11111 110101
12 11100 110100
13 11101 110111
14 10010 110110
15 10011 110001
16 10000 111000
17 10001 111011
18 10110 111010
19 10111 111101
20 10100 111100
itd. Warto zwrócić uwagę na urodę reprezentacji liczb 11 oraz -10. :)

5. Napisz algorytm znajdujący taką reprezentację dla dowolnej liczby całkowitej
6. Napisz algorytm dodający jedynkę do liczby zapisanej w tym układzie - reprezentujemy liczbę w tablicy bitowej.
7. Porównaj dwie liczby dane w dwóch tablicach bitowych
8. Zaneguj liczbę zamazując wynikiem oryginalną wartość w tablicy bitowej

Ćwiczenia 19: Binaria (2)

Zaczynamy od przykładów reprezentowania liczb w notacji zmiennopozycyjnej z wykładu (jest opisana na ważniaku), czyli 3 bity na cechę i 4 na mantysę bez ukrywania bitu 1/2 i z roznormalizowaniem wartości dla najmniejszej cechy 100 (chodzi o to, że przy najmniejszej cesze pozwalamy na mantysy mniejsze co do modułu od 1/2; nie tracimy w ten sposób jednoznaczności zapisu liczby, bo i tak mniejszej cechy nie ma).

Zaczynamy od prostych ułamków skończonych. Przedstaw w podanej reprezentacji możliwie dobre przybliżenia liczb:

5/8
5/16
5/128
5/256
5/512
5/1024
5/2028 (czyli zero)

Potem ułamki okresowe:

2/7:
3/7:
1/5
1/10
1/11
1/13

Dalej ćwiczymy dodawanie
1/11 + 1/13 =
1/13+5/8 =

Następnie robimy zadania 1-3 z wazniaka: http://wazniak.mimuw.edu.pl/index.php?title=Wstęp_do_programowania/Reprezentacja_liczb/Ćwiczenia. Omawiamy błąd względny wykonanych obliczeń i zauważamy, że jest on rzędu 2^{-t}

Ćwiczenia 20: wskaźniki

Zadanie 1 (Tablica wskaźników do tablic)

Zaimplementuj strukturę danych reprezentującą ciąg liczb z operacjami:

  1. wstaw liczbę na koniec ciągu,
  2. pobierz (usuwając) pierwszą liczbę ciągu.

Użyj w tym celu tablicy wskaźników do tablic, gdzie tablice składowe są przydzielane i zwalniane w miarę potrzeby (zaletą tej implementacji jest to, że dość elastycznie dostosowuje się do aktualnego rozmiaru ciągu, nie wymagając tylu wskaźników co zwykła lista).


Zadanie 2 (Haszowanie)

Zaimplementuj strukturę danych z operacjami:

  1. Wstaw(klucz: integer; var d: Dane); (var zwiększa efektywność)
  2. Daj(var klucz: integer; var d: Dane);

Wstaw wstawia do struktury danych parę (klucz, napis) lub (klucz,
liczba), gdzie napis jest typu string, zaś liczba typu integer.
Podaj stosowną deklarację dla typu Dane. Do przechowywania informacji
użyj tablicy [0..N] elementów odpowiedniego typu. Wstawianie ma polegać na obliczeniu klucz mod (N+1); jeśli pod tym indeksem jest wolne miejsce (-1), to wstawiamy, w przeciwnym przypadku szukamy liniowo (cyklicznie) pierwszego wolnego miejsca. Wyszukiwanie analogicznie. Zakładamy, że nigdy nie będzie wkładane więcej niż N elementów (to m.in. upraszcza wyszukiwanie indeksu dla danego klucza, zawsze jest co najmniej jedno wolne miejsce).


Zadanie 3 (New i dispose dla typu T)

Zaimplementuj własne operacje new i delete dla elementów typu T. Użyj w tym celu tablicy [1..N] zawierającej rekordy z dwoma wariantami:

  1. pole typu T
  2. pole(-a) z pewnymi dodatkowymi informacjami (jakimi?)

Wskazówka 1


Zadanie 4 (Sortowanie tablicy wskaźników do napisów)

Dana jest tablica A typu array[1..N] of ^string. Posortuj tę tablicę, używając porządku leksykograficznego (słownikowego) na słowach. Załóż, że dana jest funkcja compare(s,t:string):boolean, która ma wartość true wtedy i tylko wtedy, gdy słowo s jest leksykograficznie mniejsze od słowa t.


Napisz funkcję znajdującą w zadanej tablicy A typu array[1..N] of integer, N > 0, maksymalną sumę segmentu (spójnego fragmentu tablicy). Przyjmujemy, że segment pusty ma sumę 0.

Ćwiczenia 21: Listy (1)

Zadanie 1. Utwórz listę z konkretnych 3 elementów, np 2,3,5.

zadanie 2: Utwórz listę zawierającą wartości z tablicy A[1..n] of integer.

Zadanie 3. Odwróć listę

Zadanie 4. Scalanie posortowanych list. Chodzi o przekierowanie wskaźników dwóch posortowanych list tak, aby powstała jedna posortowana lista.

Zadanie 5. Napisz procedurę Usuń(var l1:lista; l2:lista) która usunie z listy l1 wszystkie elementy z listy l2. Zakładamy, że listy l1 i l2 są posortowane niemalejąco.

Tutaj musimy ustalić, jak rozumiemy zadanie w zależności od tego, co robimy z elementami powtarzającymi się na jednej bądź drugiej liście.

a) Załóżmy najpierw, że usuwamy wszystkie elementy z l1, które mają choć jedną wspólną wartość z jakimś elementem l2.

b) A teraz usuńmy elementy na zasadzie odejmowania multizbiorów reprezentowanych przez te listy, czyli z listy l1 usuwamy tylko tyle wartości, ile ich jest na l2.

Zadanie 6. Flaga holenderska na liście
Niech czerwone, to są elementy ujemne, białe równe zero, a czerwone - dodatnie. Przestaw listę tak, aby wszystkie ujemne liczby poprzedzały zerowe, a te z kolei dodatnie.