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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m
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 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>}}
Linia 111: Linia 111:
  
 
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 535: Linia 535:
 
|}
 
|}
  
−
<!-- 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>}}
 
-->
 
-->

Wersja z 20:45, 3 gru 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ść). 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 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}}}


Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Wstęp_do_programowania/Rekursja/Ćwiczenia&oldid=66913”