Wstęp do programowania/Rekursja/Ćwiczenia

To są zadania na rekursję.

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

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

Właściwą funkcję rekurencyjną szukającą drogi zamknij w funkcji-otoczce, która poza wywołaniem funkcji rekurencyjnej sprawdzi poprawność argumentów, przygotuje i/lub posprząta tablicę z labiryntem, zinterpretuje wynik funkcji rekurencyjnej itp. oraz będzie przechowywać dane wspólne dla wszystkich wywołań funkcji rekurencyjnej.

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 będziemy przetwarzać 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':

1. sprawdza czy punkt (i,j) nie jest poszukiwanym końcem (w tym przypadku zwraca true),
2. sprawdza czy punkt (i,j) nie jest ścianą lub punktem odwiedzonym wcześniej (w tym przypadku zwraca false),
3. zaznacza punkt (i,j) jako odwiedzony
4. 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 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ś miejscu 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').

Ćwiczenie 1

Ile razy maksymalnie może być wywołana funkcja 'szukaj' dla tego samego punktu?

Ćwiczenie 2

Jak przerobić przedstawione rozwiązanie na program wypisujący na ekran ścieżkę pomiędzy punktami (i1,j1) i (i2,j2), o ile taka ścieżka istnieje? Czy wypisana ścieżka będzie najkrótsza z możliwych ?

Ćwiczenie 3

Co by się stało, gdybyśmy usuwali zaznaczenie wychodząc z funkcji 'szukaj'? Czy program dalej by działał? Jeśli tak, to jaką by miał złożoność?

Odpowiedź

Program dalej by działał, ale miałby wykładniczą złożoność czasową zamiast liniowej (złożoność pamięciowa pozostałaby liniowa). W tej wersji program wielokrotnie przeszukiwałby sąsiadów pól, o których już z wcześniejszych obliczeń wiadomo, że nie da się z nich dojść do punktu końcowego.

Dla ciekawskich:

Rozwiązanie przedstawione powyżej polega na przeszukiwaniu wgłąb grafu reprezentującego labirynt. Inne, równie dobre rozwiązanie polega na przeszukiwaniu tego grafu wszerz, zwanego również metodą płonącego lasu. Wymaga ono użycia struktury danych -- kolejki. Rozwiązanie to łatwo przerobić na program wypisujący najkrótszą ścieżkę pomiędzy punktami (i1,j1) i (i2,j2), o ile taka ścieżka istnieje.

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ść). Sprawdź, 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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Rozwiązanie 2

{{{3}}}

Zadanie 3 (Wieże Hanoi z ograniczeniami)

Na wykładzie omawiane 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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Odpowiedź

{{{2}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Zadanie 6 (Suma składników)

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

Wskazówka 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 1

{{{3}}}