Budowa i analiza agorytmów - ¢wiczenia nr 1

20 pa¹dziernika 2011

Zadanie 1

Zapisz algorytm konwersji liczb naturalnych (dla uªatwienia nie wi¦kszych ni» 15) z systemu dzie-

si¦tnego do binarnego (czyli dwójkowego). Narysuj schemat blokowy.

Wskazówka:
Zapis binarny liczby 13 mo»e by¢ przedstwiony w nast¦puj¡cy sposób:

13

10

=

8 + 4 + 1

=

1 · 2

3

+ 1 · 2

2

+ 0 · 2

1

+ 1 · 2

0

=

1101

2

.

Zauwa», »e:
13 : 2 = 6

reszty 1

6 : 2 = 3

reszty 0

3 : 2 = 1

reszty 1

1 : 2 = 0

reszty 1

Algorithm 1 A2.1.1: Konwersja binarna
DANE: a - konwertowana liczba naturalna (dodatnia) zapisana w systemie dziesi¦tnym

dopóki a > 0 powtarzaj:

reszta← Mod(a, 2)

drukuj: reszta
a ← [a/2]

zako«cz iteracj¦

Schemat Blokowy

1

Powy»szy algorytm wykorzystuje iteracj¦ nieograniczon¡ (inaczej - warunkow¡) typu: Dopóki

warunek Q jest speªniony powtarzaj, co nast¦puje. Operator Mod liczy reszt¦ caªkowit¡ z dzielenia

liczby a przez b, np. Mod(13, 2) = 1. Z kolei operator[ ] (caªo±¢) zwraca cz¦±¢ caªkowit¡ swojego

argumentu, np.: [6.5] = 6.

Zwró¢ uwag¦, »e algorytm nie radzi sobie w sytuacji, gdy a = 0. Kolejn¡ wad¡ jest to, »e

kolejne cyfry rozwini¦cia pojawiaj¡ si¦ w odwrotnej kolejno±ci, ni» w zapisie binarnym.

2