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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 59: Linia 59:
 
''Koszt pamięciowy:'' liniowy względem rozmiaru A
 
''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.
+
''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.
 
''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.
Linia 73: Linia 73:
 
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.
 
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.
+
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.
 
''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.
Linia 87: Linia 87:
  
 
{{cwiczenie| 2|pytanko 2|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{cwiczenie| 2|pytanko 2|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
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 ?
+
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 ?
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 118: Linia 118:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Zadanie to należy rozwiązywać tak jak poprzednie. Jedyną różnicą jest to jak należy decydować czy z danego pola można przejść do sąsiedniego: oprócz zaznaczenia trzeba wziąć pod uwagę różnicę wysokości.
+
Zadanie to należy rozwiązywać tak jak poprzednie. Jedyną różnicą jest to, jak należy decydować czy z danego pola można przejść do sąsiedniego: oprócz zaznaczenia trzeba wziąć pod uwagę różnicę wysokości.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 302: Linia 302:
  
 
{{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Najgorszy przypadek, to taki, gdy przerwane jest połączenie Skąd-Dokąd w obie strony. Wtedy trzeba wykonać <math>3^{Ile}-1</math> ruchów)
+
Najgorszy przypadek to taki, gdy przerwane jest połączenie Skąd-Dokąd w obie strony. Wtedy trzeba wykonać <math>3^{Ile}-1</math> ruchów)
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 391: Linia 391:
 
''Koszt pamięciowy:'' liniowy 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.
+
''Opis:'' Aby ustawić N hetmanów, każdy z nich musi stać w osobnym wierszu. Dlatego główna procedura 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 oraz 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.
 
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.
Linia 402: Linia 402:
  
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
 
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
Zamiast rozwiązania naiwnego wymajającego <math>n^2</math> 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 <math>p(x)</math> i <math>q(x)</math> podzielimy na dolna i górną część<br>
+
Zamiast rozwiązania naiwnego wymagającego <math>n^2</math> 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 <math>p(x)</math> i <math>q(x)</math> podzielimy na dolną i górną część<br>
 
<math>p(x) = p_l(x) + p_h(x)*x^{N/2}</math> i analogicznie  
 
<math>p(x) = p_l(x) + p_h(x)*x^{N/2}</math> i analogicznie  
 
<math>q(x) = q_l(x) + q_h(x)*x^{N/2}</math>, to ich iloczyn można zapisać tak:<br>
 
<math>q(x) = q_l(x) + q_h(x)*x^{N/2}</math>, to ich iloczyn można zapisać tak:<br>
Linia 409: Linia 409:
 
<math>r_h(x) = p_h(x)*q_h(x)</math><br>
 
<math>r_h(x) = p_h(x)*q_h(x)</math><br>
 
<math>r_m(x) = (p_h(x)+p_l(x))*(q_h(x)+q_l(x))</math><br>
 
<math>r_m(x) = (p_h(x)+p_l(x))*(q_h(x)+q_l(x))</math><br>
Czyli potrzebujemy 3 mnożeń o połowę mniejszych wielomianów. W sumie uzyskamy liczbę mnożeń rzędu <math>n^{lg 3}</math>. Szczególy można znaleźć w [[Sedgewick|Sedgewick Algorithms in C++]], str. 527-530.
+
Czyli potrzebujemy 3 mnożeń o połowę mniejszych wielomianów. W sumie uzyskamy liczbę mnożeń rzędu <math>n^{lg 3}</math>. Szczegóły można znaleźć w [[Sedgewick|Sedgewick Algorithms in C++]], str. 527-530.
 
</div>
 
</div>
 
</div>}}
 
</div>}}
Linia 477: Linia 477:
 
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].
 
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.
 
</div>
 
</div>
 
</div>}}
 
</div>}}

Wersja z 08:48, 16 lis 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}}}