Metody programowania / Ćwiczenia 4: Różnice pomiędzy wersjami
| Linia 193: | Linia 193: | ||
'''begin''' | '''begin''' | ||
'''for''' c:=0 '''to''' 9 '''do''' Init(T[c]); | '''for''' c:=0 '''to''' 9 '''do''' Init(T[c]); | ||
'''for''' j:=1 '''to''' N '''do''' PutLast(T[A[j] | '''for''' j:=1 '''to''' N '''do''' PutLast(T[i_taCyfra(A[j],1)], j); | ||
'''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | '''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | ||
//Liczby z A (a raczej ich indeksy w A) są umieszczone w kolejkach tablicy T względem najbardziej | //Liczby z A (a raczej ich indeksy w A) są umieszczone w kolejkach tablicy T względem najbardziej znaczącej cyfry | ||
//Na końcu każdej kolejki jest -1 żeby wiedzieć kiedy zmniejszyć i | //Na końcu każdej kolejki jest -1 żeby wiedzieć kiedy zmniejszyć i | ||
'''for''' i:= | '''for''' i:=2 '''to''' k '''do''' | ||
'''for''' c:=0 '''to''' 9 '''do''' '''begin''' | '''for''' c:=0 '''to''' 9 '''do''' '''begin''' | ||
'''repeat''' | '''repeat''' | ||
GetFirst(T[c], l); | GetFirst(T[c], l); | ||
'''if''' l <> -1 '''then''' PutLast(T[ | '''if''' l <> -1 '''then''' PutLast(T[i_taCyfra(l,i)], l); | ||
'''until''' l = -1; | '''until''' l = -1; | ||
'''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | '''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | ||
Wersja z 13:11, 5 sty 2011
To są zadania na kolejki i stosy.
Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__
Przyjmijmy następujące definicje, gdzie typ lista był zdefiniowany w Ćwiczeniach 2.
type stos = lista;
kolejka = record
pocz, kon : lista;
end;
Dla stosów dostępne są następujące funkcje i procedury:
procedure Init(var s:stos); //tworzy pusty stos s procedure Push(var s:stos; w:integer); //wstawia w na wierzchołek stosu procedure Pop(var s:stos); //zdejmuje wierzchni element stosu function Top(s:stos): integer; //wyznacza wartość na wierzchołku stosu function Empty(s:stos): boolean; //sprawdza czy stos jest pusty procedure Destroy(s:stos); //niszczy stos (zwalnia pamięć)
Dla kolejek dostępne są następujące funkcje i procedury:
procedure Init(var k:kolejka); //tworzy pustą kolejkę k procedure PutLast(var k:kolejka; w:integer); //wstawia w na koniec kolejki procedure GetFirst(var k:kolejka; var w:integer); //usuwa pierwszy element kolejki i zapisuje na w function Empty(k:kolejka): boolean; //sprawdza czy kolejka jest pusta procedure Destroy(k:kolejka); //niszczy kolejkę (zwalnia pamięć)
Zadanie 1 (Poprawność wyrażeń nawiasowych)
Napisz funkcję sprawdzającą czy zadane wyrażenie nawiasowe składające się z nawiasów okrągłych i kwadratowych jest poprawne. Zakładamy, że dana jest funkcja DajZnak:integer, która przyjmuje następujące wartości: -1 dla (, 1 dla ), -2 dla [, 2 dla ] i 0 na oznaczenie końca wyrażenia nawiasowego.
Rozwiązanie 1
Ćwiczenie 1
Ćwiczenie 2
Zadanie 2 (Maksymalnie odległy porządek)
Napisz funkcję która dla danej tablicy A typu array[1..N] of integer obliczy maksymalne k, takie że k=j-i, 1 ≤ i ≤ j ≤ N, A[j] ≥ A[i].
Wskazówka 1
Wskazówka 2
Rozwiązanie 1
Zadanie 3 (Najpłytszy liść w drzewie)
Napisz funkcję która dla danego drzewa (definicja typu w MP Ćwiczenia2) obliczy głębokość najpłytszego (najbliższego korzeniowi) liścia. Dla drzewa pustego wynikiem powinno być zero, a dla jednoelementowanego jeden.
Wskazówka 1
Rozwiązanie 1
Zadanie 4 (Sortowanie liczb k-cyfrowych)
Zaimplementuj algorytm sortowania tablicy A typu array[1..N] of liczba dziesiętnych liczb k-cyfrowych przy użyciu tablicy dziesięciu kolejek. Typ liczba to array[1..k] of integer, najbardziej znaczący bit jest pod indeksem 1.
Wskazówka 1
Rozwiązanie 1
