wyklad 11, AGH, WFiIS, Informatyka stosowana, Semestr I, matma dyskretna-misztal, wyklad
[ Pobierz całość w formacie PDF ]
Rekurencjaiindukcja
na podstawie ”Slides
c
2005, 2010 by M. J. Golin, G. Trippen”
Wykład11
22 maja 2012
(Wykład11)
Rekurencjaiindukcja
22maja2012 1/22
Outline
1
Rekurencja
2
Wie»e Hanoi
3
Równania rekurencyjne
4
Iterowanie równa« rekurencyjnych
5
Ci¡g geometryczny
6
Liniowe równanie rekurencyjne pierwszego rz¦du
(Wykład11)
Rekurencjaiindukcja
22maja2012 2/22
Rekurencja
Obiekt zwany jest rekurencyjnym, je»eli cz¦±ciowo składa si¦ z siebie
samego lub jego definicja odwołuje si¦ do niego samego.
Aby zrozumie¢ rekurencj¦, trzeba najpierw zrozumie¢ rekurencj¦.
Aby przej±¢ 100 metrów nale»y uczyni¢ pierwszy krok, a nast¦pnie
przej±¢ reszt¦ dystansu.
Rekurencja daje mo»liwo±¢ definiowania niesko«czonego zbioru
obiektów za pomoc¡ sko«czonego wyra»enia.
Przykład. Liczby naturalne:
1
1 jest liczb¡ naturaln¡;
2
nast¦pnik liczby naturalnej jest liczb¡ naturaln¡.
(Wykład11)
Rekurencjaiindukcja
22maja2012 3/22
Wie»eHanoi
3 kołki i n kr¡»ków.
Zadanie polega na tym, by przenie±¢ wszystkie kr¡»ki na prawy kołek
przestrzegaj¡c nast¦puj¡cych zasad:
1
za jednym razem zmieniamy poło»enie tylko jednego kr¡»ka,
2
»adnego kr¡»ka nie mo»na umie±ci¢ na mniejszym.
Dane s¡
i,
j2f
1,2,3
g.
Nie
ch
fi,
jg=f
1,2,3gfigfjg
.
Przykład.
f1,2g=3
,
f1,3g=2
,
f2,3g=1
.
(Wykład11)
Rekurencjaiindukcja
22maja2012 4/22
Wie»eHanoi
Aby przenie±¢
n>1
kr¡»ków z
i
na
j
:
i)
Przenosimy
n
1
pierwszych kr¡»ków z
góry z
i
na
f
i,j
g
.
ii)
Przenosimy najwi¦kszy kr¡»ek
n
z
i
na
j
.
iii)
Przenosimy
n
1
kr¡»ków z
f
i,j
g
na
j
.
(Wykład11)
Rekurencjaiindukcja
22maja2012 5/22
[ Pobierz całość w formacie PDF ]