Wstęp do programowania/Rekursja/Ćwiczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
mNie podano opisu zmian |
|||
| 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ę | ''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 | 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 | 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 | 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 | ''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 | 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>. | 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 | 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}}}
