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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Odstepy itp.
Daria (dyskusja | edycje)
154 edycje
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}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Metody_programowania_/_Ćwiczenia_3&oldid=17295”