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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Poprawki do zadan na drzewa)
 
(Nie pokazano 20 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
To są zadania na drzewa. Przyjmujemy następujące definicje:
+
To są zadania na drzewa.  
  '''type''' el_drzewa = record
+
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Oglądaj wskazówki i rozwiązania __SHOWALL__<br>
 +
Ukryj wskazówki i rozwiązania __HIDEALL__
 +
</div>
 +
 
 +
Przyjmujemy następujące definicje:
 +
  '''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)==
 
Napisz funkcję która oblicza liczbę liści w drzewie.
 
Napisz funkcję która oblicza liczbę liści w drzewie.
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<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
 
  //Liczymy liczbe liści w drzewie
Linia 25: Linia 35:
  
 
''Omówienie:'' Koszt pamięciowy jest oczywiście związany z wielkością stosu wywołań rekurencyjnych
 
''Omówienie:'' Koszt pamięciowy jest oczywiście związany z wielkością stosu wywołań rekurencyjnych
 +
 +
[[pimp:modul3m_1_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
==Zadanie 2 (Odbicie lustrzane)==
 
==Zadanie 2 (Odbicie lustrzane)==
 
Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.
 
Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''procedure''' Lustro(d: drzewo);
 
  '''procedure''' Lustro(d: drzewo);
 
  //Przekształcamy d na swoje odbicie lustrzane
 
  //Przekształcamy d na swoje odbicie lustrzane
Linia 47: Linia 61:
  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 +
 +
[[pimp:modul3m_2_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
==Zadanie 3 (Izomorfizm drzew)==
 
==Zadanie 3 (Izomorfizm drzew)==
 
Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).
 
Napisz funkcję sprawdzającą czy dwa zadane drzewa są izomorficzne (mają taki sam kształt).
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<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
 
  //Sprawdzamy czy d1 i d2 mają taki sam kształt
Linia 71: Linia 89:
  
 
''Koszt pamięciowy:'' liniowy ze względu na minimum z wysokości drzew
 
''Koszt pamięciowy:'' liniowy ze względu na minimum z wysokości drzew
 +
 +
[[pimp:modul3m_3_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
==Zadanie 4 (Lista liści)==
 
==Zadanie 4 (Lista liści)==
Linia 81: Linia 102:
 
               end;
 
               end;
 
     drzewoL = ^węzeł;
 
     drzewoL = ^węzeł;
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Najwygodniej zrobić to obchodząc drzewo od prawej strony w lewo.
 
Najwygodniej zrobić to obchodząc drzewo od prawej strony w lewo.
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' ListaLiści(d: drzewoL): drzewoL;
 
  '''function''' ListaLiści(d: drzewoL): drzewoL;
 
  //Wynikiem funkcji jest wskaźnik do listy liści (od prawej do lewej) w drzewie d
 
  //Wynikiem funkcji jest wskaźnik do listy liści (od prawej do lewej) w drzewie d
Linia 114: Linia 138:
  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 +
 +
[[pimp:modul3m_4_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
==Zadanie 5 (Szerokość drzewa)==
 
==Zadanie 5 (Szerokość drzewa)==
 
Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.
 
Napisz funkcję obliczającą szerokość drzewa, czyli maksymalną liczbę wierzchołków na jednym poziomie.
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Najłatwiej to zrobić obchodząc drzewo wszerz; ale taniej jest gdy dla każdego poziomu będziemy pamiętać dotychczas odwiedzoną liczbę wierzchołków na tym poziomie. Do tego celu potrzebna jest lista.
 
Najłatwiej to zrobić obchodząc drzewo wszerz; ale taniej jest gdy dla każdego poziomu będziemy pamiętać dotychczas odwiedzoną liczbę wierzchołków na tym poziomie. Do tego celu potrzebna jest lista.
 
</div>
 
</div>
</div>}}
+
</div>
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Szerokość(d: drzewo): integer;
 
  '''function''' Szerokość(d: drzewo): integer;
 
  //Oblicza maksymalną liczbę wierzchołków na jednym poziomie drzewa d
 
  //Oblicza maksymalną liczbę wierzchołków na jednym poziomie drzewa d
Linia 134: Linia 163:
 
  '''begin'''
 
  '''begin'''
 
   '''if''' d <> nil '''then'''
 
   '''if''' d <> nil '''then'''
     '''if''' (d^.lsyn <> nil) '''or''' (d^.psyn = nil) '''then''' '''begin'''  //jeśli d to lisć
+
     '''if''' l = nil '''then''' '''begin'''     
      '''if''' l = nil '''then''' '''begin'''     
+
      new(l);
        new(l);
+
      l^.w:=0;
        l^.w:=0;
+
      l^.nast:=nil;
        l^.nast:=nil;
 
      '''end''';
 
      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''';
 +
    l^.w:=l^.w+1;                                    //zwiększamy licznik liści na tym poziomie
 +
    Obejdź(d^.lsyn, l^.nast);                        //obchodzimy lewe i prawe poddrzewa
 +
    Obejdź(d^.psyn, l^.nast);
 
  '''end''';
 
  '''end''';
 
  '''begin''' //Szerokość
 
  '''begin''' //Szerokość
Linia 164: Linia 189:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
</div>
 
</div>
</div>}}
+
</div>
  
 
==Zadanie 6 (Średnica drzewa)==
 
==Zadanie 6 (Średnica drzewa)==
 
Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.
 
Napisz funkcję obliczającą średnicę drzewa. Średnica to maksymalna odległość między dwoma wierzchołkami.
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
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.
 
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>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 +
<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
 
  //Obliczamy maksymalną odległość między dwoma wierzchołkami w d
Linia 204: Linia 233:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa (rekurencja)
 
</div>
 
</div>
</div>}}
+
</div>
  
 
==Zadanie 7 (Sprawdzanie czy drzewo jest BST)==
 
==Zadanie 7 (Sprawdzanie czy drzewo jest BST)==
 
Napisz funkcję sprawdzającą czy drzewo jest [[drzewem BST]].
 
Napisz funkcję sprawdzającą czy drzewo jest [[drzewem BST]].
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<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ść w tym poddrzewie.
 
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>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' CzyBST1(d: drzewo): boolean;
 
  '''function''' CzyBST1(d: drzewo): boolean;
 
  //Sprawdzamy czy d jest drzewem BST
 
  //Sprawdzamy czy d jest drzewem BST
Linia 258: Linia 291:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
</div>
 
</div>
</div>}}
+
</div>
  
  
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Można też  skorzystać z następującej własności drzew BST: w obiegu infiksowym wartości tworzą ciąg rosnący.
 
Można też  skorzystać z następującej własności drzew BST: w obiegu infiksowym wartości tworzą ciąg rosnący.
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' CzyBST2(d: drzewo): boolean;
 
  '''function''' CzyBST2(d: drzewo): boolean;
 
  //Sprawdzamy czy d jest drzewem BST
 
  //Sprawdzamy czy d jest drzewem BST
Linia 272: Linia 309:
 
     pierwsza, dobrze: boolean;
 
     pierwsza, dobrze: boolean;
 
  '''procedure''' Obejdź(d: drzewo):   
 
  '''procedure''' Obejdź(d: drzewo):   
  //Obejdź obchodzi d infiksowo; jeśli d jest liściem to porównuje d^.w z wartością z poprzedniego liścia
+
  //Obejdź obchodzi d infiksowo; dla kazdego węzła d, poównujemy d^.w z ostatnio odwiedzoną wartością
  //która mamy zapamiętaną w zmiennej globalnej ost
+
  //obiegu infiksowego, którą mamy zapamiętaną w zmiennej globalnej ost.
 
  //Wyjątkiem jest sytuacja gdy pierwsza=true, czyli gdy nie mamy jeszcze zapamiętanej żadnej wartości
 
  //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
+
  //dobrze oznacza że dotychczas odwiedzone węzły tworzą ciąg rosnący
 
  '''begin'''
 
  '''begin'''
   '''if''' dobrze '''and''' d <> nil '''then'''
+
   '''if''' dobrze '''and''' (d <> nil) '''then'''
    '''if''' d^.lsyn = nil '''and''' d^.psyn = nil '''then'''
+
    '''begin'''
      '''if''' pierwsza '''then''' '''begin'''
+
        Obejdź(d^.lsyn);
        pierwsza:=false;
+
        '''if''' pierwsza then  
        ost:=d^.w;
+
        '''begin''' ost:=d^.w //pierwszy element może być dowolny
      '''end'''
+
            pierwsza:=false
      '''else'''  
+
        '''end'''
        dobrze:=(ost < d^.w);
+
        '''else''' dobrze:=dobrze and (ost < d^.w);
    '''else''' '''begin'''
+
        '''if''' dobrze then '''begin''' //ucinamy rekursję tak wcześnie, jak się da!
      Obejdź(d^.lsyn);
+
          ost:=d^.w;
      Obejdź(d^.psyn);  
+
          Obejdź(d^.psyn);  
    '''end;     
+
        '''end''';     
 +
    '''end''';
 
  '''end''';
 
  '''end''';
 
  '''begin''' //CzyBST2
 
  '''begin''' //CzyBST2
Linia 301: Linia 339:
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
''Koszt pamięciowy:'' liniowy ze względu na wysokość drzewa  
 
</div>
 
</div>
</div>}}
+
</div>

Aktualna wersja na dzień 21:58, 28 maj 2020

To są zadania na drzewa.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

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

Zadanie 2 (Odbicie lustrzane)

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

Rozwiązanie

Zadanie 3 (Izomorfizm drzew)

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

Rozwiązanie

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

Rozwiązanie

Zadanie 5 (Szerokość drzewa)

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

Wskazówka

Rozwiązanie

Zadanie 6 (Średnica drzewa)

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

Wskazówka

Rozwiązanie

Zadanie 7 (Sprawdzanie czy drzewo jest BST)

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

Wskazówka 1

Rozwiązanie 1


Wskazówka 2

Rozwiązanie 2