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
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
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
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
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