Rekurencja.pdf

Równania rekurencyjne

RÓWNANIAREKURENCYJNE

1. Ciągi arytmetycznei geometryczne

Znajprostszymirównaniamirekurencyjnymizetknęliśmysięjużwszkole.Zacznijmyod

przypomnieniadeﬁnicji ciąguarytmetycznego.Niechbędą danedwieliczbyrzeczywiste

a i r . Ciągiem arytmetycznym nazywamy ciąg ( a N ) liczb rzeczywistych określony

wzorami

a 0 = a, a N +1 = a N + r dla n ≥ 0 .

Ze szkoły znamy też wzór ogólny (lub wzór jawny ) ciągu arytmetycznego ( a N ):

a N = a + nr

dla n =0 , 1 , 2 ,...

W podobny sposób deﬁniujemy ciągi geometryczne. Załóżmy, że dane są liczby rze

czywiste a i q . Ciągiem geometrycznym nazywamy ciąg ( a N ) liczb rzeczywistych

zdeﬁniowany wzorami

a 0 = a, a N +1 = a N q dla n ≥ 0 .

Znów wzór ogólny ciągu geometrycznego ( a N ) jest znany ze szkoły:

a N = aq N

dla n =0 , 1 , 2 ,...

2. Wieże Hanoi

Znaczenie równań rekurencyjnych w kombinatoryce polega na tym, że wielokrotnie

umiemy dość łatwo znaleźć rozwiązanierekurencyjne zadania kombinatorycznego, pod

czas gdy znalezienie wzoru ogólnego nie jest oczywiste. Z drugiej strony, znamy wiele

metod otrzymywania wzorów ogólnych z równań rekurencyjnych. Kilka takich metod

poznamy w tym i następnym wykładzie. Zacznijmy od przykładu: zadania o tzw. wie

żach Hanoi.

Łamigłówka o nazwie „Wieże Hanoi” wygląda w następujący sposób. Mamy trzy pa

łeczki. Na jedną z nich nadziano 64 krążki w kolejności od największego na dole do

najmniejszego na górze. Należy przenieść wszystkie krążki z jednej pałeczki na drugą,

przy czym wolno za każdym razem przenosić tylko jeden krążek i nie wolno kłaść więk

szegokrążkanamniejszy.Wczasieprzenoszeniawolnokłaśćkrążkinawszystkichtrzech

pałeczkach. Ile najmniej ruchów (tzn. pojedynczych przeniesień krążków) potrzeba, by

przenieść wszystkie 64 krążki?

Oznaczmy przez H N najmniejszą liczbę ruchów, które należy wykonać by przenieść n

krążków z jednej pałeczki na inną. Jest przy tym obojętne, z której pałeczki na którą

przenosimy te krążki. Również jest obojętne, czy na tych pałeczkach już leżą jakieś

krążki, byle były one większe od wszystkich krążków, które przenosimy. Oczywiście

H 0 =0. Przypuśćmy, że umiemy przenieść n krążków w minimalnej liczbie H N ruchów.

Chcemyterazprzenieść n +1krążkówzpierwszejpałeczkinadrugą.Wktórymśmomen

cie będziemy musieli przenieść największy krążek, leżący na samym dole na pierwszej

Wykłady z kombinatoryki

Wykład 4

pałeczce. Oczywiście musimy przedtem zdjąć z niego wszystkie mniejsze krążki. Nie

mogą one też leżeć na drugiej pałeczce, bo tam mamy położyć największy krążek. Mu

simy zatemprzenieść n krążkówzpierwszej pałeczki na trzecią. Wykonamyw tymcelu

H N ruchów. Następnie przenosimy największy krążek (to jest jeden ruch) i wreszcie

przenosimy n krążków ztrzeciej pałeczki na drugą (tuznów mamy H N ruchów). Razem

wykonamywięc 2 H N +1 ruchów. Widzimy, że zjednej strony jest to minimalnaliczba

ruchów, któremusimy wykonać, a z drugiej, że ta liczba ruchów jest też wystarczająca.

Zatem otrzymujemy równanie rekurencyjne:

H 0 =0 , H N +1 =2 H N +1 dla n ≥ 0 .

Obliczmy kilka początkowych wyrazów ciągu ( H N ):

H 0 =0 ,

H 1 =2 H 0 +1=1 ,

H 2 =2 H 1 +1=3 ,

H 3 =2 H 2 +1=7 ,

H 4 =2 H 3 +1=15

i tak dalej. Łatwo domyślamy się wzoru ogólnego:

H N =2 N − 1

dla n = 0 , 1 , 2 ,... Możemy teraz sprawdzić przez indukcję, że ten odgadnięty wzór

ogólny jest poprawny.

3. Równania rekurencyjne liniowe pierwszego rzędu o stałych współczynni

kach

Niech będą dane liczby rzeczywiste a , b i c . Przypuśćmy następnie, że ciąg ( a N ) został

określony za pomocą równania rekurencyjnego

a 0 = a, a N +1 = b a N + c dla n ≥ 0 .

Ciąg ( H N ) określony wyżej otrzymamy przyjmując a = 0, b = 2 i c = 1. Przyjmijmy

ponadto, że b =1 (w przeciwnym razie mielibyśmy do czynienia z ciągiem arytmetycz

nym). Obliczmy kilka początkowych wyrazów ciągu ( a N ):

a 0 = a,

a 1 = ba 0 + c = ab + c,

a 2 = ba 1 + c = ab 2 + bc + c,

a 3 = ba 2 + c = ab 3 + b 2 c + bc + c,

a 4 = ba 3 + c = ab 4 + b 3 c + b 2 c + bc + c,

a 5 = ba 4 + c = ab 5 + b 4 c + b 3 c + b 2 c + bc + c

Wykłady z kombinatoryki

Równania rekurencyjne

i tak dalej. Znów domyślamy się wzoru ogólnego:

a N = ab N + c (1+ b + b 2 + ... + b N − 1 )= ab N + c b N − 1

b − 1

dla n =0 , 1 , 2 ,... Sprawdzimy przez indukcję, że ten wzór jest poprawny.

Dla n =0 mamy

a 0 = ab 0 + c b 0 − 1

b − 1 = a.

Przypuśćmy następnie, że nasz wzór jest spełniony dla pewnego n i obliczmy a N +1 :

ab N + c b N − 1

b − 1

+ c = ab N +1 + c b N +1 − b

b − 1

a N +1 = ba N + c = b

+ c =

= ab N +1 + c b N +1 − b + b − 1

b − 1

= ab N +1 + c b N +1 − 1

b − 1 ,

co kończy dowód indukcyjny.

Wzór ogólny tego ciągu można wyznaczyć też w inny sposób, wprowadzając ciąg po

mocniczy ( b N ) zdeﬁniowany wzorem

b N = a N +1 − a N

dla n =0 , 1 , 2 ,... Wówczas

b N +1 = a N +2 − a N +1 =( ba N +1 + c ) − ( ba N + c )= b ( a N +1 − a N )= b b N ,

skąd dostajemy

b N = b 0 b N

dla n =0 , 1 , 2 ,... Zatem

a N +1 = a N + b 0 b N

dla n =0 , 1 , 2 ,... Wypiszmy n początkowych równości:

a 1 = a 0 + b 0 b 0 ,

a 2 = a 1 + b 0 b 1 ,

a 3 = a 2 + b 0 b 2 ,

a N − 1 = a N − 2 + b 0 b N − 2 ,

a N = a N − 1 + b 0 b N − 1 .

Po dodaniu stronami tych nierówności i skróceniu występujących po obu stronach wy

razów a 1 ,a 2 ,...,a N − 1 , otrzymamy

a N = a 0 + b 0 ( b 0 + b 1 + b 2 + ... + b N − 1 )= a 0 + b 0 b N − 1

b − 1 =

= a +( ab + c − a ) b N − 1

b − 1 = a + a ( b − 1) b N − 1

b − 1 + c b N − 1

b − 1 =

= a + a ( b N − 1)+ c b N − 1

b − 1 = ab N + c b N − 1

b − 1 .

Wykłady z kombinatoryki

Wykład 4

4.Równaniarekurencyjneliniowepierwszegorzęduozmiennychwspółczyn

nikach

Rozwiążemynajpierwzadanieotzw.sortowaniuprzezłączenie. Mamy2 N monet,każda

innej wagi. Dysponujemy wagą szalkową bez odważników. Naszym zadaniem będzie

ułożenie wszystkich monet w kolejności od najcięższej do najlżejszej. Będziemy to ro

bili w następujący sposób. Najpierw podzielimy monety na dwie części po 2 N − 1 monet.

Następnie każdą z tych części uporządkujemy od najcięższej do najlżejszej. Potem po

równamy najcięższe monety z obu części i cięższą z nich odłożymy jako najcięższą ze

wszystkich. Potem porównamy najcięższe monety obu części (jedna z tych części jest

teraz mniejsza, ubyła z niej jedna moneta). Cięższą monetę odkładamy na bok jako

drugą z kolei. I tak dalej. Trzeba jeszcze wyjaśnić, w jaki sposób porządkujemy obie

części. Otóż zrobimy to w taki sam sposób. Każdą z tych części podzielimy znów na

dwie części, uporządkujemy je i połączymy ze sobą. Każdą z tych mniejszych części

znów porządkujemy tak samo: dzielimy na dwie części i potem łączymy ze sobą. I tak

dalej. Wreszcie dojdziemy do części liczących tylko dwie monety i wtedy wystarczy

jedno ważenie, by taką małą część uporządkować. Ilepotrzeba ważeń, by za pomocą tej

metody uporządkować wszystkie monety?

Oznaczmy przez P N maksymalną liczbę ważeń potrzebnych do uporządkowania 2 N mo

net w sposób opisany w zadaniu. Oczywiście P 0 = 0. Jeśli bowiem mamy 2 0 , czyli 1

monetę, to nie musimy nic ważyć. Przypuśćmy teraz, że umiemy już uporządkować 2 N

monet za pomocą P N ważeń. Spróbujmy zatem uporządkować 2 N +1 monet. Najpierw

dzielimy je na dwie części, po 2 N monet każda. Następnie porządkujemy każdą z tych

części. Do uporządkowania każdej części potrzebujemy P N ważeń. Wreszcie musimy po

łączyćobieczęści.Zauważamywięc,żekażdeważeniepozwalanamodłożyćnabok,jako

kolejną,tylkojedną monetę.Douporządkowaniawszystkich2 N +1 monet będziemywięc

potrzebowaliconajwyżej2 N +1 − 1ważeń.(Czasamitołączeniemożezakończyćsięwcze

śniej,gdyprzyodkładaniumonetnabokjedną zczęściwyczerpiemydużo wcześniejniż

drugą;napewnojednakniebędziemypotrzebowaliwiększejliczbyważeń.)Łącznamak

symalna liczba ważeń potrzebnych do uporządkowania wszystkich 2 N +1 monet wynosi

więc 2 P N +2 N +1 − 1.

Ciąg liczb ( P N ) jest zatem określony wzorami: rekurencyjnymi

P 0 =0 , P N +1 =2 P N +2 N +1 − 1 dla n ≥ 0 .

Znów obliczmy kilka początkowych wyrazów ciągu ( P N ):

P 0 =0 ,

P 1 =2 0+2 1 − 1=1 ,

P 2 =2 1+2 2 − 1=5 ,

P 3 =2 5+2 3 − 1=17 ,

P 4 =2 17+2 4 − 1=49 ,

P 5 =2 49+2 5 − 1=129 ,

P 6 =2 129+2 6 − 1=321

Wykłady z kombinatoryki

Równania rekurencyjne

i tak dalej. Tu domyśleniesię wzoru ogólnego jest trudniejsze. Można jednak zauważyć,

że

P 0 − 1= − 1=( − 1) 2 0 ,

P 1 − 1=0=0 2 1 ,

P 2 − 1=4=1 2 2 ,

P 3 − 1=16=2 2 3 ,

P 4 − 1=48=3 2 4 ,

P 5 − 1=128=4 2 5 ,

P 6 − 1=320=5 2 6

i tak dalej. Widzimy już wzór ogólny

P N =( n − 1) 2 N +1

dla n = 0 , 1 , 2 ,... Sprawdzenie poprawności tego wzoru przez indukcję jest prostym

ćwiczeniem.

5. Metodaczynnika sumacyjnego

Równanie rekurencyjne otrzymane w ostatnim paragraﬁe można rozwiązać w sposób

następujący. Rozważmy ciąg ( Q N ) określony wzorem

Q N = P N

dla n ≥ 0 .

2 N

Wówczas oczywiście Q 0 =0. Podzielmy teraz obie strony równania

P N +1 =2 P N +2 N +1 − 1

przez 2 N +1 . Otrzymamy

P N +1

2 N +1 = P N

2 N +1 − 1

2 N +1 ,

czyli

Q N +1 = Q N +1 − 1

2 N +1

dla n =0 , 1 , 2 ,... Wypiszmy teraz otrzymane zależności dla początkowych wartości n :

Q 1 = Q 0 +1 − 1

2 1 ,

Q 2 = Q 1 +1 − 1

2 2 ,

Q 3 = Q 2 +1 − 1

2 3 ,

Q 4 = Q 3 +1 − 1

2 4 ,

... ...

Q N − 1 = Q N − 2 +1 − 1

2 N − 1 ,

Q N = Q N − 1 +1 − 1

2 N .

Wykłady z kombinatoryki

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: