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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 22 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
{{powrot|Wstęp do programowania/Rekursja|do modułu Rekursja}}
 
 
 
To są zadania na rekursję.
 
To są zadania na rekursję.
  
Linia 13: Linia 11:
 
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.)
 
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.)
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
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.
 
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.
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Labirynt(M,N:integer; '''var''' A:'''array'''[1..M,1..N] '''of''' integer; i1,j1,i2,j2:integer):boolean;
 
  '''function''' Labirynt(M,N:integer; '''var''' A:'''array'''[1..M,1..N] '''of''' integer; i1,j1,i2,j2:integer):boolean;
 
  // M,N >= 1
 
  // M,N >= 1
Linia 61: Linia 63:
 
''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 75: Linia 77:
 
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 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.
  
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').
+
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').
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Ile razy maksymalnie może być wywołana funkcja 'szukaj' dla tego samego punktu?
 
Ile razy maksymalnie może być wywołana funkcja 'szukaj' dla tego samego punktu?
 
</div>
 
</div>
</div>}}
+
</div>
  
{{cwiczenie| 2|pytanko 2|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
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 ?
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 2</span>
 +
<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 ?
 +
</div>
 
</div>
 
</div>
</div>}}
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 3</span>
{{cwiczenie| 3|pytanko 3|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible-content" style="display:none">
 
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ść?
 
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ść?
 
</div>
 
</div>
</div>}}
+
</div>
  
{{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
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.
 
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.
 
</div>
 
</div>
</div>}}
+
</div>
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 113: Linia 122:
  
 
W tablicy liczb całkowitych o rozmiarze M&times;N zapisana jest mapa
 
W tablicy liczb całkowitych o rozmiarze M&times;N zapisana jest mapa
gór (każdy punkt ma podaną dodatnią wysokość). Sprawdzić, czy da się
+
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:
 
przejść z punktu startowego (i1,j1) do docelowego (i2,j2) idąc:
 
* tylko w dół lub po płaskim
 
* tylko w dół lub po płaskim
Linia 119: Linia 128:
 
Tak jak w poprzednim zadaniu poruszać się można tylko w czterech kierunkach podstawowych, nie po przekątnej.
 
Tak jak w poprzednim zadaniu poruszać się można tylko w czterech kierunkach podstawowych, nie po przekątnej.
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
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.
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<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.
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Zjazd1(M,N:integer; '''var''' A:'''array'''[1..M,1..N] '''of''' integer; i1,j1,i2,j2:integer):boolean;
 
  '''function''' Zjazd1(M,N:integer; '''var''' A:'''array'''[1..M,1..N] '''of''' integer; i1,j1,i2,j2:integer):boolean;
 
  // M,N >= 1
 
  // M,N >= 1
Linia 137: Linia 150:
 
   '''begin'''
 
   '''begin'''
 
     jest:=false;
 
     jest:=false;
     '''if''' (A[i,j]>0) '''and''' (h>A[i,j]) '''begin''' // h>=A[i,j] w wariancie II
+
     '''if''' (A[i,j]>0) '''and''' (h>A[i,j])'''then''' '''begin''' // h>=A[i,j] w wariancie II
 
       '''if''' (i=i2) '''and''' (j=j2) '''then'''  
 
       '''if''' (i=i2) '''and''' (j=j2) '''then'''  
 
         jest:=true  
 
         jest:=true  
Linia 174: Linia 187:
 
''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.
 
''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.
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 2</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''function''' Zjazd2(M,N:integer; '''var''' A:'''array'''[1..M,1..N] '''of''' integer; i1,j1,i2,j2:integer):boolean;
 
  '''function''' Zjazd2(M,N:integer; '''var''' A:'''array'''[1..M,1..N] '''of''' integer; i1,j1,i2,j2:integer):boolean;
 
  // M,N >= 1
 
  // M,N >= 1
Linia 230: Linia 245:
 
''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'.
 
''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'.
 
</div>
 
</div>
</div>}}
+
</div>
  
 
==Zadanie 3 (Wieże Hanoi z ograniczeniami)==
 
==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.
+
Na wykładzie omawiane były [[Wstęp do programowania/Rekursja#wieze Hanoi|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.
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
* Dozwolone ruchy najlepiej reprezentować w tablicy typu TDozwRuchow = array[1..3, 1..3] of boolean, (przekątna nie ma znaczenia).
 
* Dozwolone ruchy najlepiej reprezentować w tablicy typu TDozwRuchow = array[1..3, 1..3] of boolean, (przekątna nie ma znaczenia).
 
* Zastanów się, jaki warunek musi być spełniony przez tablicę dozwolonych ruchów, aby zadanie miało rozwiązanie.
 
* Zastanów się, jaki warunek musi być spełniony przez tablicę dozwolonych ruchów, aby zadanie miało rozwiązanie.
 
* Użyj funkcji-otoczki do wstępnego sprawdzenia czy istnieje rozwiązanie oraz do pamiętania tablicy dozwolonych ruchów w czasie działania funkcji rekurencyjnej.  
 
* Użyj funkcji-otoczki do wstępnego sprawdzenia czy istnieje rozwiązanie oraz do pamiętania tablicy dozwolonych ruchów w czasie działania funkcji rekurencyjnej.  
 
</div>
 
</div>
</div>}}
+
</div>
  
 
<!--   
 
<!--   
Linia 249: Linia 266:
 
end;  
 
end;  
 
-->
 
-->
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''type''' Paleczki = 1..3;
 
  '''type''' Paleczki = 1..3;
 
   
 
   
Linia 279: Linia 298:
 
     '''end'''
 
     '''end'''
 
     '''else'''
 
     '''else'''
       CzyDaSie:=false
+
       CzyDaSie:=true
 
   '''end''' // CzyDaSie     
 
   '''end''' // CzyDaSie     
 
   
 
   
  '''var''' ok:boolean
+
  '''var''' ok:boolean;
 +
  i,j:integer;
 
  '''begin''' // Hanoi
 
  '''begin''' // Hanoi
 
   ok:=true;
 
   ok:=true;
Linia 296: Linia 316:
 
''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).
 
''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).
 
</div>
 
</div>
</div>}}
+
</div>
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
{{cwiczenie| 1|pytanko 1|<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Ćwiczenie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Jaki przypadek jest najgorszy i ile trzeba wykonać wtedy ruchów?
 
Jaki przypadek jest najgorszy i ile trzeba wykonać wtedy ruchów?
 
</div>
 
</div>
</div>}}
+
</div>
  
{{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
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)
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
 +
<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)
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
==Zadanie 4 (Ustawianie hetmanó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.
 
Napisz procedurę znajdująca wszystkie takie rozstawienia 8 hetmanów na szachownicy, by żadne dwa hetmany się nie atakowały.
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
W tablicach logicznych pamiętamy zajętość kolumn i obu rodzajów przekątnych, kolejnego hetmana ustawiamy w kolejnym wierszu jeśli się da, jeśli nie wracamy.  
 
W tablicach logicznych pamiętamy zajętość kolumn i obu rodzajów przekątnych, kolejnego hetmana ustawiamy w kolejnym wierszu jeśli się da, jeśli nie wracamy.  
  
Linia 318: Linia 343:
 
Oczywiście lepiej uogólnić na N hetmanów na szachownicy N×N.
 
Oczywiście lepiej uogólnić na N hetmanów na szachownicy N×N.
 
</div>
 
</div>
</div>}}
+
</div>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''procedure''' Hetmany(N:integer);
 
  '''procedure''' Hetmany(N:integer);
 
  // N >= 1
 
  // N >= 1
Linia 347: Linia 374:
 
   '''end'''; // odstaw
 
   '''end'''; // odstaw
 
      
 
      
   '''function''' wolne(k,i:integer):boolean
+
   '''function''' wolne(k,i:integer):boolean;
 
   // 1 <= k,i <= N
 
   // 1 <= k,i <= N
 
   '''begin'''
 
   '''begin'''
     wolne:='''not''' kolumny[i] & '''not''' przekgd[k-i] & '''not''' przekdg[k+i]
+
     wolne:='''not''' kolumny[i] & '''not''' przekgd[k-i] & '''not''' przekdg[k+i];
 
   '''end'''; // wolne
 
   '''end'''; // wolne
 
   
 
   
Linia 359: Linia 386:
 
   '''begin'''
 
   '''begin'''
 
     jest:=true;
 
     jest:=true;
     write('Ustawienie: ')
+
     write('Ustawienie: ');
     '''for''' i:=1 '''to''' N; '''do''' write(i,':',wiersze[i],' ')
+
     '''for''' i:=1 '''to''' N '''do''' write(i,':',wiersze[i],' ');
 
     writeln;
 
     writeln;
 
   '''end'''; // wypisz
 
   '''end'''; // wypisz
Linia 385: Linia 412:
 
   '''for''' i:=2 '''to''' 2*N '''do''' przekdg[i]:=false;
 
   '''for''' i:=2 '''to''' 2*N '''do''' przekdg[i]:=false;
 
   jest:=false;
 
   jest:=false;
   rozstaw(i);
+
   rozstaw(1);
 
   '''if''' '''not''' jest '''then''' writeln('Nie znaleziono żadnego ustawienia')
 
   '''if''' '''not''' jest '''then''' writeln('Nie znaleziono żadnego ustawienia')
 
  '''end''' // Hetmany
 
  '''end''' // Hetmany
Linia 393: Linia 420:
 
''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.
  
 
</div>
 
</div>
</div>}}
+
</div>
  
 
==Zadanie 5 (Mnożenie wielomianów)==
 
==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.
 
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.
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
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>
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 +
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 411: Linia 440:
 
<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>}}
 
  
 
==Zadanie 6 (Suma składników)==
 
==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:<br>
+
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:<br>
 
3 = 3<br>
 
3 = 3<br>
 
3 = 2+1<br>
 
3 = 2+1<br>
 
3 = 1+1+1
 
3 = 1+1+1
  
{{wskazowka| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Użyj dodatkowej tablicy do przechowywania początków rozkładów. Uważaj, aby nie kopiować tej tablicy przy każdym wywołaniu rekurencyjnym!
 
Użyj dodatkowej tablicy do przechowywania początków rozkładów. Uważaj, aby nie kopiować tej tablicy przy każdym wywołaniu rekurencyjnym!
 
</div>
 
</div>
</div>}}
+
</div>
  
{{wskazowka| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
Funkcja rekurencyjna powinna mieć parametr wskazujący jak duże składniki mogą być użyte do rozkładu pozostałej liczby. </div>
 
Funkcja rekurencyjna powinna mieć parametr wskazujący jak duże składniki mogą być użyte do rozkładu pozostałej liczby. </div>
</div>}}
+
</div>
  
{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
  '''procedure''' Suma(n:integer);
 
  '''procedure''' Suma(n:integer);
 
  // 1 <= n
 
  // 1 <= n
 
   '''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 450: Linia 487:
 
     '''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,co-i,i);
 
       '''end'''
 
       '''end'''
 
     '''end'''
 
     '''end'''
Linia 465: Linia 502:
 
''Koszt pamięciowy:'' liniowy względem n
 
''Koszt pamięciowy:'' liniowy względem n
  
[http://www.mimuw.edu.pl/~annan/modul2_19_1.html Wizualizacja]
+
[http://wazniak.mimuw.edu.pl/external/pimpek/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.
 +
</div>
 
</div>
 
</div>
</div>}}
 
  
 
<!-- to zadanie tu nie pasuje, wymaga zdecydowanie rekordow z wariantami...
 
<!-- to zadanie tu nie pasuje, wymaga zdecydowanie rekordow z wariantami...
Linia 535: Linia 572:
 
|}
 
|}
  
<!-- to między || i pierwszą | to są parametry komórki, więc żeby wpisać w komórce kreskę, to trzeba zacząc komórkę od _spacja_kreska_  :) - - >
+
<!-- to między || i pierwszą | to są parametry komórki, więc żeby wpisać w komórce kreskę, to trzeba zacząć komórkę od _spacja_kreska_  :) - - >
  
 
{{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">
W tym zadaniu chodzi o przećwiczenie metody zejść rekurencyjnych (była na wykładzie). Niestety na razie nie mamy dostatecznie ciekawych typów danych, żeby móc zapamiętać strukturę danych programu (i np. po tem go wykonywać). Tym nie mniej zadanie jest pouczające. Typ danych który ma być wymyślony to rekord z wariantami. Można uatrakcyjnić to zadanie każąc sprawdzać, czy każda użyta zmienna była wcześniej zadeklarowana i czy nie była deklarowana kilkakrotnie (tablica napisów).
+
W tym zadaniu chodzi o przećwiczenie metody zejść rekurencyjnych (była na wykładzie). Niestety na razie nie mamy dostatecznie ciekawych typów danych, żeby móc zapamiętać strukturę danych programu (i np. potem go wykonywać). Niemniej zadanie jest pouczające. Typ danych, który ma być wymyślony, to rekord z wariantami. Można uatrakcyjnić to zadanie każąc sprawdzać, czy każda użyta zmienna była wcześniej zadeklarowana i czy nie była deklarowana kilkakrotnie (tablica napisów).
 
</div>
 
</div>
 
</div>}}
 
</div>}}
 
-->
 
-->

Aktualna wersja na dzień 16:23, 28 maj 2020

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

Rozwiązanie 1

Ćwiczenie 1

Ćwiczenie 2

Ćwiczenie 3

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

Rozwiązanie 1

Rozwiązanie 2

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

Rozwiązanie 1

Ćwiczenie 1

Odpowiedź

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

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

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

Wskazówka 2

Rozwiązanie 1