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

function PoprawneNawiasy: boolean;
//Sprawdzamy czy wyrażenie nawiasowe otrzymane przez kolejne wartości funkcji DajZnak jest poprawne
var s: stos;
    ok: boolean;
begin
  Init(s);
  ok:=true;
  repeat
    z:=DajZnak;
    case z of
      -1: Push(s, -1);
      -2: Push(s, -2);
       1: if not Empty(s) then
            if Top(s) = -1 then Pop(s)
            else ok:=false
          else ok:=false;
       2: if not Empty(s) then
            if Top(s) = -2 then Pop(s)
            else ok:=false
          else ok:=false;
       0: if not Empty(s) then ok:=false;
    end {case}
  until (z = 0) or (not ok)
  PoprawneNawiasy:=ok;
  Destroy(s);
end;

Koszt czasowy: liniowy ze względu na długość wyrażenia nawiasowego

Koszt pamięciowy: liniowy ze względu na długość wyrażenia nawiasowego

Ćwiczenie 1

Czy dodanie następnych typów nawiasów istotnie zmieniłoby rozwiązanie ?

Ćwiczenie 2

Jak wygląda optymalne rozwiązanie dla jednego typu nawiasów ?

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}}}