20 pa¹dziernika 2011
Algorithm 1 Konwersja DEC2BIN - wersja naturalna
DANE: a - konwertowana liczba zapisana w systemie dziesi¦tnym potęga ← 1
powtarzaj:
potęga ← potęga · 2
a» do: potęga > a
powtarzaj:
potęga ← potęga/2
drukuj: [a/potęga]
a ← M od(a, potęga)
a» do: potęga = 1
Algorithm 2 Konwersja DEC2BIN - wersja na tablicach DANE: a - konwertowana liczba zapisana w systemie dziesi¦tnym i ← 1
powtarzaj:
T ABi ← M od(a, 2)
i ← i + 1
a ← [a/2]
a» do: a = 0
powtarzaj:
i ← i − 1
drukuj: T ABi
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 ABi 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 AB1
powtarzaj od i = 2 do i = N :
je±li max < T ABi
max ← T ABi
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