Wstęp do programowania/Rekursja/Ćwiczenia: Różnice pomiędzy wersjami
| 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, | '''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 --> | // rozkłady wpisujemy do tablicy T; pierwsze wolne miejsce to ti+1 | ||
// 0 <= | // 0 <= ti <= n | ||
// | // ti > 0 --> maxSkł=T[ti] | ||
// 0 <= co | |||
// co=0 --> ti > 0 | |||
'''var''' i:integer | '''var''' i:integer | ||
'''begin''' | '''begin''' | ||
'''if''' | '''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( | '''for''' i:=min(co,maxSkł) '''downto''' 1 '''do''' '''begin''' | ||
T[ti]:=i; | T[ti]:=i; | ||
rozklad(T,ti,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 | ''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 | 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 | 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 | 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
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ść). 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
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 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
Wskazówka 2
Rozwiązanie 1
