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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 119: Linia 119:
  
 
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{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 ?
+
Czy lista l1 musi być przekazywana przez zmienną ? W jakich przypadkach jest to konieczne ?
 
</div>
 
</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ść elelmentów jednego rodzaju (dodatnich, równych zero i ujemnych) powinna być zachowana.
  
 
{{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''' 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 elemnty ujemne, potem równe zero, a na końcu dodatnie
 +
//Osobno zbieramy elementy ujemne, dodatnie i rowne 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 136:
 
   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''';
 +
    l:=l^nast;
 +
  '''end''';  //while
 
   d.^nast:=nil;
 
   d.^nast:=nil;
 
   z^.nast:=atrapad^.nast;
 
   z^.nast:=atrapad^.nast;
Linia 164: Linia 167:
 
== 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">
 
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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 1; 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''' '''begin''' poprz:=poprz^.nast;
 
     pom:=poprz^.nast;
 
     pom:=poprz^.nast;
Linia 191: Linia 194:
  
 
{{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">
Jeśli listy mają wspólny element to ostatni niepusty element l1 i ostatni niepusty element l2 muszą byc takie same.
+
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>
Linia 220: Linia 223:
  
 
{{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">
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.
+
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>
Linia 231: Linia 234:
 
     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 264: Linia 267:
  
 
{{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">
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ą.
+
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>
Linia 289: Linia 292:
 
</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 funkcje 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">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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.  
+
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 policzyć jego długość.  
 
</div>
 
</div>
 
</div>
 
</div>
Linia 299: Linia 302:
  
 
{{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''' 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 326: Linia 329:
  
 
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{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.
+
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 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 policzyc długość cyklu.
 
</div>
 
</div>
 
</div>
 
</div>
Linia 332: Linia 335:
  
 
{{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''' 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 343:
 
   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 349:
 
     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;

Wersja z 21:28, 13 sie 2006

To są zadania na listy.

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

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

Zadanie 1 (Odwracanie listy)

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

Rozwiązanie 1

{{{3}}}

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 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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.

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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ść elelmentów jednego rodzaju (dodatnich, równych zero i ujemnych) powinna być zachowana.

Rozwiązanie 1

{{{3}}}

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 1

{{{3}}}

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Zadanie 8 (Listy z cyklem)

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

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

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

Wskazówka 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}