ZLICZANIE SEM ZMNIiTI
Strona tytułowa
REKURENCYJNE
Andrzej Sendlewski
Wydział Matematyki i Informatyki UMK w Toruniu
Następny slaid
Poprzedni slaid
Pełny ekran
MA-TA II, Ciechanów 22 maja 2010
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
c& Liczby figuralne jako
jeden z najprostszych
sposobów wprowadzenia w
Następny slaid
myślenie rekurencyjne
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 1. Rysujemy kolejne kwadraty
o bokach długości całkowitej i dzielimy je na
SEM ZMNIiTI
kwadraty jednostkowe.
Strona tytułowa
Następny slaid
1 2 3 4
Poprzedni slaid
Z ilu kwadratów jednostkowych składa się
Pełny ekran
kwadrat o boku długości n?
Ile jest wszystkich kwadratów na n-tym ry- Zamknij plik
sunku?
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
Następny slaid
3 4
Poprzedni slaid
ńł
Pełny ekran
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
k(n) =
�ł
�ł
�ł
�ł
ół k(n - 1) + 2n - 1, jeżeli n > 0.
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
2 3 4
Następny slaid
ńł
Poprzedni slaid
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
�ł
�ł
�ł
�ł
�ł
k(n) = 4, jeżeli n = 2;
Pełny ekran
�ł
�ł
�ł
�ł
�ł
�ł
�ł
�ł
�ł
ół k(n - 2) + 4n - 4, jeżeli n > 0.
Zamknij plik
Koniec pokazu
PROBLEM 2. Rysujemy kolejne trójkąty
o bokach długości całkowitej i dzielimy je na
przystające trójkąty o boku 1.
SEM ZMNIiTI
Strona tytułowa
Następny slaid
2 3 4
1
Poprzedni slaid
Z ilu małych trójkątów składa się trójkąt
Pełny ekran
o boku długości n?
Zamknij plik
Ile jest wszystkich trójkątów równobocz-
nych na n-tym rysunku?
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
Następny slaid
3 4
Poprzedni slaid
ńł
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
Pełny ekran
k(n) =
�ł
�ł
�ł
�ł
ół k(n - 1) + n + (n - 1), jeżeli n > 0.
Zamknij plik
Koniec pokazu
PROBLEM 3. Z jednakowych monet ukła-
SEM ZMNIiTI
damy kolejne  trójkąty równoboczne , tak
jak na rysunku.
Strona tytułowa
Następny slaid
Poprzedni slaid
1 2 3 4
Pełny ekran
Jaka jest wartość monet tworzących n ty
trójkąt?
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
Następny slaid
3 4
Poprzedni slaid
Pełny ekran
ńł
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
t(n) =
�ł
�ł Zamknij plik
�ł
�ł
ół t(n - 1) + n, jeżeli n > 1.
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
1 2 3 4
Następny slaid
Poprzedni slaid
1 2 3 4
Pełny ekran
Zamknij plik
k(n) = t(n) + t(n - 1)
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
1 2 3 4
Z równości
Następny slaid
(n + 1)2 = k(n + 1) = 2t(n) + (n + 1)
Poprzedni slaid
mamy
Pełny ekran
n(n + 1)
t(n) =
2
Zamknij plik
Koniec pokazu
PROBLEM 4. Z jednakowych sześcien-
SEM ZMNIiTI
nych klocków budujemy kolejne piramidy
trójkątne, jak na rysunku.
Strona tytułowa
Następny slaid
Poprzedni slaid
1
2
3
4
Pełny ekran
Z ilu sześciennych klocków zbudowana jest
n ta piramida trójkątna?
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
4
3
Następny slaid
Żółta ściana zbudowana jest z t(n) sześcien- Poprzedni slaid
nych klocków, a więc
Pełny ekran
ńł
�ł
�ł
�ł
�ł
1, jeżeli n = 1;
�ł
�ł
�ł
�ł
Zamknij plik
pt(n) =
n(n + 1)
�ł
�ł
�ł
�ł
�ł
�ł pt(n - 1) + , jeżeli n > 1.
�ł
ół
2
Koniec pokazu
PROBLEM 5. Z jednakowych sześcien-
SEM ZMNIiTI
nych klocków budujemy kolejne piramidy
 kwadratowe , jak na rysunku
Strona tytułowa
Następny slaid
1
Poprzedni slaid
2
3
4
Pełny ekran
Z ilu sześciennych klocków zbudowana jest
n ta piramida?
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
Następny slaid
3
4
Poprzedni slaid
Żółta podstawa zbudowana jest z k(n) sze-
ściennych klocków, a więc
Pełny ekran
ńł
�ł
�ł
�ł
�ł
1, jeżeli n = 1;
�ł
Zamknij plik
p(n) =
�ł
�ł
�ł
�ł
ół
p(n - 1) + n2, jeżeli n > 1.
Koniec pokazu
f& Co wspólnego z ciągiem
SEM ZMNIiTI
Strona tytułowa
Fibonacci ego ma:
bieganie po schodach,
Następny slaid
układanie kafelków,
Poprzedni slaid
gra w koszykówkę,
Pełny ekran
liczenie kodów kreskowych?
Zamknij plik
Koniec pokazu
PROBLEM 6. Na taras wieży widokowej
prowadzą schody o n stopniach.
SEM ZMNIiTI
n
n-1
Strona tytułowa
n-2
3
Następny slaid
2
Poprzedni slaid
1
0
Pełny ekran
Turysta wchodzi na taras wykonując lo-
sowo kroki co 1 albo co 2 stopnie. Na ile spo-
Zamknij plik
sobów turysta może przejść schody?
Koniec pokazu
n
SEM ZMNIiTI
n-1
n-2
Strona tytułowa
3
2
Następny slaid
1
0
Poprzedni slaid
ńł
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
Pełny ekran
�ł
�ł
�ł
�ł
�ł
s(n) = 2, jeżeli n = 2;
�ł
�ł
�ł
�ł
�ł
�ł Zamknij plik
�ł
�ł
�ł
ół s(n - 2) + s(n - 1), jeżeli n > 2.
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
PROBLEM 7. Mamy pokryć prostokątny
pas podłogi o wymiarach n�2 prostokątnymi
kafelkami o wymiarach 2 � 1. (kafelków nie
wolno łamać.) Na ile sposobów możemy to
Następny slaid
zrobić?
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
1 2 2
SEM ZMNIiTI
Strona tytułowa
3 3
3
Następny slaid
n-1 1 n-2 2
Poprzedni slaid
ńł
�ł
�ł
�ł
�ł
�ł 1, jeżeli n = 1;
�ł
Pełny ekran
�ł
�ł
�ł
�ł
s(n) = 2, jeżeli n = 2;
�ł
�ł
�ł
�ł
�ł
�ł
Zamknij plik
�ł
�ł
�ł
ół s(n - 2) + s(n - 1), jeżeli n > 2.
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
PROBLEM 8. Ile jest sposobów zdobycia
n punktów w meczu koszykówki przez jedną
z drużyn?
Następny slaid
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
+3
SEM ZMNIiTI
Strona tytułowa
+2
+1 +1
+1
0 1 2 3
Następny slaid
+2
Poprzedni slaid
l(1) = 1, l(2) = 2, l(3) = 4.
Pełny ekran
Zamknij plik
Koniec pokazu
+3
SEM ZMNIiTI
+2
Strona tytułowa
+1
n-3 n-2 n-1 n
Następny slaid
ńł
�ł
�ł
1, jeżeli n = 1;
�ł
�ł
Poprzedni slaid
�ł
�ł
�ł
�ł
�ł
2, jeżeli n = 2;
l(n) =
�ł
�ł
�ł 4, jeżeli n = 3;
�ł
�ł
�ł Pełny ekran
�ł
�ł
ół
l(n - 3) + l(n - 2) + l(n - 1), jeżeli n > 3.
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
n 1 2 3 4 5 6 7 8 9 10 11 12
l(n) 1 2 4 7 13 24 44 81 149 274 504 927
Następny slaid
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 9.(porównaj Junior 2010, py-
tanie 30)
Pasek kodu kreskowego tworzą na przemian
SEM ZMNIiTI
kreski czarne i białe. Kod ten zawsze zaczyna
się i kończy czarną kreską. Każda z kresek
Strona tytułowa
(czy to czarna, czy biała) ma grubość 1 albo
2 (przykładowy kod na rysunku).
Następny slaid
Poprzedni slaid
n
Pełny ekran
Ile jest pasków długości n o różnych ko-
dach (kody zawsze czytamy od lewej do pra-
Zamknij plik
wej strony)?
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
2 3
1
Następny slaid
4 4 4
Poprzedni slaid
L(1) = 1, L(2) = 1, L(3) = 1, L(4) = 3. Pełny ekran
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
n-2 n-3
Strona tytułowa
n n
Następny slaid
n-3 n-4
Poprzedni slaid
n n
Pełny ekran
L(n) = L(n - 2) + 2 � L(n - 3) + L(n - 4)
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
n 1 2 3 4 5 6 7 8 9 10 11 12 13
L(n) 1 1 1 3 4 6 11 17 27 45 72 116 189
Następny slaid
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
e& Zbiór skończony i jego
podzbiory, rozkłady zbioru
Następny slaid
w rodziny podzbiorów
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 10. Zbiór X ma n elementów.
Ile jest różnych podzbiorów zbioru X o k ele-
mentach?
SEM ZMNIiTI
Strona tytułowa
Jeśli k > n, to nie istnieje żaden podzbiór
zbioru X o k elementach. Załóżmy więc, że
0 k n.
Następny slaid
Poprzedni slaid
Niech
Pełny ekran
C(n, k)
oznacza liczbę wszystkich k elementowych
Zamknij plik
podzbiorów zbioru X.
Koniec pokazu
Oczywiście
C(n, 0) = 1, C(n, n) = 1.
SEM ZMNIiTI
Ustalmy element x " X. Niech Y będzie do-
wolnym k elementowym podzbiorem zbioru
Strona tytułowa
X. Mamy dwa przypadki: x " Y albo x " Y
/
x
x
Następny slaid
Y
Y Poprzedni slaid
X
X
Pełny ekran
Zamknij plik
C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
Koniec pokazu
Trójkąt Pascala
SEM ZMNIiTI
n k 0 1 2 3 4 5 6 7 8 9
0 1
Strona tytułowa
1 1 1
2 1 2 1
3 1 3 3 1
Następny slaid
4 1 4 6 4 1
5 1 5 10 10 5 1
Poprzedni slaid
6 1 6 15 20 15 6 1
Pełny ekran
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
Zamknij plik
9 1 9 36 84 126 126 84 36 9 1
Koniec pokazu
PROBLEM 11. Danych jest n różnoko-
lorowych kredek. Kredki te rozkładamy do
k jednakowych (nierozróżnialnych) pudełek
SEM ZMNIiTI
tak, że w każdym z tych pudełek znajdzie się
przynajmniej jedna kredka. Na ile sposobów
Strona tytułowa
możemy to zrobić?
Niech X oznacza zbiór kredek. Każde roz-
łożenie kredek do k pudełek powoduje roz-
Następny slaid
bicie zbioru X na k niepustych podzbiorów
X1, X2, . . . , Xk.
Poprzedni slaid
Oznaczmy poszukiwaną liczbę przez
Pełny ekran
S(n, k).
Zamknij plik
Koniec pokazu
Jeśli k > n, to żądany rozkład jest niemoż-
SEM ZMNIiTI
liwy. Załóżmy więc, że 1 k n. Gdy k = 1,
to jedyną klasą musi być cały zbiór X, więc:
Strona tytułowa
S(n, 1) = 1 .
Podobnie, gdy k = n, to jedynym roz-
Następny slaid
kładem jest rodzina zbiorów jednoelemento-
wych {{z}; z " X}, więc:
Poprzedni slaid
S(n, n) = 1 .
Pełny ekran
Zamknij plik
Koniec pokazu
Niech 1 < k < n. Ustalmy element x " X. Je-
żeli wez
miemy dowolny rozkład zbioru X na
k klas, to mamy dwa przypadki: albo {x} jest
SEM ZMNIiTI
klasą tego rozkładu, albo {x} nie jest klasą
tego rozkładu
Strona tytułowa
klasa {x}
x
x
k-1 klas
k klas
Następny slaid
Poprzedni slaid
X-{x}
X
Pełny ekran
Zamknij plik
S(n, k) = S(n - 1, k - 1) + k � S(n - 1, k)
Koniec pokazu
Liczby Stirlinga
SEM ZMNIiTI
n k 1 2 3 4 5 6 7 8 9 10
Strona tytułowa
1 1
2 1 1
3 1 3 1
4 1 7 6 1
Następny slaid
5 1 15 25 10 1
6 1 31 90 65 15 1
Poprzedni slaid
7 1 63 301 350 140 21 1
8 1 127 966 1701 1050 266 28 1
Pełny ekran
9 1 255 3025 7770 6951 2646 462 36 1
10 1 511 9330 34105 42525 22827 5880 750 45 1
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Strona tytułowa
`& O pewnym meczu
piłkarskim, czyli o zliczaniu
ścieżek w grafie
Następny slaid
skierowanym
Poprzedni slaid
Pełny ekran
Zamknij plik
Koniec pokazu
PROBLEM 12. (porównaj Junior 2006,
pytanie 30)
W meczu piłki ręcznej drużyna gospodarzy
SEM ZMNIiTI
objęła prowadzenie i utrzymała je do stanu
n : k (oczywiście n > k). Na ile sposobów mo-
Strona tytułowa
gły padać bramki w tym meczu do tego mo-
mentu?
Zilustrujmy możliwy przebieg meczu do
stanu n : k, n > k, za pomocą grafu zorien-
Następny slaid
towanego. Wynikowi x : y przyporządkujmy
punkt kratowy o współrzędnych (x, y), a
Poprzedni slaid
punkty (x, y) łączymy strzałkami z punktami
Pełny ekran
(u, v), gdy wynik u : v jest możliwym wyni-
kiem bezpośrednio po wyniku x : y. Graf taki
Zamknij plik
dla n = 6 i k = 5 przedstawia rysunek na na-
stępnym slajdzie.
Koniec pokazu
y
B
5
SEM ZMNIiTI
4
Strona tytułowa
3
Następny slaid
2
Poprzedni slaid
1
Pełny ekran
x
Zamknij plik
O 1 2 3 4 5 6
Koniec pokazu
Oznaczmy przez w(n, k) liczbę wszystkich
ścieżek prowadzących od punktu (0, 0) do
punktu (n, k). Mamy:
SEM ZMNIiTI
a) jeżeli k = 0, to
Strona tytułowa
w(0, 0) = 0 oraz w(n, 0) = 1
dla n > 0;
b) jeżeli k = 1, to
Następny slaid
Poprzedni slaid
w(2, 1) = 1
oraz Pełny ekran
w(n, 1) = w(n, 0) + w(n - 1, 1)
Zamknij plik
Koniec pokazu
dla n > 2;
c) jeżeli 1 < k < n - 1, to
SEM ZMNIiTI
w(n, k) = w(n, k - 1) + w(n - 1, k)
Strona tytułowa
d) jeżeli k = n - 1, to
w(n, k) = w(n, k - 1) ,
Następny slaid
czyli
Poprzedni slaid
Pełny ekran
w(n, n - 1) = w(n, n - 2) .
Zamknij plik
Koniec pokazu
Tabela wartości w(n, k)
SEM ZMNIiTI
n k 0 1 2 3 4 5 6 7 8 9
Strona tytułowa
0 0
1 1
2 1 1
3 1 2 2
4 1 3 5 5
Następny slaid
5 1 4 9 14 14
6 1 5 14 28 42 42
Poprzedni slaid
7 1 6 20 48 90 132 132
8 1 7 27 75 165 297 429 429
Pełny ekran
9 1 8 35 110 275 572 1001 1430 1430
10 1 9 44 154 429 1001 2002 3432 4862 4862
Zamknij plik
Koniec pokazu
SEM ZMNIiTI
Większe wartości w(n, k) mogące być
Strona tytułowa
wynikami rzeczywistego meczu:
w(20, 15) = 463991880,
w(20, 16) = 811985790,
Następny slaid
w(20, 17) = 1289624490,
w(20, 18) = 1767263190, Poprzedni slaid
w(20, 19) = 1767263190.
Pełny ekran
Zamknij plik
Koniec pokazu