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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(8 zadan na listy)
Linia 83: Linia 83:
 
   dispose(atrapa);
 
   dispose(atrapa);
 
  '''end''';  
 
  '''end''';  
−
''Koszt czasowy'': liniowy względem sumy długości listy
+
''Koszt czasowy'': liniowy względem sumy długości list
  
 
''Koszt pamięciowy'': stały
 
''Koszt pamięciowy'': stały
Linia 91: Linia 91:
 
{{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 instrukcja atrapa^.nast:=nil jest potrzebna? W jakich przypadkach ?
 
Czy instrukcja atrapa^.nast:=nil jest potrzebna? W jakich przypadkach ?
 +
</div>
 +
</div>}}
 +
 +
== 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.
 +
 +
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 +
'''procedure''' Usuń(var l1:lista; l2:lista);
 +
//Usuwamy z listy l1 wszystkie elementy z listy l2; zakładamy, że listy l1 i l2 są  posortowanych niemalejąco
 +
'''var''' atrapa, poprz: lista;
 +
'''begin'''
 +
  new(atrapa);
 +
  atrapa^.nast:=l1;
 +
  poprz:=atrapa;
 +
  '''while''' l1 <> nil and l2 <> nil '''do'''
 +
    '''if''' l1^.nast < l2^.nast '''then''' '''begin'''
 +
      l1:=l1^.nast;
 +
      poprz:=poprz^.nast;
 +
    '''end'''
 +
    '''else'''
 +
      '''if''' l1^.nast > l2^.nast '''then'''
 +
        l2:=l2^.nast
 +
      '''else''' '''begin'''
 +
        poprz^.nast:=l1^.nast;
 +
        dispose(l1);
 +
        l1:=poprz^.nast;
 +
      '''end''';
 +
  l1:=atrapa^.nast;
 +
  dispose(atrapa);
 +
'''end''';
 +
''Koszt czasowy'': liniowy względem sumy długości list
 +
 +
''Koszt pamięciowy'': stały
 +
</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 się przydaje ?
 +
</div>
 +
</div>}}
 +
 +
== 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.
 +
 +
 +
{{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);
 +
//Ustawiamy elementy listy l tak by najpierw były elemnty ujemne, potem równe zero, a na końcu dodatnie
 +
'''var''' atrapau, atrapaz, atrapad, u, z, d : lista;
 +
'''begin'''
 +
  new(atrapau); u:=atrapau;
 +
  new(atrapaz); z:=atrapaz;
 +
  new(atrapad); d:=atrapad;
 +
  '''while''' l <> nil  '''do''' '''begin'''
 +
    '''if''' l^.w < 0 '''then''' '''begin'''
 +
      u^.nast:=l;
 +
      u:=u^.nast;
 +
    '''end'''
 +
    '''else'''
 +
      '''if''' l^.w = 0 '''then''' '''begin'''
 +
        z^.nast:=l;
 +
        z:=z^.nast;
 +
      '''end''' 
 +
      '''else''' '''begin'''
 +
        d^.nast:=l;
 +
        d:=d^.nast;
 +
      '''end''';
 +
  d.^nast:=nil;
 +
  z^.nast:=atrapad^.nast;
 +
  u^.nast:=atrapaz^.nast;
 +
  l:=atrapau^.nast;
 +
  dispose(atrapad);
 +
  dispose(atrapaz);
 +
  dispose(atrapau);
 +
'''end''';
 +
''Koszt czasowy'': liniowy względem długości listy
 +
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>}}
 +
 +
 +
== 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, tak aby pozostał tylko jeden. Liczenie rozpoczynamy od elemnetu wskazywanego przez l.
 +
 +
 +
{{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);
 +
//Usuwamy z listy l cyklicznie co k-ty element dopóki nie zostanie 1; k>0, l niepusta cykliczna
 +
'''var''' atrapa, poprz: lista;
 +
'''begin'''
 +
  poprz:=l^.nast;
 +
  '''while''' poprz^.nast <> poprz '''do''' poprz:=poprz.^nast;
 +
  '''while''' poprz <> poprz^.nast '''do''' '''begin'''
 +
    '''for''' i:=1 '''to''' k-1 '''do''' '''begin''' poprz:=poprz^.nast;
 +
    pom:=poprz^.nast;
 +
    poprz^.nast:=pom^.nast;
 +
    dispose(pom);   
 +
  '''end''';
 +
  l:=poprz;
 +
'''end''';
 +
''Koszt czasowy'': rzędu n*k, gdzie n to długość listy
 +
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>}}
 +
 +
== 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).
 +
 +
{{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.
 +
</div>
 +
</div>
 +
}}
 +
 +
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 +
'''function''' Wspólny(l1, l2:lista):boolean;
 +
//Sprawdzamy czy listy proste l1 i l2 maja wspólny element
 +
'''var''' pom1, pom2: lista;
 +
'''begin'''
 +
  '''if''' l1=nil '''or''' l2=nil '''then''' Wspólny:=false
 +
  '''else''' '''begin'''
 +
    pom1:=l1;
 +
    '''while''' pom1^.nast <> nil '''do''' pom1:=pom1.^nast;
 +
    pom2:=l2;
 +
    '''while''' pom2^.nast <> nil '''do''' pom2:=pom2.^nast;
 +
    Wspólny:=(pom1=pom2);
 +
  '''end''';
 +
'''end''';
 +
''Koszt czasowy'': liniowy względem sumy długości list
 +
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>}}
 +
 +
== 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.
 +
 +
{{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.
 +
</div>
 +
</div>
 +
}}
 +
 +
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 +
'''function''' PierwszyWspólny(l1, l2:lista):lista;
 +
//Listy l1 i l2 maja wspólny element; szukamy pierwszego elementu wspólnego tych list
 +
'''var''' dl1, dl2, i: integer;
 +
    pom1, pom2: lista;
 +
'''begin'''
 +
  dl1:=0; pom1:=l1;
 +
  '''while''' pom1 <> nil '''do''' '''begin'''
 +
    dl1:=dl1+1;
 +
    pom1:=pom1^.nast;
 +
  '''end''';
 +
  dl2:=0; pom2:=l2;
 +
  '''while''' pom2 <> nil '''do''' '''begin'''
 +
    dl2:=dl2+1;
 +
    pom2:=pom2^.nast;
 +
  '''end''';
 +
  '''for''' i:=1 '''to''' dl1-dl2 '''do''' l1:=l1^.nast;
 +
  '''for''' i:=1 '''to''' dl2-dl1 '''do''' l2:=l2^.nast;
 +
  '''while''' l1 <> l2 '''do''' '''begin'''
 +
    l1:=l1^.nast;
 +
    l2:=l2^.nast;   
 +
  '''end''';
 +
  PierwszyWspólny:=l1;
 +
'''end''';
 +
''Koszt czasowy'': liniowy względem sumy długości list
 +
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>}}
 +
 +
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><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 ?
 +
</div>
 +
</div>}}
 +
 +
== Zadanie 8 (Listy z cyklem)==
 +
Napisz funkcje 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">
 +
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ą.
 +
</div>
 +
</div>
 +
}}
 +
 +
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 +
'''function''' ListaZCyklem(l:lista):boolean;
 +
//Sprawdzamy czy lista l jest listą z cyklem, czy tez kończy sie nilem
 +
'''var''' pom1, pom2: lista;
 +
'''begin'''
 +
  pom1:=l;
 +
  pom2:=l^.nast;
 +
  '''while''' pom2 <> nil '''and''' pom2 <> pom1 '''do''' '''begin'''
 +
    pom1:=pom1^.nast;
 +
    pom2:=pom2^.nast;
 +
    if pom2 <> nil pom2:=pom2^.nast;
 +
  '''end''';
 +
  ListaZCyklem:=(pom1=pom2);   
 +
'''end''';
 +
''Koszt czasowy'': liniowy względem długości listy
 +
 +
''Koszt pamięciowy'': stały
 +
</div>
 +
</div>}}
 +
 +
== Zadanie 8 (Długość cyklu w liście z cyklem)==
 +
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">
 +
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.
 +
</div>
 +
</div>
 +
}}
 +
 +
{{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;
 +
//Obliczamy długość cyklu dla listy z cyklem
 +
'''var''' pom1, pom2: lista;
 +
    dl: integer;
 +
'''begin'''
 +
  pom1:=l;
 +
  pom2:=l^.nast;
 +
  '''while'''  pom2 <> pom1 '''do''' '''begin'''
 +
    pom1:=pom1^.nast;
 +
    pom2:=pom2^.nast;
 +
    pom2:=pom2^.nast;
 +
  '''end''';
 +
  pom2:=pom1^.nast;
 +
  dl:=1;
 +
  '''while''' pom2 <> pom1 '''do''' '''begin'''
 +
    dl:=dl+1;
 +
    pom2:=pom2^.nast;
 +
  '''end''';
 +
  DługośćCyklu1:=dl;
 +
'''end''';
 +
''Koszt czasowy'': liniowy względem długości listy
 +
 +
''Koszt pamięciowy'': stały
 +
</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>
 +
</div>
 +
}}
 +
 +
{{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;
 +
//Obliczamy długość cyklu dla listy z cyklem
 +
'''var''' poprz, akt, pom1, pom2: lista;
 +
    dl: integer;
 +
'''begin'''
 +
  poprz:=nil;
 +
  akt:=l;
 +
  dl:=0;
 +
  '''while'''  akt <> nil '''do''' '''begin'''
 +
    pom1:=akt^.nast;
 +
    akt^.nast:=poprz;
 +
    poprz:=akt;
 +
    akt:=pom1;
 +
    dl:=dl+1;
 +
  '''end''';
 +
  pom1:=l;          //dl to 2m+n, gdzie n to długosć cyklu a n to liczba elementów poza cyklem
 +
  '''for''' i:=1 '''to''' (dl div 2) '''do''' pom1:=pom1^.nast;
 +
  pom2:=pom1^.nast; //pom1 i pom2 leżą na cyklu
 +
  dl:=1;            //liczymy długość cyklu
 +
  '''while''' pom2 <> pom1 '''do''' '''begin'''
 +
    dl:=dl+1;
 +
    pom2:=pom2^.nast;
 +
  '''end''';
 +
  DługośćCyklu2:=dl;
 +
'''end''';
 +
''Koszt czasowy'': liniowy względem długości listy
 +
 +
''Koszt pamięciowy'': stały
 
</div>
 
</div>
 
</div>}}
 
</div>}}

Wersja z 11:04, 10 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}}}

Ćwiczenie 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ówniez 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 potem 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, tak aby pozostał tylko jeden. Liczenie rozpoczynamy od elemnetu 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 8 (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}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Metody_programowania_/_Ćwiczenia_2&oldid=13834”