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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 44 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
 
To są zadania na listy.
 
To są zadania na listy.
 +
 +
<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>
  
 
W poniższych zadaniach będziemy używać następujących typów:
 
W poniższych zadaniach będziemy używać następujących typów:
  
  '''type''' el_listy = record  
+
  '''type''' lista = ^el_listy;
 +
      el_listy = '''record'''
 
                   w: integer;
 
                   w: integer;
                   nast: ^el_listy;
+
                   nast: lista;
                 end;
+
                 '''end''';
      lista = ^el_listy;
+
 
  
 
== Zadanie 1 (Odwracanie listy)==
 
== Zadanie 1 (Odwracanie listy)==
 
Napisz procedurę Odwróć(var l:lista) odwracającą listę l.
 
Napisz procedurę Odwróć(var l:lista) odwracającą listę l.
  
{{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">
 
  '''procedure''' Odwróć(var l:lista);
 
  '''procedure''' Odwróć(var l:lista);
 
  //Odwracamy listę l
 
  //Odwracamy listę l
Linia 27: Linia 35:
 
     '''end''';
 
     '''end''';
 
   '''end''';
 
   '''end''';
 +
  l:=poprz;
 
  '''end''';
 
  '''end''';
 
''Koszt czasowy'': liniowy względem długości listy
 
''Koszt czasowy'': liniowy względem długości listy
  
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 +
 +
[[pimp:modul2m_1_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
== Zadanie 2 (Scalanie dwóch posortowanych list)==
 
== Zadanie 2 (Scalanie dwóch posortowanych list)==
 
Napisz funkcję Scal(l1,l2:lista):lista scalającą dwie posortowane niemalejąco listy l1 i l2, tak aby wynikowa lista również była posortowana niemalejąco.
 
Napisz funkcję Scal(l1,l2:lista):lista scalającą dwie posortowane niemalejąco listy l1 i l2, tak aby wynikowa lista również była posortowana niemalejąco.
  
{{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''' Scal(l1,l2:lista): lista;
 
  '''function''' Scal(l1,l2:lista): lista;
 
  //Listy l1 i l2 są posortowane niemalejąco; scalamy je do jednej listy również posortowanej niemalejąco
 
  //Listy l1 i l2 są posortowane niemalejąco; scalamy je do jednej listy również posortowanej niemalejąco
Linia 45: Linia 59:
 
   atrapa^.nast:=nil;
 
   atrapa^.nast:=nil;
 
   akt:=atrapa;
 
   akt:=atrapa;
   '''while''' l1 <> nil and l2 <> nil '''do'''
+
   '''while''' (l1 <> nil) and (l2 <> nil) '''do'''
 
     '''if''' l1^.w < l2^.w '''then''' '''begin'''            //jeśli l1^.w < l2^.w
 
     '''if''' l1^.w < l2^.w '''then''' '''begin'''            //jeśli l1^.w < l2^.w
 
       akt^.nast:=l1;
 
       akt^.nast:=l1;
Linia 57: Linia 71:
 
         l2:=l2^.nast;
 
         l2:=l2^.nast;
 
       '''end'''
 
       '''end'''
       '''else''' '''begin'''                          //jeśli l1^.w = l2^.w
+
       '''else''' '''begin'''                          //jeśli l1^.w = l2^.w - ten else można sobie darować, i tak będzie dobrze
 
         akt^.nast:=l1;
 
         akt^.nast:=l1;
 
         akt:=akt^.nast;
 
         akt:=akt^.nast;
 +
        l1:=l1^.nast;
 
         akt^.nast:=l2;
 
         akt^.nast:=l2;
 
         akt:=akt^.nast;
 
         akt:=akt^.nast;
        l1:=l1^.nast;
 
 
         l2:=l2^.nast;
 
         l2:=l2^.nast;
 
       '''end''';
 
       '''end''';
   '''if''' l1 = nil '''then''' l1:=l2;
+
   '''if''' l1 = nil '''then'''                       //obsługa końcówki listy która nie jest pusta
  '''while''' l1 <> nil '''do''' '''begin'''              //obsługa końcówki listy która nie jest pusta
+
     akt^.nast:=l2
     akt^.nast:=l1;
+
  '''else'''
     akt:=akt^.nast;
+
     akt^.nast:=l1;                          
    l1:=l1^.nast;
 
  '''end''';
 
 
   Scal:=atrapa^.nast;
 
   Scal:=atrapa^.nast;
 
   dispose(atrapa);
 
   dispose(atrapa);
Linia 77: Linia 89:
  
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 +
 +
[[pimp:modul2m_2_1.html|Wizualizacja]]
 +
 
</div>
 
</div>
</div>}}
+
</div>
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{cwiczenie| 1|pytanko 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">Ćwiczenie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Czy instrukcja atrapa^.nast:=nil jest potrzebna? W jakich przypadkach ?
 
Czy instrukcja atrapa^.nast:=nil jest potrzebna? W jakich przypadkach ?
 
</div>
 
</div>
</div>}}
+
</div>
  
 
== Zadanie 3 (Usuwanie elementów zadanych listą)==
 
== Zadanie 3 (Usuwanie elementów zadanych listą)==
Napisz procedurę Usuń(var l1:lista; l2:lista) która  usunie z listy l1 wszystkie elementy z listy l2. Zakładamy, że listy l1 i l2 są  posortowanych niemalejąco.
+
Napisz procedurę Usuń(var l1:lista; l2:lista) która  usunie z listy l1 wszystkie elementy z listy l2. Zakładamy, że listy l1 i l2 są  posortowane niemalejąco.
 
+
<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''' Usuń(var l1:lista; l2:lista);
 
  '''procedure''' Usuń(var l1:lista; l2:lista);
 
  //Usuwamy z listy l1 wszystkie elementy z listy l2; zakładamy, że listy l1 i l2 są posortowane niemalejąco
 
  //Usuwamy z listy l1 wszystkie elementy z listy l2; zakładamy, że listy l1 i l2 są posortowane niemalejąco
Linia 96: Linia 113:
 
   atrapa^.nast:=l1;
 
   atrapa^.nast:=l1;
 
   poprz:=atrapa;
 
   poprz:=atrapa;
   '''while''' l1 <> nil and l2 <> nil '''do'''
+
   '''while''' (l1 <> nil) and (l2 <> nil) '''do'''
 
     '''if''' l1^.w < l2^.w '''then''' '''begin'''        //jeśli l1^.w < l2^.w  
 
     '''if''' l1^.w < l2^.w '''then''' '''begin'''        //jeśli l1^.w < l2^.w  
 
       l1:=l1^.nast;
 
       l1:=l1^.nast;
Linia 115: Linia 132:
  
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 +
 +
[[pimp:modul2m_3_1.html|Wizualizacja]]
 +
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
Czy lista l1 musi być przekazywana przez zmienną ? W jakich przypadkach jest to konieczne ?
 
</div>
 
</div>
</div>}}
 
 
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
Czy lista l1 musi być przekazywana przez zmienną ? W jakich przypadkach to jest konieczne ?
 
 
</div>
 
</div>
</div>}}
 
  
 
== Zadanie 4 (Uporządkowanie elementów w liście)==
 
== Zadanie 4 (Uporządkowanie elementów w liście)==
Napisz procedurę Uporządkuj(var l:lista) która  przestawi elementy w liście l tak by najpierw były elementy w których pole w jest ujemne, potem równe zero a potem dodatnie. Dodatkowo względna kolejność elelmentów jednego rodzaju (dodatnich, równych zero i ujemnych) powinna być zachowana.
+
Napisz procedurę Uporządkuj(var l:lista) która  przestawi elementy w liście l tak by najpierw były elementy w których pole w jest ujemne, potem równe zero, a na końcu dodatnie. Dodatkowo względna kolejność elementów jednego rodzaju (dodatnich, równych zero i ujemnych) powinna być zachowana.
 
+
<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''' Uporządkuj(var l:lista);
 
  '''procedure''' Uporządkuj(var l:lista);
  //Ustawiamy elementy listy l tak by najpierw były elemnty ujemne, potem równe zero, a na końcu dodatnie
+
  //Ustawiamy elementy listy l tak by najpierw były elementy ujemne, potem równe zero, a na końcu dodatnie
 +
//Osobno zbieramy elementy ujemne, dodatnie i równe zero i potem je łączymy
 
  '''var''' atrapau, atrapaz, atrapad, u, z, d : lista;
 
  '''var''' atrapau, atrapaz, atrapad, u, z, d : lista;
 
  '''begin'''
 
  '''begin'''
Linia 135: Linia 158:
 
   new(atrapad); d:=atrapad;  
 
   new(atrapad); d:=atrapad;  
 
   '''while''' l <> nil  '''do''' '''begin'''
 
   '''while''' l <> nil  '''do''' '''begin'''
     '''if''' l^.w < 0 '''then''' '''begin'''
+
     '''if''' l^.w < 0 '''then''' '''begin'''         //dołączamy l do listy u
 
       u^.nast:=l;
 
       u^.nast:=l;
 
       u:=u^.nast;
 
       u:=u^.nast;
 
     '''end'''
 
     '''end'''
 
     '''else'''  
 
     '''else'''  
       '''if''' l^.w = 0 '''then''' '''begin'''
+
       '''if''' l^.w = 0 '''then''' '''begin'''       //dołączamy l do listy z
 
         z^.nast:=l;
 
         z^.nast:=l;
 
         z:=z^.nast;
 
         z:=z^.nast;
 
       '''end'''   
 
       '''end'''   
       '''else''' '''begin'''
+
       '''else''' '''begin'''                   //dołączamy l do listy d
 
         d^.nast:=l;
 
         d^.nast:=l;
 
         d:=d^.nast;
 
         d:=d^.nast;
 
       '''end''';
 
       '''end''';
   d.^nast:=nil;
+
    l:=l^.nast;
 +
  '''end''';  //while
 +
   d^.nast:=nil;
 
   z^.nast:=atrapad^.nast;
 
   z^.nast:=atrapad^.nast;
 
   u^.nast:=atrapaz^.nast;
 
   u^.nast:=atrapaz^.nast;
Linia 159: Linia 184:
  
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 +
 +
[[pimp:modul2m_4_1.html|Wizualizacja]]
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
== Zadanie 5 (Problem Józefa Flawiusza)==
 
== Zadanie 5 (Problem Józefa Flawiusza)==
 
Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego  
 
Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego  
k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy, tak aby pozostał tylko jeden. Liczenie rozpoczynamy od elemnetu wskazywanego przez l.
+
k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy l, aż pozostanie w niej tylko jeden element. Liczenie rozpoczynamy od elementu wskazywanego przez l.
  
{{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">
 
  '''procedure''' Flawiusz(var l:lista; k:integer);
 
  '''procedure''' Flawiusz(var l:lista; k:integer);
  //Usuwamy z listy l cyklicznie co k-ty element dopóki nie zostanie 1; k>0, l niepusta cykliczna
+
  //Usuwamy z listy l cyklicznie co k-ty element dopóki nie zostanie jeden element; k>0, l niepusta cykliczna
  '''var''' atrapa, poprz: lista;
+
  '''var''' poprz, pom: lista;
 
  '''begin'''
 
  '''begin'''
 
   poprz:=l^.nast;
 
   poprz:=l^.nast;
   '''while''' poprz^.nast <> poprz '''do''' poprz:=poprz.^nast;
+
   '''while''' poprz^.nast <> l '''do''' poprz:=poprz^.nast;     //poprz wskazuje na element poprzedzający l
   '''while''' poprz <> poprz^.nast '''do''' '''begin'''
+
   '''while''' poprz <> poprz^.nast '''do''' '''begin'''               //dopóki lista ma więcej niz jeden element
     '''for''' i:=1 '''to''' k-1 '''do''' '''begin''' poprz:=poprz^.nast;
+
     '''for''' i:=1 '''to''' k-1 '''do''' poprz:=poprz^.nast;
    pom:=poprz^.nast;
+
      pom:=poprz^.nast;
 
     poprz^.nast:=pom^.nast;
 
     poprz^.nast:=pom^.nast;
 
     dispose(pom);     
 
     dispose(pom);     
Linia 184: Linia 214:
  
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 +
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
== Zadanie 6 (Listy łączące się)==
 
== Zadanie 6 (Listy łączące się)==
 
Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).
 
Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).
 
+
<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>
Jeśli listy mają wspólny element to ostatni niepusty element l1 i ostatni niepusty element l2 muszą byc takie same.
+
<div class="mw-collapsible-content" style="display:none">
 +
Jeśli listy mają wspólny element to ostatni niepusty element l1 i ostatni niepusty element l2 muszą być takie same.
 
</div>
 
</div>
 
</div>
 
</div>
}}
+
<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>
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Wspólny(l1, l2:lista):boolean;
 
  '''function''' Wspólny(l1, l2:lista):boolean;
 
  //Sprawdzamy czy listy proste l1 i l2 maja wspólny element
 
  //Sprawdzamy czy listy proste l1 i l2 maja wspólny element
Linia 214: Linia 246:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>
  
 
== Zadanie 7 (Pierwszy wspólny element list łączących się)==
 
== Zadanie 7 (Pierwszy wspólny element list łączących się)==
 
Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.
 
Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.
 
+
<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>
Pierwszy wspólny element jest tak samo odległy od końca list. Jeśli więc obliczymy długości list to możemy iść po nich równocześnie w takiej samej odległości od końca i sprawdzać czy trafiliśmy już na wspolny element czy nie.
+
<div class="mw-collapsible-content" style="display:none">
 +
Każdy wspólny element list jest tak samo odległy od końca list. Jeśli więc obliczymy długości list to możemy iść po nich równocześnie w takiej samej odległości od końca i sprawdzać czy trafiliśmy już na wspólny element czy nie.
 
</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''' PierwszyWspólny(l1, l2:lista):lista;
 
  '''function''' PierwszyWspólny(l1, l2:lista):lista;
 
  //Listy l1 i l2 maja wspólny element; szukamy pierwszego elementu wspólnego tych list
 
  //Listy l1 i l2 maja wspólny element; szukamy pierwszego elementu wspólnego tych list
Linia 231: Linia 265:
 
     pom1, pom2: lista;
 
     pom1, pom2: lista;
 
  '''begin'''
 
  '''begin'''
   dl1:=0; pom1:=l1;
+
   dl1:=0; pom1:=l1;              
   '''while''' pom1 <> nil '''do''' '''begin'''
+
   '''while''' pom1 <> nil '''do''' '''begin'''             //liczymy długość l1
 
     dl1:=dl1+1;
 
     dl1:=dl1+1;
 
     pom1:=pom1^.nast;
 
     pom1:=pom1^.nast;
 
   '''end''';  
 
   '''end''';  
 
   dl2:=0; pom2:=l2;
 
   dl2:=0; pom2:=l2;
   '''while''' pom2 <> nil '''do''' '''begin'''
+
   '''while''' pom2 <> nil '''do''' '''begin'''             //liczymy długość l2
 
     dl2:=dl2+1;
 
     dl2:=dl2+1;
 
     pom2:=pom2^.nast;
 
     pom2:=pom2^.nast;
 
   '''end''';  
 
   '''end''';  
   '''for''' i:=1 '''to''' dl1-dl2 '''do''' l1:=l1^.nast;
+
   '''for''' i:=1 '''to''' dl1-dl2 '''do''' l1:=l1^.nast;   //wyrównujemy odległość od końców list
 
   '''for''' i:=1 '''to''' dl2-dl1 '''do''' l2:=l2^.nast;
 
   '''for''' i:=1 '''to''' dl2-dl1 '''do''' l2:=l2^.nast;
   '''while''' l1 <> l2 '''do''' '''begin'''
+
   '''while''' l1 <> l2 '''do''' '''begin'''                 //szukamy elementu wspólnego
 
     l1:=l1^.nast;
 
     l1:=l1^.nast;
 
     l2:=l2^.nast;     
 
     l2:=l2^.nast;     
Linia 253: Linia 287:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>
  
{{cwiczenie| 1|pytanko 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">Ćwiczenie</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Skąd wiadomo, że w ostatnim while'u l1 i l2 sa zawsze różne od nil ?
 
Skąd wiadomo, że w ostatnim while'u l1 i l2 sa zawsze różne od nil ?
 
</div>
 
</div>
</div>}}
+
</div>
  
 
== Zadanie 8 (Listy z cyklem)==
 
== Zadanie 8 (Listy z cyklem)==
Napisz funkcje która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.  
+
Napisz funkcję która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.  
  
{{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">
Wystarczy poruszać sie po liście dwoma wskaźnikami o dwóch różnych względnie pierwszych prędkościach; wtedy albo trafimy na nil albo te wskaźniki się zejdą.
+
<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">
 +
Wystarczy poruszać sie po liście dwoma wskaźnikami o dwóch różnych względnie pierwszych prędkościach; wtedy albo trafimy szybszym wskaźnikiem na nil albo oba wskaźniki się zejdą.
 
</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''' ListaZCyklem(l:lista):boolean;
 
  '''function''' ListaZCyklem(l:lista):boolean;
  //Sprawdzamy czy lista l jest listą z cyklem, czy tez kończy sie nilem
+
  //Sprawdzamy czy lista l jest listą z cyklem, czy tez kończy się nilem
 
  '''var''' pom1, pom2: lista;
 
  '''var''' pom1, pom2: lista;
 
  '''begin'''
 
  '''begin'''
 
   pom1:=l;
 
   pom1:=l;
 
   pom2:=l^.nast;
 
   pom2:=l^.nast;
   '''while''' pom2 <> nil '''and''' pom2 <> pom1 '''do''' '''begin'''
+
   '''while''' (pom2 <> nil) '''and''' (pom2 <> pom1) '''do''' '''begin'''
 
     pom1:=pom1^.nast;
 
     pom1:=pom1^.nast;
 
     pom2:=pom2^.nast;
 
     pom2:=pom2^.nast;
     if pom2 <> nil pom2:=pom2^.nast;
+
     '''if''' pom2 <> nil '''then''' pom2:=pom2^.nast;
 
   '''end''';
 
   '''end''';
 
   ListaZCyklem:=(pom1=pom2);     
 
   ListaZCyklem:=(pom1=pom2);     
Linia 287: Linia 326:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>
  
== Zadanie 8 (Długość cyklu w liście z cyklem)==
+
== Zadanie 9 (Długość cyklu w liście z cyklem)==
Napisz funkcje która dla danej listy z cyklem obliczy długość cyklu.
+
Napisz funkcję która dla danej listy z cyklem obliczy długość cyklu.
  
{{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">
Można poruszać sie po liście dwoma wskaźnikami tak jak w zadaniu poprzednim; gdy wskaźniki sie zejdą to znaczyże jesteśmy na cyklu; wystarczy zatrzymać jeden wskaźnik a drugim obejść cykl.  
+
<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">
 +
Można poruszać sie po liście dwoma wskaźnikami tak jak w zadaniu poprzednim; gdy wskaźniki sie zejdą to znaczy, że jesteśmy na cyklu; wystarczy zatrzymać jeden wskaźnik a drugim obejść cykl i obliczyć jego długość.  
 
</div>
 
</div>
 
</div>
 
</div>
}}
+
<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>
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible-content" style="display:none">
  '''function''' DługośćCyklu1(l:lista):boolean;
+
  '''function''' DługośćCyklu1(l:lista):integer;
 
  //Obliczamy długość cyklu dla listy z cyklem
 
  //Obliczamy długość cyklu dla listy z cyklem
 
  '''var''' pom1, pom2: lista;
 
  '''var''' pom1, pom2: lista;
Linia 323: Linia 364:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>
  
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
 
Jeśli przechodząc po liście z cyklem będziemy ją odwracać to dojdziemy do poczatku; odwiedzimy przy tym 2m+n elementów gdzie n to długosć cyklu a n to liczba elementów poza cyklem. Wtedy (2m+n div 2)-ty element leży na cyklu i poczynając od niego można policzyc długość cyklu.
+
<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">
 +
Jeśli przechodząc po liście z cyklem będziemy ją odwracać to dojdziemy do początku; odwiedzimy przy tym 2m+n elementów gdzie n to długość cyklu a m to liczba elementów poza cyklem. Wtedy (2m+n div 2)-ty element leży na cyklu i poczynając od niego można obliczyć długość cyklu.
 
</div>
 
</div>
 
</div>
 
</div>
}}
+
<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>
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible-content" style="display:none">
  '''function''' DługośćCyklu2(l:lista):boolean;
+
  '''function''' DługośćCyklu2(l:lista):integer;
 
  //Obliczamy długość cyklu dla listy z cyklem
 
  //Obliczamy długość cyklu dla listy z cyklem
 
  '''var''' poprz, akt, pom1, pom2: lista;
 
  '''var''' poprz, akt, pom1, pom2: lista;
Linia 340: Linia 384:
 
   akt:=l;
 
   akt:=l;
 
   dl:=0;
 
   dl:=0;
   '''while'''  akt <> nil '''do''' '''begin'''
+
   '''while'''  akt <> nil '''do''' '''begin'''                       //odwracamy listę i liczymy ile kroków zajmuje dojście do nil
 
     pom1:=akt^.nast;
 
     pom1:=akt^.nast;
 
     akt^.nast:=poprz;
 
     akt^.nast:=poprz;
Linia 346: Linia 390:
 
     akt:=pom1;
 
     akt:=pom1;
 
     dl:=dl+1;
 
     dl:=dl+1;
   '''end''';
+
   '''end''';                                             //dl to 2m+n, gdzie n to długosć cyklu a
  pom1:=l;          //dl to 2m+n, gdzie n to długosć cyklu a n to liczba elementów poza cyklem
+
  pom1:=l;                                          //m to liczba elementów poza cyklem
   '''for''' i:=1 '''to''' (dl div 2) '''do''' pom1:=pom1^.nast;
+
   '''for''' i:=1 '''to''' (dl div 2) '''do''' pom1:=pom1^.nast;      
   pom2:=pom1^.nast; //pom1 i pom2 leżą na cyklu
+
   pom2:=pom1^.nast;                               //pom1 i pom2 leżą na cyklu
   dl:=1;           //liczymy długość cyklu
+
   dl:=1;                                           //liczymy długość cyklu
 
   '''while''' pom2 <> pom1 '''do''' '''begin'''
 
   '''while''' pom2 <> pom1 '''do''' '''begin'''
 
     dl:=dl+1;
 
     dl:=dl+1;
Linia 361: Linia 405:
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
 
</div>
 
</div>
</div>}}
+
</div>

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

To są zadania na listy.

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

W poniższych zadaniach będziemy używać następujących typów:

type lista = ^el_listy;
     el_listy = record
                  w: integer;
                  nast: lista;
                end;


Zadanie 1 (Odwracanie listy)

Napisz procedurę Odwróć(var l:lista) odwracającą listę l.

Rozwiązanie 1

Zadanie 2 (Scalanie dwóch posortowanych list)

Napisz funkcję Scal(l1,l2:lista):lista scalającą dwie posortowane niemalejąco listy l1 i l2, tak aby wynikowa lista również była posortowana niemalejąco.

Rozwiązanie

Ćwiczenie

Zadanie 3 (Usuwanie elementów zadanych listą)

Napisz procedurę Usuń(var l1:lista; l2:lista) która usunie z listy l1 wszystkie elementy z listy l2. Zakładamy, że listy l1 i l2 są posortowane niemalejąco.

Rozwiązanie

Ćwiczenie

Zadanie 4 (Uporządkowanie elementów w liście)

Napisz procedurę Uporządkuj(var l:lista) która przestawi elementy w liście l tak by najpierw były elementy w których pole w jest ujemne, potem równe zero, a na końcu dodatnie. Dodatkowo względna kolejność elementów jednego rodzaju (dodatnich, równych zero i ujemnych) powinna być zachowana.

Rozwiązanie

Zadanie 5 (Problem Józefa Flawiusza)

Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy l, aż pozostanie w niej tylko jeden element. Liczenie rozpoczynamy od elementu wskazywanego przez l.

Rozwiązanie

Zadanie 6 (Listy łączące się)

Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).

Wskazówka

Rozwiązanie

Zadanie 7 (Pierwszy wspólny element list łączących się)

Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.

Wskazówka

Rozwiązanie

Ćwiczenie

Zadanie 8 (Listy z cyklem)

Napisz funkcję która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.

Wskazówka

Rozwiązanie

Zadanie 9 (Długość cyklu w liście z cyklem)

Napisz funkcję która dla danej listy z cyklem obliczy długość cyklu.

Wskazówka 1

Rozwiązanie 1


Wskazówka 2

Rozwiązanie 2