Wstęp do programowania/Rekursja/Ćwiczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 434: Linia 434:
 
   '''var''' T:'''array'''[1..n] '''of''' integer;
 
   '''var''' T:'''array'''[1..n] '''of''' integer;
 
   
 
   
   '''procedure''' rozklad('''var''' T:'''array'''[1..n] '''of''' integer; ti,k,m:integer)
+
   '''procedure''' rozklad('''var''' T:'''array'''[1..n] '''of''' integer; ti,co,maxSkł:integer)
   // 0 <= ti <= n
+
  // rozkładamy liczbę co używając składników nie większych niż maxSkł
   // ti > 0 --> k=T[ti]
+
  // rozkłady wpisujemy do tablicy T; pierwsze wolne miejsce to ti+1
   // 0 <= m
+
   // 0 <= ti <= n
   // m=0 --> ti > 0
+
   // ti > 0 --> maxSkł=T[ti]  
 +
   // 0 <= co
 +
   // co=0 --> ti > 0
 
   '''var''' i:integer
 
   '''var''' i:integer
 
   '''begin'''
 
   '''begin'''
     '''if''' m=0 '''then''' '''begin'''
+
     '''if''' co=0 '''then''' '''begin'''
 
       write(n,' = ');
 
       write(n,' = ');
 
       '''for''' i:=1 '''to''' ti-1 '''do''' write(T[i],'+');
 
       '''for''' i:=1 '''to''' ti-1 '''do''' write(T[i],'+');
Linia 448: Linia 450:
 
     '''else''' '''begin'''
 
     '''else''' '''begin'''
 
       ti:=ti+1;
 
       ti:=ti+1;
       '''for''' i:=min(k,m) '''downto''' 1 '''do''' '''begin'''
+
       '''for''' i:=min(co,maxSkł) '''downto''' 1 '''do''' '''begin'''
 
         T[ti]:=i;
 
         T[ti]:=i;
         rozklad(T,ti,i,m-i);
+
         rozklad(T,ti,i,co-i);
 
       '''end'''
 
       '''end'''
 
     '''end'''
 
     '''end'''
Linia 465: Linia 467:
 
[http://www.mimuw.edu.pl/~annan/modul2_19_1.html Wizualizacja]
 
[http://www.mimuw.edu.pl/~annan/modul2_19_1.html Wizualizacja]
  
''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.
+
''Opis:'' Funkcja rekurencyjna 'rozkład' przegląda wszystkie nierosnące rozkłady liczby co używające składników niewiększych niż maxSkł. Ponieważ w tablicy T[1..ti] jest już nierosnący ciąg składników o sumie n-co, wydłużenie go o dowolny taki rozkład co 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.
+
Istotnie, jeśli co=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 co-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'.
 
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.
+
Zauważ, że można by też tak napisać procedurę 'rozklad', aby nigdy nie wywoływała się rekurencyjnie dla co=0. Wypisywanie pełnego rozkładu miałoby miejsce wtedy, gdy min(maxSkł,co)=co (czyli maxSkł>=co) i oczywiście pętla 'for' zaczynałaby się w takim przypadku od co-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].
+
Druga możliwa modyfikacja polega na zrezygnowaniu z parametru maxSkł, ponieważ maxSkł albo jest równe T[ti], albo co jeśli ti=0. Można by też użyć strażnika T[0]=n i zawsze mielibyśmy maxSkł=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.
 
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.

Wersja z 17:20, 3 paź 2006

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

Ćwiczenie 2

{{{3}}}

Ćwiczenie 3

{{{3}}}

Odpowiedź

{{{2}}}

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

{{{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 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

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 1

{{{3}}}