Metody programowania / Ćwiczenia 2

From Studia Informatyczne

To są zadania na listy.

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

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;


Spis treści

Zadanie 1 (Odwracanie listy)

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

Rozwiązanie 1

procedure Odwróć(var l:lista);
//Odwracamy listę l
var poprz, akt, pom : lista;
begin
  if l <> nil then begin
    poprz:=nil;
    akt:=l;
    while akt<>nil do begin
      pom:=akt^.nast;
      akt^.nast:=poprz;
      poprz:=akt;
      akt:=pom;
    end;
  end;
  l:=poprz;
end;

Koszt czasowy: liniowy względem długości listy

Koszt pamięciowy: stały

Wizualizacja

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

function Scal(l1,l2:lista): lista;
//Listy l1 i l2 są posortowane niemalejąco; scalamy je do jednej listy również posortowanej niemalejąco
var atrapa, akt : lista;
begin
  new(atrapa);
  atrapa^.nast:=nil;
  akt:=atrapa;
  while (l1 <> nil) and (l2 <> nil) do
    if l1^.w < l2^.w then begin            //jeśli l1^.w < l2^.w
      akt^.nast:=l1;
      akt:=akt^.nast;
      l1:=l1^.nast;
    end
    else 
      if l1^.w > l2^.w then begin         //jeśli l1^.w > l2^.w
        akt^.nast:=l2;
        akt:=akt^.nast;
        l2:=l2^.nast;
      end
      else begin                          //jeśli l1^.w = l2^.w - ten else można sobie darować, i tak będzie dobrze
        akt^.nast:=l1;
        akt:=akt^.nast;
        l1:=l1^.nast;
        akt^.nast:=l2;
        akt:=akt^.nast;
        l2:=l2^.nast;
      end;
  if l1 = nil then                       //obsługa końcówki listy która nie jest pusta
    akt^.nast:=l2 
  else 
    akt^.nast:=l1;                           
  Scal:=atrapa^.nast;
  dispose(atrapa);
end; 

Koszt czasowy: liniowy względem sumy długości list

Koszt pamięciowy: stały

Wizualizacja

Ćwiczenie 1

Czy instrukcja atrapa^.nast:=nil jest potrzebna? W jakich przypadkach ?

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 1

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
var atrapa, poprz: lista;
begin
  new(atrapa);
  atrapa^.nast:=l1;
  poprz:=atrapa;
  while (l1 <> nil) and (l2 <> nil) do
    if l1^.w < l2^.w then begin        //jeśli l1^.w < l2^.w 
      l1:=l1^.nast;
      poprz:=poprz^.nast;
    end
    else 
      if l1^.w > l2^.w then            //jeśli l1^.w > l2^.w
        l2:=l2^.nast
      else begin                       //jeśli l1^.w = l2^.w
        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

Wizualizacja

Ćwiczenie 1

Czy lista l1 musi być przekazywana przez zmienną ? W jakich przypadkach jest to konieczne ?

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 1

procedure Uporządkuj(var l:lista);
//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;
begin
  new(atrapau); u:=atrapau;
  new(atrapaz); z:=atrapaz;
  new(atrapad); d:=atrapad; 
  while l <> nil  do begin
    if l^.w < 0 then begin          //dołączamy l do listy u
      u^.nast:=l;
      u:=u^.nast;
    end
    else 
      if l^.w = 0 then begin        //dołączamy l do listy z
        z^.nast:=l;
        z:=z^.nast;
      end  
      else begin                    //dołączamy l do listy d
        d^.nast:=l;
        d:=d^.nast;
      end;
    l:=l^.nast;
  end;   //while
  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

Wizualizacja

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

procedure Flawiusz(var l:lista; k:integer);
//Usuwamy z listy l cyklicznie co k-ty element dopóki nie zostanie jeden element; k>0, l niepusta cykliczna
var poprz, pom: lista;
begin
  poprz:=l^.nast;
  while poprz^.nast <> l do poprz:=poprz^.nast;      //poprz wskazuje na element poprzedzający l
  while poprz <> poprz^.nast do begin               //dopóki lista ma więcej niz jeden element
    for i:=1 to k-1 do  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

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

Jeśli listy mają wspólny element to ostatni niepusty element l1 i ostatni niepusty element l2 muszą być takie same.

Rozwiązanie 1

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

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

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.

Rozwiązanie 1

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              //liczymy długość l1
    dl1:=dl1+1;
    pom1:=pom1^.nast;
  end; 
  dl2:=0; pom2:=l2;
  while pom2 <> nil do begin              //liczymy długość l2
    dl2:=dl2+1;
    pom2:=pom2^.nast;
  end; 
  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;
  while l1 <> l2 do begin                 //szukamy elementu wspólnego
    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

Ćwiczenie 1

Skąd wiadomo, że w ostatnim while'u l1 i l2 sa zawsze różne od nil ?

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 1

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ą.

Rozwiązanie 1

function ListaZCyklem(l:lista):boolean;
//Sprawdzamy czy lista l jest listą z cyklem, czy tez kończy się 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  then pom2:=pom2^.nast;
  end;
  ListaZCyklem:=(pom1=pom2);     
end;

Koszt czasowy: liniowy względem długości listy

Koszt pamięciowy: stały

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

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ść.

Rozwiązanie 1

function DługośćCyklu1(l:lista):integer;
//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

Wskazówka 2

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.

Rozwiązanie 2

function DługośćCyklu2(l:lista):integer;
//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                       //odwracamy listę i liczymy ile kroków zajmuje dojście do nil
    pom1:=akt^.nast;
    akt^.nast:=poprz;
    poprz:=akt;
    akt:=pom1;
    dl:=dl+1;
  end;                                             //dl to 2m+n, gdzie n to długosć cyklu a
 pom1:=l;                                          //m 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