Metody programowania / Ćwiczenia 3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Odstepy itp.)
(Poprawki do zadan na drzewa)
Linia 1: Linia 1:
 
To są zadania na drzewa. Przyjmujemy następujące definicje:
 
To są zadania na drzewa. Przyjmujemy następujące definicje:
 
  '''type''' el_drzewa = record
 
  '''type''' el_drzewa = record
                        w: integer;
+
                    w: integer;
                        lsyn, psyn: ^el_drzewa;
+
                    lsyn, psyn: ^el_drzewa;
                        end;
+
                  end;
          drzewo = ^el_drzewa;
+
        drzewo = ^el_drzewa;
 
 
  
 
==Zadanie 1 (Liczba liści w drzewie)==
 
==Zadanie 1 (Liczba liści w drzewie)==
Linia 12: Linia 11:
 
{{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''' LiczbaLiści(d: drzewo): integer;
 
  '''function''' LiczbaLiści(d: drzewo): integer;
 +
//Liczymy liczbe liści w drzewie
 
  '''begin'''
 
  '''begin'''
 
   '''if''' d = nil '''then''' LiczbaLiści:=0
 
   '''if''' d = nil '''then''' LiczbaLiści:=0
Linia 27: Linia 27:
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 
  
 
==Zadanie 2 (Odbicie lustrzane)==
 
==Zadanie 2 (Odbicie lustrzane)==
Linia 34: Linia 33:
 
{{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''' Lustro(d: drzewo);
 
  '''procedure''' Lustro(d: drzewo);
 +
//Przekształcamy d na swoje odbicie lustrzane
 
  '''var''' pom: drzewo;
 
  '''var''' pom: drzewo;
 
  '''begin'''
 
  '''begin'''
Linia 49: Linia 49:
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 
  
 
==Zadanie 3 (Izomorfizm drzew)==
 
==Zadanie 3 (Izomorfizm drzew)==
Linia 56: Linia 55:
 
{{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''' Izomorficzne(d1,d2: drzewo): boolean;
 
  '''function''' Izomorficzne(d1,d2: drzewo): boolean;
 +
//Sprawdzamy czy d1 i d2 mają taki sam kształt
 
  '''var''' i: boolean;
 
  '''var''' i: boolean;
 
  '''begin'''
 
  '''begin'''
Linia 70: Linia 70:
 
''Koszt czasowy:'' liniowy ze względu na sumę wielkości drzew
 
''Koszt czasowy:'' liniowy ze względu na sumę wielkości drzew
  
''Koszt pamięciowy:'' liniowy ze względu na minimum z wysokości drzew (rekurencja)
+
''Koszt pamięciowy:'' liniowy ze względu na minimum z wysokości drzew
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 
  
 
==Zadanie 4 (Lista liści)==
 
==Zadanie 4 (Lista liści)==
Napisz funkcję wiążącą liście drzewa w listę (od lewej do prawej). Wynikiem funkcji jest wskaźnik do utworzonej listy. Zakładamy, że każdy węzeł ma dodatkowe pole będące wskaźnikiem do węzła, czyli używamy typów
+
Napisz funkcję wiążącą liście drzewa w listę (od lewej do prawej). Wynikiem funkcji ma być wskaźnik do utworzonej listy. Zakładamy, że każdy węzeł ma dodatkowe pole będące wskaźnikiem do węzła, czyli używamy typów
 
  '''type''' węzeł = record
 
  '''type''' węzeł = record
                        w: integer;
+
                w: integer;
                        lsyn, psyn, nast: ^węzeł;
+
                lsyn, psyn, nast: ^węzeł;
                        end;
+
              end;
          drzewoL = ^węzeł;
+
    drzewoL = ^węzeł;
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Linia 90: Linia 89:
 
{{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''' ListaLiści(d: drzewoL): drzewoL;
 
  '''function''' ListaLiści(d: drzewoL): drzewoL;
  '''var''' l: drzewoL;
+
//Wynikiem funkcji jest wskaźnik do listy liści (od prawej do lewej) w drzewie d
  '''procedure''' Lista(d: drzewoL);   
+
  '''var''' l: drzewoL; //dotychczas obliczona lista liści
 +
  '''procedure''' Lista(d: drzewoL);  
 +
//Jeśli węzeł d jest liściem to dopisujemy go z przodu listy l 
 +
  //l jest zmienną globalną dla procedury Lista
 
  '''begin'''
 
  '''begin'''
 
   '''if''' d <> nil '''then'''  
 
   '''if''' d <> nil '''then'''  
Linia 114: Linia 116:
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 
  
 
==Zadanie 5 (Szerokość drzewa)==
 
==Zadanie 5 (Szerokość drzewa)==
Linia 126: Linia 127:
 
{{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''' Szerokość(d: drzewo): integer;
 
  '''function''' Szerokość(d: drzewo): integer;
  '''var''' l, pom: lista
+
//Oblicza maksymalną liczbę wierzchołków na jednym poziomie drzewa d
  '''procedure''' Obejdź(d: drzewo; l:lista);   
+
  '''var''' l, pom: lista;
  //Zakładamy, że d <> nil, a l <> nil odpowiada poziomowi na którym jest d   
+
    maks: integer;   
 +
  '''procedure''' Obejdź(d: drzewo; var l:lista);   
 +
  //Wskaźnik l odpowiada poziomowi na którym jest d; jeśli l = nil to trzeba listę poziomów wydłużyć  
 
  '''begin'''
 
  '''begin'''
  l^.w:=l^.w+1;
+
   '''if''' d <> nil '''then'''
   '''if''' l^.nast = nil '''and''' (d^.lsyn <> nil '''or''' d^.psyn <> nil) '''then''' '''begin'''
+
    '''if''' (d^.lsyn <> nil) '''or''' (d^.psyn = nil) '''then''' '''begin'''   //jeśli d to lisć
    new(l^.nast);
+
      '''if''' l = nil '''then''' '''begin'''   
    l^.nast^.w:=0;
+
        new(l);
    l^.nast^.nast:=nil;
+
        l^.w:=0;
  '''end''';
+
        l^.nast:=nil;
  '''if''' d^.lsyn <> nil '''then''' Obejdż(d^.lsyn, l^.nast);
+
      '''end''';
  '''if''' d^.psyn <> nil '''then''' Obejdż(d^.psyn, l^.nast);
+
      l^.w:=l^.w+1;                                     //zwiększamy licznik liści na tym poziomie
 +
    '''end'''
 +
    '''else''' '''begin'''                                         //jesli d nie jest liściem
 +
      Obejdź(d^.lsyn, l^.nast);                         //obchodzimy lewe i prawe poddrzewa
 +
      Obejdź(d^.psyn, l^.nast);
 +
    '''end''';
 
  '''end''';
 
  '''end''';
  '''begin''' //ListaLiści
+
  '''begin''' //Szerokość
  '''if''' d = nil '''then''' Szerokość:=0
+
   l:=nil;
   '''else''' '''begin'''
+
  Obejdź(d, l);
    new(l);
+
  maks:=0;                                             //szukamy maksimum na l i jednocześnie ją niszczymy
    l^.nast:=nil;
+
  '''while''' l <> nil '''do''' '''begin'''
    l^.w:=0;
+
    maks:=max(maks, l^.w);
    Obejdź(d,l);
+
    pom:=l;
    maks:=0;
+
    l:=l^.nast;
    '''while''' l <> nil '''do''' '''begin'''
+
    dispose(pom);
      maks:=max(maks, l^.w);
 
      pom:=l;
 
      l:=l^.nast;
 
      dispose(pom);
 
    '''end''';
 
    Szerokość:=maks;
 
 
   '''end''';
 
   '''end''';
 +
  Szerokość:=maks;
 
  '''end''';
 
  '''end''';
  
Linia 162: Linia 165:
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 
 
  
 
==Zadanie 6 (Średnica drzewa)==
 
==Zadanie 6 (Średnica drzewa)==
Linia 169: Linia 170:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Nazwijmy d wierzchołek średnicy położony najbliżej korzenia. Wtedy średnica składa się z najdłuższej ścieżki w lewym i w prawym poddrzewie d.
+
Niech d to wierzchołek średnicy położony najbliżej korzenia. Wtedy średnica składa się z najdłuższej ścieżki w lewym i w prawym poddrzewie d.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 175: Linia 176:
 
{{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''' Średnica(d: drzewo): integer;
 
  '''function''' Średnica(d: drzewo): integer;
 +
//Obliczamy maksymalną odległość między dwoma wierzchołkami w d
 
  '''var''' dl, maks: integer;
 
  '''var''' dl, maks: integer;
 
  '''function''' Ścieżki(d:drzewo; var dl, maks:integer);
 
  '''function''' Ścieżki(d:drzewo; var dl, maks:integer);
  //Na dl i maks są obliczne odpowiednio długość najdłuższej ścieżki w d i maksymalna średnica w d
+
  //Na dl i maks są obliczane odpowiednio długość najdłuższej ścieżki w d i maksymalna średnica w d
 +
//Dla d = nil ustalamy dl na -1 żeby dobrze obliczać dl dla liści 
 
  '''var''' dl1,dl2,m1,m2, pom: integer;
 
  '''var''' dl1,dl2,m1,m2, pom: integer;
 
  '''begin'''
 
  '''begin'''
Linia 202: Linia 205:
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 
  
 
==Zadanie 7 (Sprawdzanie czy drzewo jest BST)==
 
==Zadanie 7 (Sprawdzanie czy drzewo jest BST)==
Linia 208: Linia 210:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Sprawdzenie, że w każdym wierzchołku d^.lsyn^.w < d^.w < d^.psyn^.w nie wystarcza. Trzeba dla każdego poddrzewa wiedzieć jaka jest maksymalna i minimalna wartość tam występująca.
+
Sprawdzenie, że w każdym wierzchołku d^.lsyn^.w < d^.w < d^.psyn^.w nie wystarcza. Trzeba dla każdego poddrzewa wiedzieć jaka jest maksymalna i minimalna wartość w tym poddrzewie.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 214: Linia 216:
 
{{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''' CzyBST1(d: drzewo): boolean;
 
  '''function''' CzyBST1(d: drzewo): boolean;
 +
//Sprawdzamy czy d jest drzewem BST
 
  '''var''' mala, duza: integer;
 
  '''var''' mala, duza: integer;
 
  '''function''' Czy(d: drzewo; var mala,duza :integer): boolean;   
 
  '''function''' Czy(d: drzewo; var mala,duza :integer): boolean;   
Linia 232: Linia 235:
 
     mala:=d^.w;
 
     mala:=d^.w;
 
   '''end''';
 
   '''end''';
   '''if''' d^.psyn <> nil '''then''' '''begin'''  ///analogiczne sprawdzenie prawego poddrzewa
+
   '''if''' d^.psyn <> nil '''then''' '''begin'''  //analogiczne sprawdzenie prawego poddrzewa
 
     c2:=Czy(d^.psyn, m2, d2);
 
     c2:=Czy(d^.psyn, m2, d2);
 
     '''if''' c2 '''then''' '''begin'''
 
     '''if''' c2 '''then''' '''begin'''
Linia 265: Linia 268:
 
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
  '''function''' CzyBST2(d: drzewo): boolean;
 
  '''function''' CzyBST2(d: drzewo): boolean;
 +
//Sprawdzamy czy d jest drzewem BST
 
  '''var''' ost: integer;
 
  '''var''' ost: integer;
      pierwsza, dobrze: boolean;
+
    pierwsza, dobrze: boolean;
 
  '''procedure''' Obejdź(d: drzewo):   
 
  '''procedure''' Obejdź(d: drzewo):   
  //Obejdź obchodzi d infiksowo; w liściach porównuje ost-ostatnio napotkaną wartość z wartością w liściu; wyjątkiem jest sytuacja gdy pierwsza=true, czyli gdy nie mamy jeszcze zapamiętanej żadnej wartości
+
  //Obejdź obchodzi d infiksowo; jeśli d jest liściem to porównuje d^.w z wartością z poprzedniego liścia
  // dobrze oznacza że dotychczas odwiedzone liście tworzą ciąg rosnący
+
//która mamy zapamiętaną w zmiennej globalnej ost
 +
//Wyjątkiem jest sytuacja gdy pierwsza=true, czyli gdy nie mamy jeszcze zapamiętanej żadnej wartości
 +
  //dobrze oznacza że dotychczas odwiedzone liście tworzą ciąg rosnący
 
  '''begin'''
 
  '''begin'''
 
   '''if''' dobrze '''and''' d <> nil '''then'''
 
   '''if''' dobrze '''and''' d <> nil '''then'''

Wersja z 21:41, 14 sie 2006

To są zadania na drzewa. Przyjmujemy następujące definicje:

type el_drzewa = record
                   w: integer;
                   lsyn, psyn: ^el_drzewa;
                 end;
        drzewo = ^el_drzewa;

Zadanie 1 (Liczba liści w drzewie)

Napisz funkcję która oblicza liczbę liści w drzewie.

Rozwiązanie 1

{{{3}}}

Zadanie 2 (Odbicie lustrzane)

Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.

Rozwiązanie 1

{{{3}}}

Zadanie 3 (Izomorfizm drzew)

Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).

Rozwiązanie 1

{{{3}}}

Zadanie 4 (Lista liści)

Napisz funkcję wiążącą liście drzewa w listę (od lewej do prawej). Wynikiem funkcji ma być wskaźnik do utworzonej listy. Zakładamy, że każdy węzeł ma dodatkowe pole będące wskaźnikiem do węzła, czyli używamy typów

type węzeł = record
               w: integer;
               lsyn, psyn, nast: ^węzeł;
             end;
   drzewoL = ^węzeł;

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 5 (Szerokość drzewa)

Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 6 (Średnica drzewa)

Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Zadanie 7 (Sprawdzanie czy drzewo jest BST)

Napisz funkcję sprawdzającą czy drzewo jest drzewem BST.

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}


Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}