Metody programowania / Ćwiczenia 4: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
4 zadania na stosy i kolejki |
Poprawki w zadaniach na stosy |
||
| Linia 2: | Linia 2: | ||
'''type''' stos = lista; | '''type''' stos = lista; | ||
kolejka = record | |||
pocz, kon : lista; | |||
end; | |||
Dla stosów dostępne są następujące funkcje i procedury: | Dla stosów dostępne są następujące funkcje i procedury: | ||
| Linia 26: | Linia 26: | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
'''function''' PoprawneNawiasy: boolean; | '''function''' PoprawneNawiasy: boolean; | ||
//Sprawdzamy czy wyrażenie nawiasowe otrzymane | //Sprawdzamy czy wyrażenie nawiasowe otrzymane przez kolejne wartości funkcji DajZnak jest poprawne | ||
'''var''' s: stos; | '''var''' s: stos; | ||
ok: boolean; | ok: boolean; | ||
| Linia 63: | Linia 63: | ||
{{cwiczenie| 2|pytanko 2|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{cwiczenie| 2|pytanko 2|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
Jak wygląda optymalne | Jak wygląda optymalne rozwiązanie dla jednego typu nawiasów ? | ||
</div> | </div> | ||
</div>}} | </div>}} | ||
==Zadanie 2 (Maksymalnie odległy porządek)== | ==Zadanie 2 (Maksymalnie odległy porządek)== | ||
| Linia 76: | Linia 74: | ||
</div> | </div> | ||
</div>}} | </div>}} | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
'''function''' MaksOdległość(A:array[1..N] of integer): integer; | '''function''' MaksOdległość(N:integer; A:array[1..N] of integer): integer; | ||
//Obliczamy maksymalne k, takie że k=j-i, 1 <= i <= j <= N, A[j] >= A[i] | //Obliczamy maksymalne k, takie że k=j-i, 1 <= i <= j <= N, A[j] >= A[i] | ||
'''var''' s: stos; | '''var''' s: stos; | ||
| Linia 87: | Linia 84: | ||
Push(s, A[N]); | Push(s, A[N]); | ||
j:=N-1; | j:=N-1; | ||
'''while''' j >= 1 '''do''' | '''while''' j >= 1 '''do''' //wkładamy kandydatów na j na stos | ||
'''if''' A[j] > Top(s) '''then''' | '''if''' A[j] > Top(s) '''then''' | ||
Push(s, A[j]); | Push(s, A[j]); | ||
i:=1; | i:=1; | ||
maks:=0; | maks:=0; | ||
'''while''' (i <= N) and (not Empty(s)) '''do''' | '''while''' (i <= N) and (not Empty(s)) '''do''' //dla każdego i szukamy najlepszego j; uaktualniamy maks | ||
'''if''' Top(s) >= A[i] '''then''' '''begin''' | '''if''' Top(s) >= A[i] '''then''' '''begin''' | ||
maks:=max(maks, Top(s)-i); | maks:=max(maks, Top(s)-i); | ||
| Linia 109: | Linia 106: | ||
</div>}} | </div>}} | ||
==Zadanie 3 (Najpłytszy liść w drzewie)== | |||
==Zadanie 3 (Najpłytszy | |||
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. | 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. | ||
| Linia 117: | Linia 113: | ||
</div> | </div> | ||
</div>}} | </div>}} | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
| Linia 129: | Linia 122: | ||
'''function''' NajpłytszyLiść(d:drzewo): integer; | '''function''' NajpłytszyLiść(d:drzewo): integer; | ||
//Obliczamy | //Obliczamy głębokość najpłytszego liścia w drzewie d | ||
'''var''' k:kolejkaPar; | '''var''' k:kolejkaPar; | ||
liść: integer; | liść: integer; | ||
| Linia 141: | Linia 134: | ||
PutLast(k, e); | PutLast(k, e); | ||
liść:=0; | liść:=0; | ||
'''while''' | '''while''' (liść = 0) '''do''' '''begin''' //dopóki nie znaleźliśmy liścia kolejka nie może byc pusta | ||
GetFirst(k, w); | GetFirst(k, w); | ||
l:=w.drz^.lsyn; | l:=w.drz^.lsyn; | ||
p:=w.drz^.psyn; | p:=w.drz^.psyn; | ||
'''if''' l = nil '''and'' p = nil '''then''' liść:=w.poz | '''if''' l = nil '''and''' p = nil '''then''' liść:=w.poz | ||
'''else''' '''begin''' | '''else''' '''begin''' | ||
'''if''' l <> nil '''then''' '''begin''' | '''if''' l <> nil '''then''' '''begin''' //wstawiamy lewego syna do kolejki | ||
e.drz:=l | e.drz:=l | ||
e.poz:=w.poz+1; | e.poz:=w.poz+1; | ||
PutLast(k, e); | PutLast(k, e); | ||
'''end'''; | '''end'''; | ||
'''if''' p <> nil '''then''' '''begin''' | '''if''' p <> nil '''then''' '''begin''' //wstawiamy prawego syna do kolejki | ||
e.drz:=p | e.drz:=p | ||
e.poz:=w.poz+1; | e.poz:=w.poz+1; | ||
| Linia 168: | Linia 161: | ||
</div> | </div> | ||
</div>}} | </div>}} | ||
==Zadanie 4 (Sortowanie liczb k-cyfrowych)== | ==Zadanie 4 (Sortowanie liczb k-cyfrowych)== | ||
| Linia 179: | Linia 171: | ||
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
'''procedure''' Sortuj(var A: array[1..N] of liczba); | '''procedure''' Sortuj(N:integer; var A: array[1..N] of liczba); | ||
//Sortujemy tablicę liczb k-cyfrowych | //Sortujemy tablicę liczb k-cyfrowych | ||
'''var''' T: array[0..9] of kolejka; | '''var''' T: array[0..9] of kolejka; | ||
| Linia 188: | Linia 180: | ||
'''for''' j:=1 '''to''' N '''do''' PutLast(T[A[j]^[k]], j); | '''for''' j:=1 '''to''' N '''do''' PutLast(T[A[j]^[k]], j); | ||
'''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | '''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | ||
//Liczby (a raczej ich indeksy w | //Liczby z A (a raczej ich indeksy w A) są umieszczone w kolejkach tablicy T względem najbardziej znaczącego bitu | ||
//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:=k-1 '''to''' 1 '''do''' | '''for''' i:=k-1 '''to''' 1 '''do''' | ||
| Linia 198: | Linia 190: | ||
'''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | '''for''' c:=0 '''to''' 9 '''do''' PutLast(T[c], -1); | ||
'''end'''; | '''end'''; | ||
//W kolejkach w tablicy T liczby | //W kolejkach w tablicy T liczby są już posortowane | ||
//Trzeba je w tej kolejności umieścić w A; używamy pomocniczej tablicy B | //Trzeba je w tej kolejności umieścić w A; używamy pomocniczej tablicy B | ||
j:=1; | j:=1; | ||
| Linia 220: | Linia 212: | ||
</div> | </div> | ||
</div>}} | </div>}} | ||
Wersja z 22:02, 14 sie 2006
To są zadania na kolejki i stosy. Przyjmijmy następujące definicje, gdzie typ lista był zdefiniowany w MP Ćwiczenia1
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
{{{3}}}
Ćwiczenie 1
{{{3}}}
Ćwiczenie 2
{{{3}}}
Zadanie 2 (Maksymalnie odległy porządek)
Napisz funkcję która dla danej tablicy A typu array[1..N] of integer policzy maksymalne k, takie że k=j-i, 1 ≤ i ≤ j ≤ N, A[j] ≥ A[i].
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
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
{{{3}}}
Rozwiązanie 1
{{{3}}}
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, najmniej znaczący bit jest pod indeksem 1.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
