Wstęp do programowania / Ćwiczenia 2

To są ćwiczenia z rekurencji.

Zadanie 1 (Labirynt)

Czy istnieje ścieżka miedzy wskazanymi punktami (i1,j1) i (i2,j2) w labiryncie reprezentowanym przez prostokątną tablicę liczb całkowitych o rozmiarze M×N, zawierającą zera (ściana) i jedynki (droga)? Zakładamy, że nie można przechodzić z pola na pole po skosie (np. z (2,5) na (3,6)), a tylko w czterech podstawowych kierunkach (np. z (2,5) na (3,5), (2,4) itd.)

Wskazówka 1

Rozwiązanie 1

function Labirynt(M,N:integer; var A:array[1..M,1..N] of integer; i1,j1,i2,j2:integer):boolean;
// M,N >= 1
// A zawiera 0 (ściana) i 1 (droga)

  function szukaj(i,j:integer):boolean;
  // 1 <= i <= M
  // 1 <= j <= N
  var jest:boolean;
  begin
    if (i=i2) and (j=j2) then 
      jest:=true 
    else begin
      jest:=false;
      if A[i,j]>0 then begin
        A[i,j]:=-1;
        if i>1 then jest:=szukaj(i-1,j);
        if not jest and (i<M) then jest:=szukaj(i+1,j);
        if not jest and (j>1) then jest:=szukaj(i,j-1);
        if not jest and (j<N) then jest:=szukaj(i,j+1);
      end
    end;
    szukaj:=jest
  end; // szukaj
  
var i,j:integer;
begin // Labirynt
  if not((1<=i1) and (i1<=M) and (1<=j1) and (j1<=N) and
    (1<=i2) and (i2<=M) and (1<=j2) and (j2<=N)) then
    Labirynt:=false
  else
  begin
    Labirynt:=szukaj(i1,j1);  
    for i:=1 to M do 
      for j:=1 to N do 
        if A[i,j]=-1 then A[i,j]:=1
  end
end; // Labirynt

Koszt czasowy: liniowy względem rozmiaru A (czyli M×N)

Koszt pamięciowy: liniowy względem rozmiaru A

Opis: Przeszukujemy wgłąb tablicę zaznaczając odwiedzone pola poprzez ustawienie ich wartości na -1. Dzięki temu nie zapętlimy się, ani nie przetwarzamy wielokrotnie tych samych pól.

Dyskusja: Funkcja 'Labirynt' jest otoczką, która sprawdza poprawność parametrów, wywołuje właściwą funkcję rekurencyjną 'szukaj' oraz sprząta po niej zaznaczenia w tablicy A.

Wewnętrzna funkcja rekurencyjna 'szukaj' ma za zadanie znaleźć ścieżkę z punktu (i,j) do punktu (i2,j2) po niezaznaczonych polach w tablicy A. Korzysta ona z kilku nazw zadeklarowanych przez otoczkę (M, N, A, i2, j2), dlatego nie są one parametrami wywołania funkcji 'szukaj'.

Funkcja 'szukaj':

sprawdza czy punkt (i,j) nie jest poszukiwanym końcem (w tym przypadku zwraca true),
sprawdza czy punkt (i,j) nie jest ścianą lub punktem odwiedzonym wcześniej (w tym przypadku zwraca false),
zaznacza punkt (i,j) jako odwiedzony
próbuje szukać drogi z punktów sąsiednich dla punktu (i,j), o ile sąsiedzi Ci istnieją.

Zauważ, że testy 1 i 2, mogłyby być wykonane przed każdym wywołaniem funkcji 'szukaj' w punkcie 4 (oraz w otoczce) zamiast na jej początku, jednak prowadziłoby to do wielokrotnego pisania bardzo podobnych fragmentów programu, co łatwo prowadzi do błędów. Oczywiście nie zmniejszyłoby to złożoności czasowej i pamięciowej.

Podobnie, jak testy 1 i 2, testy istnienia sąsiadów (i>1), (i<M) itp. w punkcie 4 mogłyby być wykonane na początku funkcji 'szukaj' (wtedy nie zakładalibyśmy, że (i,j) jest poprawnym punktem w tablicy), ale nie mając wiedzy w którą stronę ostatnio poszliśmy, musielibyśmy dla sprawdzić pełną poprawność obu współrzędnych (i,j), czyli w sumie sprawdzalibyśmy 4 warunki. W aktualnej wersji sprawdzamy tylko 1 warunek.

Poprawność rozwiązania: Oczywiste jest, że jeśli funkcja 'Labirynt' da wynik true, to ścieżka z (i1,j1) do (i2,j2) istnieje. Mniej oczywiste jest, że jeśli funkcja da wynik false, to ścieżka na pewno nie istnieje.

Aby przeprowadzić dowód przez sprzeczność, załóżmy, że funkcja 'szukaj' wywołana w funkcji 'Labirynt' dała wynik false, a ścieżka z (i1,j1) do (i2,j2) istnieje. W takim razie A[i1,j1]=-1 a A[i2,j2]=1. Wynika z tego, że ścieżka z (i1,j1) do (i2,j2) w którymś miejścu opuszcza zaznaczoną część tablicy, czyli istnieją dwa sąsiednie pola (i,j) i (i',j') na tej ścieżce, takie że A[i,j]=-1, A[i',j']=1. Z tego wynika, że funkcja szukaj została (w czasie działania programu) wywołana z parametrami (i,j), ale nie została wywołana z parametrami (i',j'). Jest to niemożliwe, bo pola te sąsiadują ze sobą i wywołanie dla (i,j) wywołałoby rekurencyjnie 'szukaj' dla (i',j').

Pytanko 1:

Pytanko 2:

Pytanko 3: (trudniejsze)

Odpowiedź:

Dla ciekawskich:

Zadanie 2 (Z górki na pazurki)

W tablicy liczb całkowitych o rozmiarze M×N zapisana jest mapa gór (każdy punkt ma podaną dodatnią wysokość). Sprawdzić, czy da się przejść z punktu startowego (i1,j1) do docelowego (i2,j2) idąc:

tylko w dół lub po płaskim
tylko w dół

Tak jak w poprzednim zadaniu poruszać się można tylko w czterech kierunkach podstawowych, nie po przekątnej.

Wskazówka 1

Rozwiązanie 1

function Zjazd1(M,N:integer; var A:array[1..M,1..N] of integer; i1,j1,i2,j2:integer):boolean;
// M,N >= 1
// A zawiera liczby > 0

  function szukaj(h,i,j:integer):boolean;
  // 0 < h
  // 1 <= i <= M
  // 1 <= j <= N
  var jest:boolean;
    hpom:integer;
  begin
    jest:=false;
    if (A[i,j]>0) and (h>A[i,j]) begin // h>=A[i,j] w wariancie II
      if (i=i2) and (j=j2) then 
        jest:=true 
      else begin
        hpom:=A[i,j];
        A[i,j]:=-A[i,j];
        if i>1 then jest:=szukaj(hpom,i-1,j);
        if not jest and (i<M) then jest:=szukaj(hpom,i+1,j);
        if not jest and (j>1) then jest:=szukaj(hpom,i,j-1);
        if not jest and (j<N) then jest:=szukaj(hpom,i,j+1);
      end
    end;
    szukaj:=jest
  end; // szukaj
  
var i,j:integer;
begin // Zjazd1
  if not((1<=i1) and (i1<=M) and (1<=j1) and (j1<=N) and
    (1<=i2) and (i2<=M) and (1<=j2) and (j2<=N)) then
    Zajzd:=false
  else
  begin
    Zjazd:=szukaj(A[i1,j1]+1,i1,j1); // wystarczy szukaj(A[i1,j1],i1,j1) w wariancie II
    for i:=1 to M do 
      for j:=1 to N do 
        if A[i,j]<0 then A[i,j]:=-A[i,j]
  end
end; // Zjazd1

Koszt czasowy: liniowy względem rozmiaru A (czyli M×N)

Koszt pamięciowy: liniowy względem rozmiaru A

Opis: Podobnie jak w poprzednim zadaniu, przeszukujemy tablicę wgłąb, jednak przechodzimy tylko do tych pól sąsiednich, które mają mniejszą (odpowiednio: mniejszą lub równą) wysokość.

Dyskusja: Tak jak w rozwiązaniu poprzedniego zadania, istnienie sąsiada na planszy badamy przed wywołaniem rekurencyjnym, a poprawność przejścia na początku wywołania. Służy nam do tego dodatkowy parametr 'h', który oznacza wysokość poprzedniego pola. Dlatego pierwsze wywołanie funkcji 'szukaj' ma pierwszy parametr A[i1,j1]+1 (w wariancie I). Uwaga! Funkcja ta nie zadziała, jeśli A[i1,j1]=MaxInt (czyli maksymalnej możliwej wartości typu integer). Poniżej przedstawione jest rozwiązanie bez tego mankamentu.

Rozwiązanie 2

function Zjazd2(M,N:integer; var A:array[1..M,1..N] of integer; i1,j1,i2,j2:integer):boolean;
// M,N >= 1
// A zawiera liczby > 0

  function wdol(h,i,j:integer):boolean;
  // sprawdza czy pole (i,j) nie jest zaznaczone i
  // czy przejscie z pola o wysokosci h na pole (i,j) jest rzeczywiscie w dół
  // 1 <= i <= M
  // 1 <= j <= N
  begin
    wdol:=(A[i,j]>0) and (h>A[i,j]) // h>=A[i,j] w wariancie II
  end; //wdol

  function szukaj(i,j:integer):boolean;
  // 1 <= i <= M
  // 1 <= j <= N
  var jest:boolean;
    hpom:integer;
  begin
    if (i=i2) and (j=j2) then 
      jest:=true 
    else begin
      jest:=false;
      hpom:=A[i,j];
      A[i,j]:=-hpom;
      if i>1 then if wdol(hpom,i-1,j) then jest:=szukaj(i-1,j);
      if not jest and (i<M) then if wdol(hpom,i+1,j) then jest:=szukaj(i+1,j);
      if not jest and (j>1) then if wdol(hpom,i,j-1) then jest:=szukaj(i,j-1);
      if not jest and (j<N) then if wdol(hpom,i,j+1) then jest:=szukaj(i,j+1);
    end;
    szukaj:=jest
  end; // szukaj
  
var i,j:integer;
begin // Zjazd2
  if not((1<=i1) and (i1<=M) and (1<=j1) and (j1<=N) and
    (1<=i2) and (i2<=M) and (1<=j2) and (j2<=N)) then
    Zajzd:=false
  else
  begin
    Zjazd:=szukaj(i1,j1); 
    for i:=1 to M do 
      for j:=1 to N do 
        if A[i,j]<0 then A[i,j]:=-A[i,j]
  end
end; // Zjazd2

Koszt czasowy: liniowy względem rozmiaru A (czyli M×N)

Koszt pamięciowy: liniowy względem rozmiaru A

Opis: Rozwiązanie jest bardzo podobne do poprzedniego. Różnica polega na przeniesieniu kodu z początku funkcji 'szukaj' do osobnej funkcji 'wdol'. Funkcja ta jest używana jako test dopuszczający do rekurencyjnego wywołania funkcji 'szukaj'.

Zadanie 3 (Wieże Hanoi z ograniczeniami)

Na wykładzie były wieże Hanoi. Ciekawa modyfikacja tego zadania polega na zabronieniu ruchów pomiędzy niektórymi pałeczkami, np. z pierwszej na drugą. Zapisać procedurę realizującą to zadanie przy zabronionych niektórych ruchach.

Wskazówka 1

Rozwiązanie 1

type Paleczki = 1..3;

procedure Hanoi(Ile: integer; Skad, Dokad: Paleczki; Dozw: TDozwRuchow);

  procedure Rob(Skad, Dokad, Pom: Paleczki; Ile: Integer);
  // Pom jest zawsze rowne 6-Skad-Dokad, ale z parametrem jest czytelniej
  begin
    if Ile > 0 then
      if Dozw[Skad, Dokad] then begin
        Rob(Skad, Pom, Dokad, Ile-1);
        Przenies(Skad,Dokad);
        Rob(Pom, Dokad, Skad, Ile-1);
      end
      else begin
        Rob(Skad, Dokad, Pom, Ile-1);
        Przenies(Skad, Pom);
        Rob(Dokad, Skad, Pom, Ile-1);
        Przenies(Pom, Dokad);
        Rob(Skad, Dokad, Pom, Ile-1);
      end
  end; //Rob

  function CzyDaSie(Skad, Dokad, Pom: Paleczki):boolean
  begin
    if not Dozw[Skad, Dokad] and not (Dozw[Skad, Pom] and Dozw[Pom, Dokad]) then begin
      writeln('Nie da sie przełożyć krążka z ',Skad,' na ',Pom);
      CzyDaSie:=false
    end
    else
      CzyDaSie:=false
  end // CzyDaSie     

var ok:boolean
begin // Hanoi
  ok:=true;
  for i:=1 to 2 do for j:=i+1 to 3 do
    ok:=ok and CzyDaSie(i,j,6-i-j) and CzyDaSie(j,i,6-i-j);
  if ok then Rob(Skad,Dokad,6-Skad-Dokad,Ile);
end; // Hanoi

Koszt czasowy: wykładniczy ze względu na Ile

Koszt pamięciowy: liniowy ze względu na Ile

Omówienie: Zauważ, że dużo łatwiej jest rozwiązać to zadanie sformułowane w sposób ogólny, niż gdy powie się, że zabroniony jest konkretny ruch (np. 1 → 2).

Pytanko 1

Odpowiedź

Najgorszy przypadek, to taki, gdy przerwane jest połączenie Skąd-Dokąd w obie strony. Wtedy trzeba wykonać $3^{I l e} - 1$ ruchów)

Zadanie 4 (Ustawianie hetmanów)

Napisz procedurę znajdująca wszystkie takie rozstawienia 8 hetmanów na szachownicy, by żadne dwa hetmany się nie atakowały.

Wskazówka 1

Rozwiązanie 1

procedure Hetmany(N:integer);
// N >= 1
var 
  wiersze:array[1..N] of integer;
  kolumny:array[1..N] of boolean;
  przekgd:array[-(N-1)..N-1] of boolean; // przekątne \ o stałej różnicy
  przekdg:array[2..2*N] of boolean;      // przekątne / o stałej sumie
 
  procedure ustaw(k,i:integer);
  // 1 <= k,i <= N
  begin
    wiersze[k]:=i;
    kolumny[i]:=true;
    przekgd[k-i]:=true;   
    przekdg[k+i]:=true;   
  end; // ustaw
  
  procedure odstaw(k,i:integer);
  // 1 <= k,i <= N
  begin
    wiersze[k]:=0;
    kolumny[i]:=false;
    przekgd[k-i]:=false;   
    przekdg[k+i]:=false;   
  end; // odstaw
   
  function wolne(k,i:integer):boolean
  // 1 <= k,i <= N
  begin
    wolne:=not kolumny[i] & not przekgd[k-i] & not przekdg[k+i]
  end; // wolne

  var jest:boolean;

  procedure wypisz;
  var i:integer;
  begin
    jest:=true;
    write('Ustawienie: ')
    for i:=1 to N; do write(i,':',wiersze[i],' ')
    writeln;
  end; // wypisz

  procedure rozstaw(k:integer);
  var i:integer;
  begin
    if k=N+1 then 
      wypisz
    else 
      for i:=1 to N do
        if wolne(k,i) then begin
	   ustaw(k,i);
	   rozstaw(k+1);
	   odstaw(k,i);
        end
  end; // rozstaw

var i:integer;
begin // Hetmany
  for i:=1 to N do wiersze[i]:=0;
  for i:=1 to N do kolumny[i]:=false;
  for i:=-(N-1) to N-1 do przekgd[i]:=false;
  for i:=2 to 2*N do przekdg[i]:=false;
  jest:=false;
  rozstaw(i);
  if not jest then writeln('Nie znaleziono żadnego ustawienia')
end // Hetmany

Koszt czasowy: wykładniczy względem N

Koszt pamięciowy: liniowy względem N

Opis: Aby ustawić N hetmanów, każdy z nich musi stać w osobnym wierszu. Dlatego główna procedurą rekurencyjna 'rozstaw' próbuje ustawić k-tego hetmana w wierszu k w kolejnych kolumnach. Jeśli to się uda (wolne(k,i)=true) zaznacza zajętość odpowiedniej kolumny i przekątnych i wywołuje się rekurencyjnie aby rozstawić pozostałe hetmany. Po powrocie z wywołania rekurencyjnego, kolumna i przekątne są zwalniane i pętla for próbuje ustawić k-tego hetmana w kolejnej kolumnie.

Jeśli nie ma już żadnych hetmanów do rozstawiania (k=N+1) oznacza to, że N jest już ustawionych - pozostaje ich wypisać. Przy okazji zmienna 'jest' rejestruje czy jakiekolwiek rozwiązanie zostało wypisane. Jeśli nie, główna procedura 'Hetmany' wypisuje stosowny komunikat.

Zadanie 5 (Mnożenie wielomianów)

Dane są dwie tablice (array[0..N-1] of real) reprezentujące dwa wielomiany stopnia N-1. Należy obliczyć iloczyn tych wielomianów metodą dziel-i-zwyciężaj. Zakładamy, że N jest potęgą dwójki.

Wskazówka 1

Zamiast rozwiązania naiwnego wymajającego $n^{2}$ mnożeń zróbmy trochę lepsze (aczkolwiek nie najlepsze) polegające na podzieleniu wielomianów na dwie części. Cały pomysł polega na spostrzeżeniu, że jeśli zadane wielomiany $p (x)$ i $q (x)$ podzielimy na dolna i górną część
$p (x) = p_{l} (x) + p_{h} (x) * x^{N / 2}$ i analogicznie $q (x) = q_{l} (x) + q_{h} (x) * x^{N / 2}$ , to ich iloczyn można zapisać tak:
$p (x) * q (x) = r_{l} (x) + (r_{m} (x) - r_{l} (x) - r_{h} (x)) * x^{N / 2} + r_{h} (x) * x^{N}$ , gdzie
$r_{l} (x) = p_{l} (x) * q_{l} (x)$
$r_{h} (x) = p_{h} (x) * q_{h} (x)$
$r_{m} (x) = (p_{h} (x) + p_{l} (x)) * (q_{h} (x) + q_{l} (x))$
Czyli potrzebujemy 3 mnożeń o połowę mniejszych wielomianów. W sumie uzyskamy liczbę mnożeń rzędu $n^{l g 3}$ . Szczególy można znaleźć w Sedgewick Algorithms in C++, str. 527-530.

Zadanie 6 (Suma składników)

Napisz procedurę, która wypisze dla zadanej liczby n jej wszystkie rozkłady na sumy nieujemnych liczb naturalnych większych od 1 ustawionych w kolejności nierosnącej. Np. dla n = 3:
3 = 3
3 = 2+1
3 = 1+1+1

Wskazówka 1

Wskazówka 2

Rozwiązanie 1

procedure Suma(n:integer);
// 1 <= n

  procedure rozklad(var T:array[1..n] of integer; ti,k,m:integer)
  // 0 <= ti <= n
  // ti > 0 --> k=T[ti]
  // 0 <= m
  // m=0 --> ti > 0
  var i:integer
  begin
    if m=0 then begin
      writeln(n,' = ');
      for i=1 to ti-1 do write(T[i],'+');
      writeln(T[ti])
    end         
    else begin
      ti:=ti+1;
      for i=min(k,m) downto 1 do begin
        T[ti]:=i;
        rozklad(T,ti,i,m-i);
      end
    end
  end //rozklad

var T:array[1..n] of integer;
begin     
  rozklad(T,0,n,n);
end // Suma

Koszt czasowy: wykładniczy względem n

Koszt pamięciowy: liniowy względem n

Opis: Funkcja rekurencyjna 'rozkład' przegląda wszystkie nierosnące rozkłady liczby m używające składników niewiększych niż k. Ponieważ w tablicy T[1..ti] jest już nierosnący ciąg składników o sumie n-m, wydłużenie go o dowolny taki rozkład m będzie dawać poprawny rozkład n.

Istotnie, jeśli m=0, w tablicy jest już gotowy rozkład n, więc wypisujemy go. W przeciwnym razie zwiekszamy ti, wszystkie liczby i, które mogą znaleźć się w tym miejscu rozkładu umieszczamy kolejno w T[ti] i wywołujemy rekurencyjnie funkcję 'rozklad', aby do wydłużonego rozkładu dopisała wszystkie rozkłady m-i o pierwszym składniku nieprzekraczającym i.

Zwróć uwagę, że tablica T przekazywana jest przez zmienną i dlatego jej zawartość nie jest kopiowana. Tablica T mogłaby też być zmienną globalną (dla procedury 'Suma'), ponieważ i tak wszystkie wywołania funkcji rozklad korzystają z tej samej tablicy zadeklarowanej w głównej części procedury 'Suma'.

Zauważ, że można by też tak napisać procedurę 'rozklad', aby nigdy nie wywoływała się rekurencyjnie dla m=0. Wypisywanie pełnego rozkładu miałoby miejsce wtedy, gdy min(k,m)=m (czyli k>=m) i oczywiscie petla 'for' zaczynalaby sie w takim przypadku od m-1.

Druga możliwa modyfikacja polega na zrezygnowaniu z parametru k, ponieważ k albo jest równe T[ti], albo m jeśli ti=0. Mozna by też użyć strażnika T[0]=n i zawsze mielibyśmy k=T[ti].

Poza wspomnianymi modyfikacjami całą procedurę 'rozkład' można by napisać w sposób rosnący, tzn. zamiast generować coraz mniejsze składniki - generować coraz większe, aż osiągniemy, bądź przekroczymy n. W takim wypadku składniki należałoby wypisywać w odwrotnej kolejności.

Wstęp do programowania / Ćwiczenia 2

Spis treści

Zadanie 1 (Labirynt)

Zadanie 2 (Z górki na pazurki)

Zadanie 3 (Wieże Hanoi z ograniczeniami)

Zadanie 4 (Ustawianie hetmanów)

Zadanie 5 (Mnożenie wielomianów)

Zadanie 6 (Suma składników)

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia