BAL - ¢wiczenia nr 2

20 pa¹dziernika 2011

Algorithm 1 Konwersja DEC2BIN - wersja naturalna
DANE: a - konwertowana liczba zapisana w systemie dziesi¦tnym

pot˛ega ← 1

powtarzaj:

pot˛ega ← pot˛ega · 2

a» do: pot˛ega > a

powtarzaj:

pot˛ega ← pot˛ega/2
drukuj: [a/pot˛ega]
a ← M od(a, pot˛ega)

a» do: pot˛ega = 1

Algorithm 2 Konwersja DEC2BIN - wersja na tablicach
DANE: a - konwertowana liczba zapisana w systemie dziesi¦tnym

i ← 1

powtarzaj:

T AB

i

← M od(a, 2)

i ← i + 1
a ← [a/2]

a» do: a = 0

powtarzaj:

i ← i − 1
drukuj: T AB

i

a» do: i = 1

Algorytm wykorzystuje pomocnicz¡ tablic¦, w której przechowuje kolejne

cyfry rozwini¦cia binarnego, które zwraca we wªa±ciwej kolejno±ci, drukuj¡c je

pocz¡wszy od ostatniego elementu tablicy, a» do pierwszego. Algorytm zacho-

wuje si¦ poprawnie tak»e dla a = 0.

1

Algorithm 3 Przeszukiwanie jednowymiarowych tablic nieuporz¡dkowanych -

przeszukiwanie liniowe
DANE: T AB(N) - N -elementowa jednowymiarowa tablica (wektor)

x - szukany element

i ← 1

dopóki T AB

i

6= x

oraz i ≤ N powtarzaj:

i ← i + 1

zako«cz iteracj¦

je±li i ≤ N

drukuj: Szukany element znajduje si¦ na miejscu, i

w przeciwnym przypadku

drukuj: Szukanego elementu nie ma w tablicy

Algorytm nie jest specjalnie porywaj¡cy, jednak w tym przypadku trudno

byªo si¦ spodziewa¢ czego± nadzwyczajnego.

Algorithm 4 Szukanie najwi¦kszego elementu w tablicy nieuporz¡dkowanej
DANE: T AB(N) - N -elementowa jednowymiarowa tablica

max ← T AB

1

powtarzaj od i = 2 do i = N :

je±li max < T AB

i

max ← T AB

i

zako«cz iteracj¦

drukuj: max

Do przemy±lenia na nast¦pne zaj¦cia

Sortowanie tablic binarnych (Zadanie o adze polskiej)

W N urnach znajduj¡ sie dwa rodzaje »etonów: czerwone (0) i biaªe (1), po

jednym w ka»dej urnie. Maj¡c do dyspozycji operacje: test koloru »etonu w

urnie, oraz zamiana »etonów pomi¦dzy dwiema urnami, uªó» wszystkie »etony

czerwone przed biaªymi.

Skonstruuj algorytm realizuj¡cy zadanie o adze polskiej.

2