Metody programowania / Ćwiczenia 4

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

{{{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 obliczy maksymalne k, takie że k=j-i, 1 ≤ i ≤ j ≤ N, A[j] ≥ A[i].

Wskazówka 1

{{{3}}}

Wskazówka 2

{{{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 jednoelementowego 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, najbardziej znaczący bit jest pod indeksem 1.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}