Pseudokody do wyk lad 3

10 marzec 2011

Przyk lad 11: Cia

,

g Fibonacciego

F

k

= F

k

−1

+ F

k

−2

,

k

≥ 2

z warunkami pocza

,

tkowymi F

0

= 0, F

1

= 1. Wyznaczy´

c F

n

FIB-1 (n)

k

← 2

F [0]

← 0

F [1]

← 1

while k

≤ n

do F [k]

← F [k − 1] + F [k − 2]

k

← k + 1

return F [n]

Przyk lad 12: Cia

,

g Fibonacciego bez u˙zycia tablicy

FIB-2 (n)

k

← 2

F 0

← 0

F 1

← 1

while k

≤ n

do F k

← F 0 + F 1

F 0

← F 1

F 1

← F k

k

← k + 1

return F k

Typeset by

AMS-TEX

1

2

Przyk lad 13: n-ty wyraz cia

,

gu Fibonacciego w czasie Θ(log n)

A =

(

1

1

1

0

)

Kolejne pote

,

gi macierzy A zawieraja

,

kolejne wyrazy cia

,

gu

Fibonacciego

Przyk lad 14: Wie˙ze Hanoi

HANOI (n, X, Y, Z)

if n = 1

then X

→ Y

else HANOI (n

− 1, X, Z, Y )

X

→ Y

HANOI (n

− 1, Z, Y, X)

Przyk lad 15: Scalanie dw´

och uporza

,

dkowanych cia

,

g´

ow

SCAL-1 (A, p, q, r)

i

← p

j

← q + 1

l

← p

while (i

≤ q) and (j ≤ r)

do if A[i]

≤ A[j]

then B[l]

← A[i]

i

← i + 1

else B[l]

← A[j]

j

← j + 1

l

← l + 1

while i

≤ q

do B[l]

← A[i]

i

← i + 1

l

← l + 1

3

while j

≤ r

do B[l]

← A[j]

j

← j + 1

l

← l + 1

for i

← p to r

do A[i]

← B[i]

Przyk lad 16: Scalanie dw´

och uporza

,

dkowanych cia

,

g´

ow - wersja

z wartownikami

SCAL-2 (A, p, q, r)

n

← q − p + 1

m

← r − q

for i

← 1 to n

do B[i]

← A[p + i − 1]

for j

← 1 to m

do C[j]

← A[q + j]

B[n + 1]

← ∞

C[m + 1]

← ∞

i

← 1

j

← 1

for k

← p to r

do if B[i]

≤ C[j]

then A[k]

← B[i]

i

← i + 1

else A[k]

← C[j]

j

← j + 1

4

Przyk lad 17: Sortowanie przez wstawianie

SORT (A, n)

for j

← 2 to n

do r

← A[j]

i

← j − 1

while i > 0 and A[i] > r

do A[i + 1]

← A[i]

i

← i − 1

A[i + 1]

← r