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

Jeśli po elemencie i indeksie j pojawi się element większy o indeksie j' większym od j, to element o indeksie j nie ma szans być rekordowym. Takim elementem nie ma się co przejmować, jako końcem potencjalnego rekordowego skoku.

Wskazówka 2

Przeglądając tablicę od tyłu wkładamy na stos kandydatów na bycie najlepszym j. Potem przeglądając tablicę od przodu wyliczamy k, zdejmując zużytych kandydatów na j ze stosu.

Rozwiązanie

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]
var s: stos;
    i,j,maks: integer;
begin
  Init(s);
  Push(s, A[N]);
  j:=N-1;
  while j >= 1 do  
   begin                        //wkładamy kandydatów na j na stos
    if A[j] > Top(s) then
      Push(s, A[j]);
      j:=j-1
   end;
  i:=1;
  maks:=0;
  while (i <= N) and (not Empty(s)) do     //dla każdego i szukamy najlepszego j; uaktualniamy maks
    if Top(s) >= A[i] then begin
      maks:=max(maks, Top(s)-i);
      Pop(s);
    end
    else 
      i:=i+1; 
  MaksOdległość:=maks;
  Destroy(s);
end;

Koszt czasowy: liniowy ze względu na długość tablicy

Koszt pamięciowy: liniowy ze względu na długość tablicy

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

Trzeba użyć przeszukiwania wszerz i kolejki w której trzymane będą pary składające się ze wskaźnika do węzła i głębokości węzła.

Rozwiązanie

type para = record
       drz: drzewo;
       poz: integer;
     end;

Typ kolejkaPar odpowiada kolejce w której trzymane są wartości typu para; poniżej jest on używany bez uprzedniej definicji.

function NajpłytszyLiść(d:drzewo): integer;
//Obliczamy głębokość najpłytszego liścia w drzewie d
var k:kolejkaPar;
    liść: integer;
    e,w: para;
begin
  if d = nil then NajpłytszyLiść:=0
  else begin
    Init(k);
    e.drz:=d;
    e.poz:=1;
    PutLast(k, e);
    liść:=0; 
    while (liść = 0) do begin                     //dopóki nie znaleźliśmy liścia kolejka nie może byc pusta
      GetFirst(k, w);
      l:=w.drz^.lsyn;
      p:=w.drz^.psyn;
      if l = nil and p = nil then liść:=w.poz
      else begin
        if l <> nil then begin                    //wstawiamy lewego syna do kolejki
          e.drz:=l
          e.poz:=w.poz+1;
          PutLast(k, e); 
        end;
        if p <> nil then begin                    //wstawiamy prawego syna do kolejki
          e.drz:=p
          e.poz:=w.poz+1;
          PutLast(k, e); 
        end;
    end;
    NajpłytszyLiść:=liść;
    Destroy(k);
  end;
end;

Koszt czasowy: liniowy ze względu na N

Koszt pamięciowy: liniowy ze względu na N

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

Zastosujmy k-krotne sortowanie kubełkowe: przeglądamy ciąg liczb patrząc na i-tą (i=k..1) cyfrę i wkładamy liczbę do właściwej kolejki. Po przejrzeniu ciągu kontynuujemy ze zmniejszonym o jeden i.

Rozwiązanie

procedure Sortuj(N:integer; var A: array[1..N] of liczba);
//Sortujemy tablicę liczb k-cyfrowych 
var T: array[0..9] of kolejka;
    B: array[1..N] of liczba;
    i,j,maks: integer;
function i_taCyfra(x,i:Integer):Integer;
//wyznacza i-tą cyfrę liczby x
var j:Integer;
begin
 for j:=1 to i-1 do x:=x div 10; 
 //Tu zamiast pętli można by użyć dzielnika pobranego z tablicy potęg 10 raz ustawionej na początku działania programu
 i_taCyfra:=x mod 10
end; 
 
begin
  for c:=0 to 9 do Init(T[c]);
  for j:=1 to N do PutLast(T[i_taCyfra(A[j],1)], j);
  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 znaczącej cyfry
  //Na końcu każdej kolejki jest -1 żeby wiedzieć kiedy zmniejszyć i
  for i:=2 to k do 
    for c:=0 to 9 do begin
      repeat
        GetFirst(T[c], l);
        if l <> -1 then PutLast(T[i_taCyfra(l,i)], l);
      until l = -1;
      for c:=0 to 9 do PutLast(T[c], -1);
    end; 
  //W kolejkach w tablicy T liczby są już posortowane
  //Trzeba je w tej kolejności umieścić w A; używamy pomocniczej tablicy B   
  j:=1;
  for c:=0 to 9 do 
    repeat
      GetFirst(T[c], l);
      if l <> -1 then begin
        B[j]:=A[l];
        j:=j+1;
      end;
    until l = -1;
  for j:=1 to N do A[j]:=B[j];
  for c:=0 to 9 do Destroy(T[c]);   
end;

Koszt czasowy: rzędu N*k

Koszt pamięciowy: liniowy względem N

Uwaga: Koszt pamięciowy związany jest z zawartościa kolejek w T i z pomocniczą tablicą B (obie rzędu N).