Matematyka dyskretna

Arytmetyka

Andrzej Szepietowski

1

System dziesi¸

etny

Najpowszechniej używanym sposobem przedstawiania liczb naturalnych jest system dziesi¸etny, gdzie na przyk lad zapis:

178

przedstawia liczb¸e sk ladaj¸ac¸a si¸e z jednej setki, siedmiu dziesi¸atek i ośmiu jedności. Możemy to zapisać w postaci:

178 = 1 · 100 + 7 · 10 + 8 · 1,

albo inaczej:

178 = 1 · 102 + 7 · 101 + 8 · 100.

Tak wi¸ec w systemie dziesi¸etnym kolejne cyfry oznaczaj¸a wspó lczynniki przy kolejnych pot¸egach liczby dziesi¸eć, zaczynaj¸ac od najwi¸ekszej, a kończ¸ac na najmniejszej pot¸edze. Mówimy, że liczba dziesi¸eć jest podstaw¸a lub baz¸a systemu dziesi¸etnego. W systemie dziesi¸etnym używamy dziesi¸eciu cyfr:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

a zapis:

drdr 1 . . . d1d0

−

oznacza liczb¸e:

d

1

r · 10r + dr

1 · 10r−

+ . . . + d1 · 101 + d0 · 100,

(1)

−

któr¸a możemy też zapisać w postaci:

r

X di · 10i,

(2)

i=0

gdzie di s¸a cyframi należ¸acymi do zbioru {0, . . . , 9}.

Liczby można też zapisywać w systemach z inn¸a baz¸a. Jeżeli za baz¸e systemu wybierzemy liczb¸e b, to potrzebujemy b cyfr, a zapis:

drdr 1 . . . d1d0

−

oznacza w systemie z baz¸a b liczb¸e:

d

1

r · br + dr

1 · br−

+ . . . + d1 · b1 + d0 · b0,

(3)

−

któr¸a możemy też zapisać w postaci:

r

X di · bi.

(4)

i=0

1

2

System dwójkowy

W informatyce bardzo ważnym systemem jest system dwójkowy (binarny), gdzie podstaw¸a jest liczba 2 i gdzie mamy tylko dwie cyfry, 0 i 1 (cyfry w systemie dwójkowym nazywa si¸e bitami).

Zapis:

drdr 1 . . . d1d0

−

oznacza liczb¸e:

d

1

r · 2r + dr

1 · 2r−

+ . . . + d1 · 21 + d0 · 20

−

lub:

r

X di · 2i.

i=0

Na przyk lad, zapis 110 oznacza w systemie dwójkowym liczb¸e:

1 · 22 + 1 · 21 + 0 · 20,

czemu w systemie dziesi¸etnym odpowiada:

4 + 2 = 6.

Podobnie zapis:

1101101

oznacza w systemie dziesi¸etnym liczb¸e:

64 + 32 + 8 + 4 + 1 = 109.

W poniższej tabeli przedstawiono kilkanaście kolejnych liczb w postaci dwójkowej i dziesi¸etnej, a w nast¸epnej — kilkanaście pierwszych pot¸eg liczby 2 w postaci dwójkowej i dziesi¸etnej.

dwójkowy

dziesi¸etny

0

0

1

1

10

2

11

3

100

4

101

5

110

6

111

7

1000

8

1001

9

1010

10

1011

11

1100

12

1101

13

1110

14

1111

15

10000

16

2

pot¸ega

dwójkowy

dziesi¸etny

0

1

1

1

10

2

2

100

4

3

1000

8

4

10000

16

5

100000

32

6

1000000

64

7

10000000

128

8

100000000

256

9

1000000000

512

10

10000000000

1024

3

Zwi¸

ekszanie liczby o jeden

Algorytm zwi¸

ekszania liczby o jeden. Aby zwi¸ekszyć o jeden liczb¸e zapisan¸a w systemie

dwójkowym:

• wskazujemy na ostatni bit,

• powtarzamy, co nast¸epuje:

jeżeli wskazany bit jest zerem, to zamieniamy go na jedynk¸e i kończymy algorytm,

jeżeli jest on równy jeden, to zamieniamy go na zero i wskazujemy nast¸epny bit w lewo; jeżeli nie ma nast¸epnego bitu w lewo, to stawiamy jedynk¸e na pocz¸atku liczby i kończymy algorytm.

Mówi¸ac inaczej, szukamy pierwszego zera od prawej strony, zamieniamy go na jedynk¸e, a wszystkie jedynki stoj¸ace za nim zamieniamy na zera. Na przyk lad, liczba o jeden wi¸eksza od liczby 100100111

to

100101000.

Jeżeli liczba nie zawiera zer, tylko same jedynki, to zamieniamy te jedynki na zera i stawiamy jedynk¸e na pocz¸atku. Na przyk lad, po liczbie

11111

jest liczba

100000.

Zauważmy, że podobnie dzia la algorytm zwi¸ekszania o jeden liczb w systemie dziesi¸etnym (lub dowolnym innym systemie). Szukamy pierwszej od prawej cyfry różnej od dziewi¸atki (najwi¸ekszej cyfry w systemie), zwi¸ekszamy t¸e cyfr¸e o jeden, a wszystkie stoj¸ace za ni¸a dziewi¸atki zamieniamy na zera.

3

4

Porównywanie liczb

Algorytm porównywania liczb. Aby stwierdzić, która z dwóch liczb jest wi¸eksza, post¸epujemy w nast¸epuj¸acy sposób:

• jeżeli zapisy liczb nie s¸a tej samej d lugości, to wi¸eksz¸a jest liczba z d luższym zapisem (zak ladamy tu, że zapis liczby różnej od zera nie ma zer na pocz¸atku),

• jeżeli zapisy liczb s¸a równej d lugości, to porównujemy bit po bicie od lewej strony do prawej:

jeżeli bity s¸a takie same, to przechodzimy do nast¸epnego bitu w prawo,

jeżeli bity s¸a różne, to kończymy i stwierdzamy, że wi¸eksza jest ta liczba, która ma wi¸ekszy bit na tej pozycji,

• jeżeli wszystkie bity s¸a takie same, to porównywane liczby s¸a równe.

Na przyk lad:

1011010 > 1010101.

Powyższe liczby s¸a tej samej d lugości i maj¸a takie same trzy pierwsze bity, a różni¸a si¸e dopiero czwartym bitem — czwarty bit pierwszej liczby (1) jest wi¸ekszy od czwartego bitu drugiej liczby (0).

5

Operacje arytmetyczne w systemie dwójkowym

Operacje dodawania, mnożenia, odejmowania i dzielenia w systemie dwójkowym można wykonywać podobnie do tak zwanych szkolnych pisemnych dzia lań arytmetycznych w systemie dziesi¸etnym.

Dzia lania w systemie dwójkowym s¸a prostsze, ponieważ mamy tu tylko dwie cyfry, 0 i 1, i prostsze s¸a operacje na pojedynczych cyfrach.

Zacznijmy od tabliczki dodawania i mnożenia. Wygl¸adaj¸a one tak:

+

0

1

*

0

1

0

0

1

0

0

0

1

1

10

1

0

1

Przypuśćmy, że chcemy dodać dwie liczby w postaci dwójkowej. Zak ladamy tu, że obie liczby s¸a tej samej d lugości. Jeżeli nie s¸a, to krótsz¸a z nich uzupe lniamy na pocz¸atku zerami.

Algorytm dodawania. Aby dodać dwie liczby w postaci binarnej:

drdr 1 . . . d0,

−

erer 1 . . . e0,

−

dla kolejnych pozycji i od 0 do r obliczamy bit sumy si oraz ci — tak zwany bit przeniesienia do nast¸epnej pozycji:

4

• najpierw obliczamy s0 oraz c0:

s0 = d0 + e0

(mod 2)

(czyli s0 jest reszt¸a z dzielenia d0 + e0 przez 2),

c0 = d0e0,

• nast¸epnie po kolei, dla każdego i od 1 do r, obliczamy i-ty bit sumy wed lug wzoru: si = di + ei + ci 1

(mod 2),

−

a bit ci jest jedynk¸a, jeżeli co najmniej dwa spośród bitów di, ei oraz ci 1 s¸a jedynkami,

−

• na końcu obliczamy najbardziej znacz¸acy bit sumy:

sr+1 = cr.

Wynikiem dodawania jest liczba

sr+1sr . . . s0

(może si¸e zdarzyć, że sr+1 = 0).

Na przyk lad, dodawanie liczb 10101 i 111 wygl¸ada nast¸epuj¸aco:

1

0

1

0

1

+

1

1

1

1

1

1

0

0

Aby odj¸ać od siebie dwie liczby w systemie dwójkowym, odejmujemy bit po bicie od prawej do lewej, a w przypadku gdy trzeba odj¸ać bit wi¸ekszy od mniejszego, ,,pożyczamy” dwójk¸e z nast¸epnej (w lewo) pozycji (szczegó ly algorytmu pozostawiono jako ćwiczenie). Na przyk lad, odejmowanie liczb 10101 i 111 wygl¸ada nast¸epuj¸aco:

1

0

1

0

1

−

1

1

1

1

1

1

0

Aby pomnożyć dwie liczby, mnożymy pierwsz¸a liczb¸e przez poszczególne cyfry drugiej liczby, a wyniki podpisujemy pod spodem odpowiednio przesuni¸ete wzgl¸edem siebie. Każdy kolejny wynik jest przesuni¸ety o jedn¸a kolumn¸e w lewo. Nast¸epnie sumujemy te iloczyny. Oto przyk lad mnożenia liczb 10101 i 101:

1

0

1

0

1

1

0

1

1

0

1

0

1

0

0

0

0

0

1

0

1

0

1

1

1

0

1

0

0

1

5

Zauważmy, że pomnożenie liczby w postaci dwójkowej przez 2 oznacza dopisanie jednego zera na końcu liczby. Podobnie pomnożenie przez i-t¸a pot¸eg¸e liczby 2 oznacza dopisanie na końcu liczby i zer. Na przyk lad:

1101101

pomnożone przez

1000

daje wynik

1101101000.

Również dzielenie wykonuje si¸e podobnie jak w systemie dziesi¸etnym. Na przyk lad: 1

0

1

0

1

1

1

0

1

0

0

1

:

1

0

1

1

0

1

1

1

0

1

0

1

1

0

1

1

0

1

0

0

0

Jeżeli liczba jest podzielna przez 2, to ma w postaci binarnej zero na końcu, a jeżeli dzieli si¸e przez i-t¸a pot¸eg¸e dwójki, to ma na końcu i zer. Podzielenie liczby przez 2 oznacza skreślenie w jej postaci binarnej jednego zera z końca. Na przyk lad:

1010011000

podzielone przez 2 daje:

101001100.

6

Zamiana systemu

Zastanówmy si¸e teraz, jak przechodzić od jednego sposobu przedstawiania liczby do drugiego.

Ponieważ b¸edziemy używać różnych systemów zapisu liczb, wi¸ec zapis w systemie z baz¸a b oznaczymy przez:

(drdr 1 . . . d1d0)b.

−

B¸edziemy rezygnować z tego zapisu, jeżeli nie b¸edzie w¸atpliwości, jakiego systemu używamy. Przedysku-tujmy to na przyk ladach. Aby przedstawić liczb¸e

(110101)2

w postaci dziesi¸etnej, korzystamy ze wzoru 3:

(110101)2 = 1 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20,

6

i wykonujemy wszystkie rachunki w systemie dziesi¸etnym:

(110101)2 = 1 · 32 + 1 · 16 + 0 · 8 + 1 · 4 + 0 · 2 + 1 · 1 = 32 + 16 + 4 + 1 = (53)10.

Podobnie możemy post¸epować przy zamianie w odwrotn¸a stron¸e, z systemu dziesi¸etnego na dwójkowy.

Najpierw korzystamy ze wzoru 1:

(53)10 = 5 · 101 + 3 · 100,

nast¸epnie przedstawiamy cyfry i podstaw¸e systemu 10 w postaci dwójkowej i wykonujemy wszystkie dzia lania w systemie dwójkowym:

(53)10 = (101)2 · (1010)2 + (11)2 = (110010)2 + (11)2 = (110101)2.

Ten sposób zamiany liczb z postaci dziesi¸etnej na dwójkow¸a jest analogiczny do sposobu, w jaki wyżej zamienialiśmy liczby z postaci dwójkowej na dziesi¸etn¸a. By lby to naturalny sposób dla kogoś, kto swobodnie liczy w systemie dwójkowym. Sposób ten ma t¸e wad¸e, że wolno dzia la. Zobaczymy na przyk ladach dwa szybsze algorytmy zamiany postaci liczby z dziesi¸etnej na dwójkow¸a.

Weźmy liczb¸e 178. Pierwszy sposób polega na tym, że wyszukujemy najwi¸eksz¸a pot¸eg¸e liczby 2, która jeszcze jest mniejsza od naszej liczby (w przyk ladzie 128 = 27), nast¸epnie odejmujemy t¸e pot¸eg¸e od naszej liczby i z różnic¸a post¸epujemy tak samo. Na końcu mamy liczb¸e w postaci sumy pot¸eg dwójki. W naszym przyk ladzie wygl¸ada to tak:

178 = 128 + 50 = 128 + 32 + 18 = 128 + 32 + 16 + 2.

Teraz już latwo zapisać nasz¸a liczb¸e w postaci dwójkowej:

(178)10 = (10110010)2.

Drugi sposób polega na kolejnym dzieleniu liczby w sposób ca lkowity przez 2 i zapami¸etywaniu reszt z dzielenia. Reszty te zapisane w odwrotnej kolejności tworz¸a zapis binarny liczby. Na przyk lad, weźmy znowu liczb¸e 178. W poniższej tabeli przedstawiono kolejne ilorazy i reszty.

liczba

iloraz

reszta

178

89

0

89

44

1

44

22

0

22

11

0

11

5

1

5

2

1

2

1

0

1

0

1

Reszty zapisane w odwrotnej kolejności:

10110010,

7

tworz¸a binarny zapis liczby (178)10.

Poprawność dzia lania tego algorytmu wynika z faktu, że jeżeli podzielimy liczb¸e r

X

x =

di · 2i

i=0

przez 2, to reszta z dzielenia wyniesie d0, a iloraz ca lkowitoliczbowy wyniesie: r

X d

1

i · 2i− ,

i=1

nast¸epne dzielenie przez 2 da reszt¸e d1 oraz iloraz:

r

X d

2

i · 2i− ,

i=2

i tak dalej.

Ostatni sposób można latwo uogólnić na algorytm zamiany liczb z systemu dziesi¸etnego na system z inn¸a baz¸a b. Należy tylko dzielić przez b. Jeżeli chcemy, na przyk lad, przedstawić liczb¸e 60 w systemie trójkowym, to dzielimy j¸a kolejno przez 3 i spisujemy reszty z dzielenia: liczba

iloraz

reszta

60

20

0

20

6

2

6

2

0

2

0

2

W wyniku otrzymamy:

(60)10 = (2020)3.

7

U lamki

Przypomnijmy najpierw krótko, jak przedstawia si¸e u lamek w systemie dziesi¸etnym. Na przyk lad, 0.234

oznacza:

2 · 10 1

2

3

−

+ 3 · 10− + 4 · 10− .

Użyliśmy kropki do oddzielania cz¸eści ca lkowitej od u lamkowej. Jest to cz¸esto używany w informatyce sposób, stosowany mi¸edzy innymi w j¸ezyku Pascal.

Ogólniej, zapis:

0.d1d2 . . . dr

oznacza liczb¸e:

d

1

2

r

1 · 10−

+ d2 · 10− + . . . + dr · 10− ,

8

któr¸a możemy też zapisać w postaci:

r

X d

i

i · 10− .

i=1

Podobnie możemy zapisywać u lamki w systemie dwójkowym. Jedyna różnica polega na tym, że w systemie binarnym podstaw¸a pot¸eg jest dwójka i że używamy tylko dwóch cyfr, 0 i 1. Tak wi¸ec w systemie dwójkowym zapis:

0.d1d2 . . . dr

oznacza liczb¸e:

d

1

2

r

1 · 2−

+ d2 · 2− + . . . + dr · 2− ,

lub inaczej:

r

X d

i

i · 2− .

i=1

Na przyk lad:

(0.1)2 = (0.5)10,

(0.11)2 = (0.75)10,

(0.101)2 = (0.625)10.

W poniższej tabeli przedstawiono kilka pierwszych ujemnych pot¸eg liczby 2 w systemie dwójkowym i dziesi¸etnym.

2 1

−

(0.1)2

(0.5)10

2 2

−

(0.01)2

(0.25)10

2 3

−

(0.001)2

(0.125)10

2 4

−

(0.0001)2

(0.0625)10

2 5

−

(0.00001)2

(0.03125)10

2 6

−

(0.000001)2

(0.015625)10

8

System szesnastkowy

W informatyce używa si¸e też systemu szesnastkowego, gdzie podstaw¸a jest liczba 16. Do systemu szesnastkowego potrzebujemy szesnastu cyfr. Zwykle używa si¸e nast¸epuj¸acych ,,cyfr”: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

W poniższej tabeli zestawiono cyfry systemu szesnastkowego z odpowiadaj¸acymi im liczbami w systemie dwójkowym i dziesi¸etnym.

9

szesnastkowy

dwójkowy

dziesi¸etny

0

0000

0

1

0001

1

2

0010

2

3

0011

3

4

0100

4

5

0101

5

6

0110

6

7

0111

7

8

1000

8

9

1001

9

A

1010

10

B

1011

11

C

1100

12

D

1101

13

E

1110

14

F

1111

15

Liczby w systemie szesnastkowym poprzedza si¸e zwykle (na przyk lad w j¸ezyku Pascal) znakiem dolara $. I tak zapis $A1 oznacza liczb¸e w systemie szesnastkowym, która w systemie dziesi¸etnym ma poniższ¸a postać:

$A1 = 10 · 16 + 1 = (161)10.

Dzi¸eki temu, że 16 jest pot¸eg¸a dwójki, prosta jest zamiana postaci liczby z systemu dwójkowego na szesnastkowy, i na odwrót. Przy zamianie z systemu szesnastkowego na dwójkowy wystarczy zamieniać kolejne cyfry przedstawienia na grupy odpowiednich czterech bitów wed lug powyższej tabeli. Na przyk lad liczba, która w systemie szesnastkowym wygl¸ada tak:

$A91,

w systemie dwójkowym ma postać:

1010|1001|0001.

Przy zamianie z postaci dwójkowej na postać szesnastkow¸a post¸epujemy odwrotnie. Zast¸epujemy grupy po cztery bity pojedynczymi cyframi. Na przyk lad:

(1110|0011|1011|0000)2 = $E3B0.

Jeżeli liczba cyfr w postaci dwójkowej nie dzieli si¸e przez 4, to uzupe lniamy j¸a zerami na pocz¸atku.

Na przyk lad:

(110|1111|0110|0010)2 = (0110|1111|0110|0010)2 = $6F 62.

W ten sposób możemy używać zapisu szesnastkowego do zwi¸ez lego przedstawiania d lugich ci¸agów bitów.

9

Reprezentacja liczb w komputerze

W j¸ezyku Pascal każda zmienna ma swój typ, który jest deklarowany na pocz¸atku programu.

Sposób przechowywania wartości zmiennej zależy od jej typu.

10

10

Integer

Zmienne typu integer przechowywane s¸a w dwóch bajtach. Jeden bajt (ang. byte) zawiera osiem bitów, tak wi¸ec wartość zmiennej typu integer przechowywana jest w szesnastu bitach. Pierwszy bit oznacza znak. Jeżeli jest on zerem, to liczba jest dodatnia, jeżeli jedynk¸a, to ujemna.

Jeżeli liczba jest dodatnia, to pozosta le pi¸etnaście bitów stanowi binarny zapis tej liczby. Na przyk lad liczba 15 jest przechowywana jako:

0000|0000|0000|1111.

Najwi¸eksz¸a liczb¸e dodatni¸a, jak¸a można przechować w zmiennej typu integer, jest: 0111|1111|1111|1111,

czyli zero i pi¸etnaście jedynek. Jest to:

215 − 1 = (32767)10.

Liczby ujemne s¸a przechowywane w tak zwanym systemie uzupe lnieniowym. Liczba ujemna o wartości bezwzgl¸ednej x jest przedstawiana jako liczba:

216 − x

w postaci binarnej. Na przyk lad liczba −1 jest przedstawiona jako:

1111|1111|1111|1111,

czyli szesnaście jedynek. A liczba −3 jako:

1111|1111|1111|1101.

Najmniejsza liczba ujemna, któr¸a można zmieścić do zmiennej typu integer, to:

1000|0000|0000|0000,

czyli jedynka i pi¸etnaście zer, która koduje liczb¸e:

−215 = (−32768)10.

W j¸ezyku Pascal nie ma żadnego zabezpieczenia przed przekroczeniem maksymalnego lub mini-malnego zakresu liczb typu integer. Jeżeli, na przyk lad, do liczby 32767, która jest przechowywana jako:

0111|1111|1111|1111,

dodamy jedynk¸e, to otrzymamy:

1000|0000|0000|0000,

która koduje liczb¸e −32768, i komputer nie zakomunikuje tego przekroczenia.

11

11

Real

Liczby typu real s¸a zapisywane w dwóch notacjach:

• sta lopozycyjnej,

• zmiennopozycyjnej.

Liczby w notacji sta lopozycyjnej to, na przyk lad:

0.10,

11.023,

12.0,

czyli notacja dziesi¸etna. Zwróćmy uwag¸e, że kropka oddziela cz¸eść ca lkowit¸a liczby od cz¸eści u lamkowej.

W notacji zmiennopozycyjnej liczba przedstawiona jest w postaci:

mEc,

gdzie m jest mantys¸a, liczb¸a w postaci dziesi¸etnej z przedzia lu 1 ≤ m < 10 lub −10 < m ≤ −1, a c, zwana cech¸a, jest liczb¸a ca lkowit¸a. Zapis mEc oznacza liczb¸e:

m · 10c.

W poniższej tabeli mamy kilka liczb w postaci sta lo- i zmiennopozycyjnej.

4837.92

4.83792E3

0.034

3.4E − 2

−12.0

−1.2E1

Sposób przechowywania wartości zmiennych typu real jest skomplikowany i nie b¸edzie przedstaw-iony szczegó lowo.

12

Inne typy ca lkowite

W j¸ezyku Pascal, oprócz integer, można używać innych typów ca lkowitych; s¸a to:

• shortint, zawiera liczby ca lkowite z przedzia lu od −128 do 127,

• byte, zawiera liczby ca lkowite z przedzia lu od 0 do 255,

• word, zawiera liczby ca lkowite z przedzia lu od 0 do 65535,

• longint, zawiera liczby ca lkowite z przedzia lu od −2147483648 do 2147483647.

Elementy typu byte i shortint przechowywane s¸a w jednym bajcie (osiem bitów) pami¸eci, typu word — w dwóch bajtach, a typu longint — w czterech bajtach pami¸eci. Liczby typu shortint i longint mog¸a być dodatnie lub ujemne i s¸a zapami¸etywane w postaci uzupe lnieniowej z pierwszym bitem oznaczaj¸acym znak (podobnie jak liczby typu integer). Elementy typu byte i word mog¸a być tylko dodatnie i s¸a przechowywane w postaci dwójkowej.

12

13

Wyrażenia arytmetyczne w j¸

ezyku Pascal

W j¸ezyku Pascal wyrażeniami arytmetycznymi s¸a sta le liczbowe, na przyk lad:

234,

−123,

0.123,

−23.45,

3.21E − 5,

oraz zmienne typów liczbowych (np. integer lub real). Wyrażenia można także budować za pomoc¸a operatorów arytmetycznych i nawiasów. Jeżeli U oraz W s¸a dwoma wyrażeniami arytmetycznymi, to wyrażeniami arytmetycznymi s¸a także:

U+W, U-W, U*W, U/W, (U), U div V, U mod V.

Gwiazdka ∗ reprezentuje tutaj znak mnożenia, a operacje div oraz mod to iloraz i reszta z dzielenia ca lkowitoliczbowego (s¸a one opisane dok ladnie w rozdziale o teorii liczb).

Na przyk lad, wyrażeniami arytmetycznymi s¸a:

-(2-3)/2+7*4, (2-3)/(3*2), 7 div 2, 7 mod 2.

Jeżeli x oraz y s¸a zmiennymi liczbowymi, to wyrażeniami arytmetycznymi s¸a także: 2*x, x*x-2/y.

Dla danego wyrażenia możemy obliczyć jego wartość. Robi si¸e to wed lug zwyk lych regu l znanych ze szko ly. Najpierw oblicza si¸e wyrażenia w nawiasach, potem mnożenie i dzielenie (od lewej do prawej), a na końcu dodawanie i odejmowanie (od lewej do prawej).

14

Poszukiwania binarne (binary search)

Znana jest gra w dwadzieścia pytań. W tej grze za pomoc¸a dwudziestu pytań, na które odpowiedzi¸a może być ,,tak” lub ,,nie”, należy odgadn¸ać pomyślan¸a przez przeciwnika rzecz. Zobaczymy, jak można wykorzystać binarny system zapisu liczb do opracowania strategii wygrywaj¸acej w tej grze.

Najpierw uprośćmy nieco t¸e gr¸e. Za lóżmy, że możemy zadać tylko cztery pytania i że odgadu-jemy liczb¸e naturaln¸a x ze zbioru:

A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.

Wtedy należy zadać nast¸epuj¸ace cztery pytania:

• Czy liczba x należy do zbioru A1 = {8, 9, 10, 11, 12, 13, 14, 15}?

• Czy x należy do zbioru A2 = {4, 5, 6, 7, 12, 13, 14, 15}?

• Czy x należy do zbioru A3 = {2, 3, 6, 7, 10, 11, 14, 15}?

• Czy x należy do zbioru A4 = {1, 3, 5, 7, 9, 11, 13, 15}?

Dlaczego te cztery pytania wystarcz¸a? Sprawa stanie si¸e jasna, jeżeli przedstawimy liczby w postaci binarnej. Każd¸a za pomoc¸a czterech bitów (z zerami na pocz¸atku). Wtedy nasz zbiór wygl¸ada tak: A = { 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}.

A pytania wygl¸adaj¸a teraz tak:

13

• Czy x należy do zbioru A1 = {1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}?

• Czy x należy do zbioru A2 = {0100, 0101, 0110, 0111, 1100, 1101, 1110, 1111}?

• Czy x należy do zbioru A3 = {0010, 0011, 0110, 0111, 1010, 1011, 1110, 1111}?

• Czy x należy do zbioru A4 = {0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111}?

Zauważmy, że zbiór A1 zawiera wszystkie liczby z pierwszym bitem równym jedynce, w A2 s¸a wszystkie liczby z drugim bitem równym jedynce, i tak dalej. Tak wi¸ec nasze pytania s¸a w rzeczy-wistości pytaniami o kolejne bity odgadywanej liczby. Na przyk lad w pierwszym pytaniu pytamy, czy pierwszy bit odgadywanej liczby jest jedynk¸a.

Ale można do tych pytań podejść inaczej. Najpierw dzielimy zbiór na po lowy: na liczby mniejsze od ośmiu i na liczby wi¸eksze lub równe ośmiu, i pytamy, do której po lowy należy odgadywana liczba (dok ladniej pytamy, czy liczba należy do górnej po lowy). Po uzyskaniu odpowiedzi mamy dwa razy w¸eższy przedzia l poszukiwań. Przypuśćmy, że odgadywan¸a liczb¸a jest 11. W drugim etapie dzielimy przedzia l

{8, 9, 10, 11, 12, 13, 14, 15}

na po lowy, górn¸a:

{12, 13, 14, 15}

i doln¸a:

{8, 9, 10, 11}

i pytamy, do której po lowy należy szukana liczba. Po drugiej odpowiedzi przedzia l poszukiwań jest już cztery razy krótszy. Po dwóch kolejnych pytaniach przedzia l zaw¸eża si¸e do jednej liczby. Drugi sposób jest ca lkowicie równoważny pierwszemu, tutaj też pytamy o kolejne bity i otrzymujemy takie same odpowiedzi.

Potrzeba cztery razy kolejno dzielić zbiór na po lowy, aby z pocz¸atkowej d lugości 16 przejść na końcu do d lugości 1. A ile trzeba podzia lów, jeżeli na pocz¸atku mamy n = 2k elementów?

Po pierwszym podziale nasz zbiór b¸edzie mia l d lugość 2k 1

2

i

− , po drugim 2k− , a po i-tym 2k− .

Jak widać, potrzeba k = log2 n kolejnych podzia lów, aby dojść do 1. Tak wi¸ec jeżeli mamy do dyspozycji 20 pytań, to możemy odnaleźć jedn¸a spośród 220 liczb ca lkowitych z przedzia lu od 0 do 220 − 1 = 1 048 575.

15

Waga

Zobaczymy teraz, jak można wykorzystać trójkowy system zapisu liczb. W systemie trójkowym podstaw¸a jest liczba 3, mamy trzy cyfry {0, 1, 2} i zapis

drdr 1 . . . d1d0

−

oznacza liczb¸e:

d

1

r · 3r + dr

1 · 3r−

+ . . . + d1 · 31 + d0 · 30,

−

14

lub inaczej:

r

X di · 3i.

i=0

Wyobraźmy sobie wag¸e szalkow¸a. Na jednej szalce, lewej, k ladziemy jakiś przedmiot do zważenia, a nast¸epnie na obu szalkach k ladziemy odważniki. Jeżeli waga jest w równowadze, to ważony przedmiot ma wag¸e równ¸a sumie (nomina lów) odważników po lożonych na prawej szalce minus suma odważników po lożonych na lewej szalce, obok ważonego przedmiotu. Na przyk lad, jeżeli na prawej szalce leż¸a odważniki o ci¸eżarach 2 i 20 gramów, a na lewej odważniki o wadze 4 i 5 gramów, to przedmiot waży 13 = (20 + 2) − (5 + 4) gramów.

Interesuj¸ace nas pytanie brzmi: jakie powinny być nomina ly poszczególnych odważników, aby można by lo zważyć każdy ci¸eżar o wadze od 1 do N , przy jak najmniejszej liczbie odważników.

Zak ladamy, że ważymy tylko przedmioty o ca lkowitych wagach.

Rozpatrzmy najpierw przyk lad czterech odważników o wagach:

c1, c2, c3, c4.

Ile różnych ci¸eżarów można odważyć za pomoc¸a czterech odważników? Ponieważ każdy odważnik może si¸e znajdować na prawej lub lewej szalce, lub na stole, to mamy 34 = 81 różnych po lożeń odważników. Wśród tych po lożeń jest takie, gdzie wszystkie cztery odważniki leż¸a na stole (wt-edy ważymy zerowy ci¸eżar). Ponadto jeżeli odważniki leż¸a na szalkach i odważaj¸a ci¸eżar W , to zamieniwszy po lożenia odważników na szalkach (odważniki z lewej przek ladamy na praw¸a szalk¸e, i na odwrót), b¸edziemy odważać ci¸eżar −W . Tak wi¸ec spośród 81 u lożeń odważników na szalkach tylko

81 − 1 = 40

2

odważa jakiś dodatni ci¸eżar. Oczywiście może si¸e zdarzyć, że dwa różne po lożenia odważników odważaj¸a ten sam ci¸eżar.

Interesuje nas, czy istniej¸a takie cztery odważniki, za pomoc¸a których można odważyć każdy ci¸eżar od 1 do 40. Odpowiedź na to pytanie jest pozytywna. Istniej¸a takie cztery odważniki, s¸a to: 1,

3,

9,

27.

Zauważmy, że nomina ly odważników to cztery pierwsze pot¸egi liczby 3. Każde u lożenie tych odważników odważa ci¸eżar:

W = d3 · 27 + d2 · 9 + d1 · 3 + d0 · 1,

(5)

lub inaczej:

W = d3 · 33 + d2 · 32 + d1 · 31 + d0 · 30,

gdzie di = 1, jeżeli odważnik o nominale 3i leży na prawej szalce, di = −1, jeżeli leży na lewej, i di = 0, jeżeli leży na stole.

Zobaczymy, że każd¸a liczb¸e od 1 do 40 można przedstawić w postaci 5. Zauważmy, że jeżeli do ci¸eżaru W dodamy:

40 = 27 + 9 + 3 + 1,

15

to otrzymamy:

W + 40 = (d3 + 1) · 33 + (d2 + 1) · 32 + (d1 + 1) · 31 + (d0 + 1) · 30.

Jeżeli teraz oznaczymy:

ei = di + 1,

dla 0 ≤ i ≤ 3, to otrzymamy:

W + 40 = e3 · 33 + e2 · 32 + e1 · 31 + e0 · 30.

(6)

Zauważmy, że każde ei jest teraz ze zbioru {0, 1, 2} i wzór 6 przedstawia rozwini¸ecie liczby W + 40

w systemie trójkowym, a ponieważ W jest z przedzia lu od 1 do 40, to W + 40 jest z przedzia lu od 41 do 80 i można j¸a przedstawić za pomoc¸a czterech cyfr w systemie trójkowym.

Powyższy wywód sugeruje algorytm odszukiwania po lożenia odważników dla danego ci¸eżaru W .

Algorytm wa żenia. Chc¸ac zważyć ci¸eżar W z przedzia lu od 1 do 40:

• przedstawiamy liczb¸e W + 40 w systemie trójkowym: W + 40 = (e3e2e1e0)3,

• od każdej cyfry odejmujemy jedynk¸e: di = ei − 1,

• postać (d3d2d1d0) określa po lożenie poszczególnych odważników wed lug zasady:

jeżeli di = 1, to odważnik o nominale 3i należy po lożyć na prawej szalce,

jeżeli di = −1, to na lewej,

jeżeli di = 0, to na stole.

Spróbujmy zważyć ci¸eżar W = 20 gramów. W rozdziale o zamianie systemu obliczyliśmy, że liczba 60 = 20 + 40 w systemie trójkowym ma postać:

(60)10 = (2020)3,

czyli:

60 = 2 · 27 + 0 · 9 + 2 · 3 + 0 · 1.

Odejmujemy teraz jedynk¸e od każdej cyfry i otrzymujemy:

(1¯11¯1).

Tutaj ¯1 oznacza −1. Mamy wi¸ec:

20 = 27 − 9 + 3 − 1.

Metod¸e opisan¸a wyżej można uogólnić na wi¸eksz¸a liczb¸e odważników. Jeżeli mamy N odważników o nomina lach:

1, 3, . . . , 3N 1

− ,

to możemy odważyć każdy ci¸eżar W z przedzia lu od 1 do (3N − 1)/2. Należy rozwin¸ać liczb¸e W + (3N − 1)/2 w systemie trójkowym, a nast¸epnie od każdej cyfry rozwini¸ecia odj¸ać jedynk¸e.

16

16

Zadania

1. Zwi¸eksz o jeden nast¸epuj¸ace liczby zapisane w postaci dwójkowej: a) 11010011; b) 111111.

2. Porównaj nast¸epuj¸ace pary liczb: a) 110011, 110100;

b) 11010, 1110.

3. Dodaj (odejmij, pomnóż) w postaci dwójkowej nast¸epuj¸ace pary liczb: a) 110011, 110100; b) 11010, 1110.

4. Napisz dok ladny algorytm odejmowania dwóch liczb w postaci dwójkowej.

5. Liczby 81, 126 przedstaw w postaci dwójkowej. Jak b¸ed¸a one reprezentowane w komputerze jako sta le typu integer (byte, word)?

6. Nast¸epuj¸ace liczby przedstaw w postaci dwójkowej: 6.75, 5.625, $B1, $FF.

7. Nast¸epuj¸ace liczby przedstaw w postaci trójkowej: 80, 120.

8. Nast¸epuj¸ace liczby w postaci dwójkowej, 10001101, 100101, przedstaw w postaci: a) dziesi¸etnej, b) szesnastkowej.

9. Opisz algorytm zamiany u lamka z postaci dziesi¸etnej na postać dwójkow¸a.

10. Ile maksymalnie pytań z odpowiedziami TAK/NIE trzeba zadać, aby odgadn¸ać liczb¸e z przedzia lu od 0 do 100 000?

11. Jak należy u lożyć na szalkach odważniki o nomina lach 1, 3, 9, 27, aby odważyć ci¸eżar: a) 35, b) 29?

17