Pseudokody do wyk ladu 2

2 marzec 2011

Przyk lad 8: Cia

,

g Fibonacciego

F

n

= F

n

−1

+ F

n

−2

,

n

≥ 2, F

0

= 0,

F

1

= 1

FIB (n)

if n = 0

then FIB

← 0

else if n = 1

then FIB

← 1

else FIB

← FIB(n − 1)+FIB(n − 2)

Drzewo wywo la´

n rekurencyjnych

Niech T (n) oznacza liczbe

,

we

,

z l´

ow w drzewie rekurencyjnym odpo-

wiadaja

,

cym algorytmowi. Np. T (5) = 15, T (6) = 25, ...

Twierdzenie 2. Dla n

≥ 2

T (n) > 2

n/2

Dow´

od (indukcja wzgle

,

dem n). Dla n = 2 oczywiste, bo T (2) = 3.

Za l´

o˙zmy, ˙ze

T (m) > 2

m/2

dla

2

≤ m < n

Z zale˙zno´

sci rekurencyjnej

T (n) = T (n

− 1) + T (n − 2) + 1

Typeset by

AMS-TEX

1

2

Na mocy za lo˙zenia indukcyjnego

T (n) > 2

(n

−1)/2

+ 2

(n

−2)/2

+ 1

> 2

(n

−2)/2

+ 2

(n

−2)/2

= 2

n/2

Przyk lad 9: Najwie

,

kszy wsp´

olny dzielnik

N W D(a, b) = N W D(b, a mod b)

a i b dowolne nieujemne liczby ca lkowite

NWD (a, b)

if b = 0

then NWD

← a

else NWD

← NWD(b, a mod b)

NWD (a, b)

if b = 0

then return a
else return NWD(b, a mod b)

Twierdzenie 3. Je˙zeli a > b

≥ 0 i wywo lanie NWD(a, b) prowadzi

do k

≥ 1 wywo la´n rekurencyjnych, to

a

≥ F

k+2

i

b

≥ F

k+1

Dow´

od. Indukcja wzgle

,

dem k. Dla k = 1

b

≥ 1 = F

2

a skoro a > b, to musi by´

c

a

≥ 2 = F

3

3

Poiewa˙z b > (a mod b), w ka˙zdym wywo laniu rekurencyjnym
pierwszy argument jest ostro wie

,

kszy ni˙z drugi; za lo˙zenie, ˙ze a > b,

jest wie

,

c zachowane w ka˙zdym wywo laniu rekurencyjnym.

Przyjmijmy za lo˙zenie indukcyjne, ˙ze twierdzenie jest prawdziwe,

je´

sli wykonuje sie

,

k

− 1 wywo la´n rekurencyjnych; poka˙zemy ˙ze za-

chodzi ono r´

ownie˙z dla k wywo la´

n. Poniewa˙z k > 0, mamy b > 0,

wie

,

c NWD(a, b) wywo luje rekurencyjnie NWD(b, a mod b), co z

kolei prowadzi do k

− 1 wywo la´n rekurencyjnych.

Z za lo˙zenia indukcyjnego wynika, ˙ze b

≥ F

k+1

(co dowodzi

cze

,

´

sci tezy twierdzenia) i ˙ze (a mod b)

≥ F

k

. Mamy

b + (a

mod b) = b + (a

− ⌊a/b⌋b) ≤ a

poniewa˙z skoro a > b > 0, to

⌊a/b⌋ ≥ 1. Sta

,

d

a

≥ b + (a mod b) ≥ F

k+1

+ F

k

= F

k+2

Wniosek. Dla dowolnej liczby ca lkowitej k

≥ 1, je´sli a > b ≥ 0

oraz b < F

k+1

, to wykonanie NWD(a, b) powoduje mniej ni˙z k

wywo la´

n rekurencyjnych.

Przyk lad 10: Wyszukiwanie binarne

Zak ladamy, ˙ze

A[1]

≤ A[2] ≤ . . . ≤ A[n]

ELEMENT (A, n, x)

i

← 1

j

← n

repeat k

← (i + j) div 2

if x > A[k]

then i

← k + 1

else j

← k − 1

until (A[k] = x) or (i > j)

if A[k] = x

then return k
else drukuj komunikat

4

Z lo ˙zono´

s´

c algorytm´

ow typu ,,dziel i zwycie

,

˙zaj”

T (n) – ,,czas” dzia lania dla problemu rozmiaru n

D(n) – ,,czas” dzielenia problemu na podproblemy

C(n) – ,,czas” la

,

czenia rozwia

,

za´

n podproblem´

ow

n/b – rozmiar ka˙zdego podproblemu

a – liczba podproblem´

ow

T (n) = aT (n/b) + D(n) + C(n)