Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Arytmetyka
1.1 System dziesiętny
Najpowszechniej używanym sposobem przedstawiania liczb naturalnych jest system dzie-
siętny, gdzie na przykład zapis:
178
przedstawia liczbę składającą się z jednej setki, siedmiu dziesiątek 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ęc w systemie dziesiętnym kolejne cyfry oznaczają współczynniki przy kolejnych
potęgach liczby dziesięć, zaczynając od największej, a kończąc na najmniejszej potędze.
Mówimy, że liczba dziesięć jest podstawą lub bazą systemu dziesiętnego. W systemie
dziesiętnym używamy dziesięciu cyfr:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
a zapis:
drdr-1 . . . d1d0
oznacza liczbÄ™:
dr · 10r + dr-1 · 10r-1 + . . . + d1 · 101 + d0 · 100, (1.1)
którą możemy też zapisać w postaci:
r
di · 10i, (1.2)
i=0
3
4 Rozdział 1. Arytmetyka
gdzie di są cyframi należącymi do zbioru {0, . . . , 9}.
Liczby można też zapisywać w systemach z inną bazą. Jeżeli za bazę systemu wybie-
rzemy liczbÄ™ b, to potrzebujemy b cyfr, a zapis:
drdr-1 . . . d1d0
oznacza w systemie z bazÄ… b liczbÄ™:
dr · br + dr-1 · br-1 + . . . + d1 · b1 + d0 · b0, (1.3)
którą możemy też zapisać w postaci:
r
di · bi. (1.4)
i=0
1.2 System dwójkowy
W informatyce bardzo ważnym systemem jest system dwójkowy (binarny), gdzie pod-
stawą jest liczba 2 i gdzie mamy tylko dwie cyfry, 0 i 1 (cyfry w systemie dwójkowym
nazywa siÄ™ bitami). Zapis:
drdr-1 . . . d1d0
oznacza liczbÄ™:
r
di · 2i = dr · 2r + dr-1 · 2r-1 + . . . + d1 · 21 + d0 · 20.
i=0
PrzykÅ‚ad 1.1 Zapis 110 oznacza w systemie dwójkowym liczbÄ™ 1 · 22 + 1 · 21 + 0 · 20,
czemu w systemie dziesiętnym odpowiada 4 + 2 = 6.
Podobnie zapis 1101101 oznacza w systemie dziesiętnym liczbę 64+32+8+4+1 =
109.
Poniżej w pierwszej tabeli przedstawiono jedenaście pierwszych potęg liczby 2 w postaci
dwójkowej i dziesiętnej, a w drugiej siedemnaście kolejnych liczb w postaci dwójkowej i
dziesiętnej.
potęga dwójkowy dziesiętny
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
1.3. Zwiększanie liczby o jeden 5
dwójkowy dziesiętny
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
1.3 Zwiększanie liczby o jeden
Algorytm zwiększania liczby o jeden. Aby zwiększyć o jeden liczbę zapisaną w syste-
mie dwójkowym:
wskaż na ostatni bit,
powtarzaj, co następuje:
jeżeli wskazany bit jest zerem, to
zamień go na jedynkę i zakończ algorytm;
jeżeli jest on równy jeden, to
zamień go na zero i wskaż następny bit w lewo;
jeżeli nie ma następnego bitu w lewo,
to dostaw jedynkę na początku liczby i zakończ algorytm.
Mówiąc inaczej, szukamy pierwszego zera od prawej strony, zamieniamy go na jedynkę,
a wszystkie jedynki stojÄ…ce za nim zamieniamy na zera.
Przykład 1.2 Liczba o jeden większa od liczby 100100111 to 100101000.
Jeżeli liczba nie zawiera zer, tylko same jedynki, to zamieniamy te jedynki na zera i
stawiamy jedynkÄ™ na poczÄ…tku.
Przykład 1.3 Po liczbie 11111 jest liczba 100000.
Zauważmy, że podobnie działa algorytm zwiększania o jeden liczb w systemie dziesięt-
nym (lub dowolnym innym systemie). Szukamy pierwszej od prawej cyfry różnej od dzie-
wiątki (największej cyfry w systemie), zwiększamy tę cyfrę o jeden, a wszystkie stojące
za niÄ… dziewiÄ…tki zamieniamy na zera.
6 Rozdział 1. Arytmetyka
1.4 Porównywanie liczb
Algorytm porównywania liczb. Aby stwierdzić, która z dwóch liczb w postaci dwójko-
wej jest większa, postępuj w następujący sposób:
jeżeli liczby nie są tej samej długości, to większą jest dłuższym liczba
jeżeli liczby są równej długości, to
porównuj bit po bicie od lewej strony do prawej:
jeżeli bity są takie same, to
przejdz
do następnego bitu w prawo,
jeżeli bity są różne, to
zakończ; większa jest liczba z większym bitem na tej pozycji,
jeżeli wszystkie bity są takie same, to porównywane liczby są równe.
Przykład 1.4 1011010 > 1010101. Liczby te są tej samej długości, mają takie same trzy
pierwsze bity, a różnią się dopiero czwartym bitem  czwarty bit pierwszej liczby jest
większy od czwartego bitu drugiej liczby.
1.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łań arytmetycznych w
systemie dziesiętnym. Działania w systemie dwójkowym są prostsze, ponieważ mamy tu
tylko dwie cyfry, 0 i 1. Zacznijmy od tabliczki dodawania i mnożenia.
+ 0 1 * 0 1
0 0 1 0 0 0
1 1 10 1 0 1
Algorytm dodawania.
Dane wejściowe: dwie liczby w postaci binarnej dr . . . d0, oraz er . . . e0. Zakładamy, że
liczby są tej samej długości. Jeżeli nie są, to krótszą uzupełniamy na początku zerami.
Dane wyjściowe: bity sumy obu liczb sr+1sr . . . s0.
s0 := (d0 + e0) mod 2
c0 := d0 · e0;
dla kolejnych pozycji i od 1 do r oblicz
si := (di + ei + ci-1) mod 2,
ci := 1, jeżeli co najmniej dwa spośród bitów di, ei oraz ci-1 są jedynkami,
sr+1 := cr.
Przykład 1.5 Dodawanie liczb 10101 i 111 wygląda następująco:
1.5. Operacje arytmetyczne w systemie dwójkowym 7
1 0 1 0 1
+ 1 1 1
1 1 1 0 0
Algorytm najpierw oblicza ostatni bit sumy s0, który jest resztą z dzielenia (d0 + e0)
przez 2, oraz przeniesienie z ostatniego bitu c0. Następnie dla każdej pozycji i od 1 do
r oblicza bit sumy si oraz przeniesienie do następnej pozycji. Na końcu obliczany jest
najbardziej znaczÄ…cy bit sumy sr+1 = cr.
Aby odjąć od siebie dwie liczby w systemie dwójkowym, odejmujemy bit po bicie
od prawej do lewej, a w przypadku gdy trzeba odjąć bit większy od mniejszego,  poży-
czamy dwójkę z następnej (w lewo) pozycji (szczegóły algorytmu pozostawiono jako
ćwiczenie).
Przykład 1.6 Odejmowanie liczb 10101 i 111 wygląda następująco:
1 0 1 0 1
- 1 1 1
1 1 1 0
Aby pomnożyć dwie liczby, mnożymy pierwszą liczbę przez poszczególne cyfry dru-
giej liczby, a wyniki podpisujemy pod spodem odpowiednio przesunięte względem siebie.
Każdy kolejny wynik jest przesunięty o jedną kolumnę w lewo. Następnie sumujemy te
iloczyny.
Przykład 1.7 Oto przykład 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
Zauważmy, że pomnożenie liczby w postaci dwójkowej przez dwa oznacza dopisa-
nie jednego zera na końcu liczby. Podobnie pomnożenie liczby przez i-tą potęgę dwójki
oznacza dopisanie na końcu i zer.
Przykład 1.8 1101101 pomnożone przez 1000 daje wynik 1101101000.
Również dzielenie wykonuje się podobnie jak w systemie dziesiętnym. Na przykład:
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
8 Rozdział 1. Arytmetyka
Jeżeli liczba jest podzielna przez dwa, to ma w postaci binarnej zero na końcu, a jeżeli
dzieli się przez i-tą potęgę dwójki, to ma na końcu i zer. Podzielenie liczby przez dwa
oznacza skreślenie w jej postaci binarnej jednego zera z końca.
Przykład 1.9 1010011000 podzielone przez dwa daje 101001100.
1.6 Zamiana systemu
Zastanówmy się teraz, jak przechodzić od jednego sposobu przedstawiania liczby do dru-
giego. Ponieważ będziemy używać różnych systemów zapisu liczb, więc zapis w systemie
z bazÄ… b oznaczymy przez:
(drdr-1 . . . d1d0)b.
Będziemy rezygnować z tego zapisu, jeżeli nie będzie wątpliwości, jakiego systemu uży-
wamy. Przedyskutujmy to na przykładach. Aby przedstawić liczbę
(110101)2
w postaci dziesiętnej, korzystamy ze wzoru (1.3):
(110101)2 = 1 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20,
i wykonujemy wszystkie rachunki w systemie dziesiętnym:
(110101)2 = 1 · 32 + 1 · 16 + 0 · 8 + 1 · 4 + 0 · 2 + 1 · 1 = 32 + 16 + 4 + 1 = (53)10.
Podobnie możemy postępować przy zamianie w odwrotną stronę, z systemu dziesiętnego
na dwójkowy. Najpierw korzystamy ze wzoru (1.1):
(53)10 = 5 · 101 + 3 · 100,
następnie przedstawiamy cyfry i podstawę systemu 10 w postaci dwójkowej i wykonuje-
my wszystkie działania 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ętnej na dwójkową jest analogiczny do sposobu,
w jaki wyżej zamienialiśmy liczby z postaci dwójkowej na dziesiętną. Byłby to naturalny
sposób dla kogoś, kto swobodnie liczy w systemie dwójkowym. Sposób ten ma tę wadę,
że wolno działa. Zobaczymy na przykładach dwa szybsze algorytmy zamiany postaci
liczby z dziesiętnej na dwójkową.
Wez
my liczbę 178. Pierwszy sposób polega na tym, że wyszukujemy największą po-
tęgę liczby 2, która jeszcze jest mniejsza od naszej liczby (w przykładzie 128 = 27),
następnie odejmujemy tę potęgę od naszej liczby i z różnicą postępujemy tak samo. Na
końcu mamy liczbę w postaci sumy potęg dwójki. W naszym przykładzie wygląda to tak:
178 = 128 + 50 = 128 + 32 + 18 = 128 + 32 + 16 + 2.
1.6. Zamiana systemu 9
Teraz już łatwo zapisać naszą liczbę w postaci dwójkowej:
(178)10 = (10110010)2.
Drugi sposób polega na kolejnym dzieleniu liczby w sposób całkowity przez 2 i za-
pamiętywaniu reszt z dzielenia. Reszty te zapisane w odwrotnej kolejności tworzą zapis
binarny liczby. Na przykład, wez
my znowu liczbę 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,
tworzą binarny zapis liczby (178)10. Poprawność działania tego algorytmu wynika z fak-
tu, że jeżeli podzielimy liczbę
r
x = di · 2i
i=0
przez 2, to reszta z dzielenia wyniesie d0, a iloraz całkowitoliczbowy wyniesie:
r
di · 2i-1,
i=1
następne dzielenie przez 2 da resztę d1 oraz iloraz:
r
di · 2i-2,
i=2
i tak dalej.
Ostatni sposób można łatwo uogólnić na algorytm zamiany liczb z systemu dziesięt-
nego na system z inną bazą b. Należy tylko dzielić przez b. Aby przedstawić liczbę 60 w
systemie trójkowym, dzielimy ją 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.
10 Rozdział 1. Arytmetyka
1.7 Długość liczby
Zastanówmy się ile cyfr zawiera zapis dziesiętny liczby naturalnej x. Cztery cyfry w
systemie dziesiętnym posiadają liczby od 1000 = 103 do 9999 = 104 - 1, a k cyfr
posiadają liczby od 10k-1 do 10k - 1. Tak więc liczba x ma k cyfr wtedy i tylko wtedy
gdy k - 1 d" log10 x < k, czyli gdy log10 x = k - 1. Mamy więc
Lemat 1.10 Liczba naturalna x ma w systemie dziesiętnym log10 x + 1 (w przybliżeniu
log10 x) cyfr.
Podobnie w systemie z podstawÄ… b, liczba x ma k cyfr wtedy i tylko wtedy gdy k-1 d"
logb x < k, czyli:
Lemat 1.11 W systemie o podstawie b liczba naturalna x ma logb x +1 (w przybliżeniu
logb x) cyfr.
Korzystając z tego faktu możemy ustalać przybliżoną liczbę cyfr potrzebną do zapisu
liczb.
Wniosek 1.12 Liczba, posiadająca k cyfr w systemie dziesiętnym ma około k log2 10 H"
10
k · bitów w systemie dwójkowym, a liczba majÄ…ca k bitów w postaci dwójkowej ma
3
3
okoÅ‚o k · cyfr w postaci dziesiÄ™tnej.
10
Dowód: Jeżeli liczba x ma w postaci dziesiętnej k cyfr, to k H" log10 x. W postaci dwój-
10
kowej x ma okoÅ‚o log2 x bitów, a log2 x = log10x · log2 10 H" k · log2 10 H" k · ,
3
3
ponieważ log10 2 H" 0.301029996 H" .
10
Podobnie, jeżeli liczba x ma w postaci dwójkowej k bitów, to w postaci dziesiętnej
3
ma okoÅ‚o log10 x = log102 · log2 x H" k · .
10
1.8 Duże liczby
Aby się zorientować jak duże mogą być liczby przedstawione za pomocą systemu dzie-
siętnego lub dwójkowego przypatrzmy się poniższej tabeli:
Liczba sekund w roku H" 3 × 107
Wiek układu słonecznego w latach H" 1010
Wiek układu słonecznego w sekundach H" 1017
Liczba cykli w roku (100 MHz) H" 3 × 1015
Liczba ciÄ…gów 64 bitowych 264 H" 1.8 × 1019
Liczba ciÄ…gów 128 bitowych 2128 H" 3.4 × 1038
Liczba ciÄ…gów 256 bitowych 2256 H" 1.2 × 1077
Liczba atomów na Ziemi H" 1051
Liczba atomów w naszej galaktyce H" 1067
Dane do tabeli zaczerpnięto z książki A. Menezes, P. van Oorschot and S. Vanstone,
Handbook of Applied Cryptography. oraz z książki B. Schneier, Applied Cryptography.
Tabela ta pozwala ocenić niektóre algorytmy.
1.9. UÅ‚amki 11
PrzykÅ‚ad 1.13 Rozważmy prosty algorytm sprawdzajÄ…cy," liczba naturalna x jest pierw-
czy
sza. Algorytm ten dzieli x przez kolejne liczby od 2 do x. Jeżeli x ma 120 bitów, to
potrzeba 260 H" 1018 dzieleń. Jeżeli założymy, że komputer potrafi wykonać 100 milionów
dzieleÅ„ w ciÄ…gu sekundy i 3×1015 w ciÄ…gu roku, to bÄ™dzie liczyÅ‚ okoÅ‚o 300 lat. W rozdziale
o teorii liczb będziemy mówić o szybszych algorytmach sprawdzających pierwszość liczb
mających po kilkaset bitów.
Przykład 1.14 Przypuśćmy, że chcemy zaprojektować tablicę, która dla każdego ciągu
złożongo z ośmiu liter przechowuje jakąś informację (jeden bajt). Zakładając, że mamy
26 liter, takich ciągów jest
10
268 = 108·log 26 = 108·1.41 > 1011,
zatem potrzebowalibyśmy więcej niż 100 gigabajtów pamięci.
1.9 UÅ‚amki
Przypomnijmy najpierw krótko, jak przedstawia się ułamek w systemie dziesiętnym. Na
przykład,
0.234
oznacza:
2 · 10-1 + 3 · 10-2 + 4 · 10-3.
Użyliśmy kropki do oddzielania części całkowitej od ułamkowej. Jest to często używany
w informatyce sposób, stosowany między innymi w języku Pascal. Ogólniej, zapis:
0.d1d2 . . . dr
oznacza liczbÄ™:
d1 · 10-1 + d2 · 10-2 + . . . + dr · 10-r,
którą możemy też zapisać w postaci:
r
di · 10-i.
i=1
Podobnie możemy zapisywać ułamki w systemie dwójkowym. Jedyna różnica polega na
tym, że w systemie binarnym podstawą potęg jest dwójka i że używamy tylko dwóch cyfr,
0 i 1. Tak więc w systemie dwójkowym zapis:
0.d1d2 . . . dr
oznacza liczbÄ™:
d1 · 2-1 + d2 · 2-2 + . . . + dr · 2-r,
lub inaczej:
r
di · 2-i.
i=1
12 Rozdział 1. Arytmetyka
Przykład 1.15
(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ęg liczby 2 w systemie
dwójkowym i dziesiętnym.
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
1.10 System szesnastkowy
W informatyce używa się też systemu szesnastkowego, gdzie podstawą jest liczba 16. Do
systemu szesnastkowego potrzebujemy szesnastu cyfr. Zwykle używa się następujących
 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ącymi im licz-
bami w systemie dwójkowym i dziesiętnym.
szesnastkowy dwójkowy dziesiętny
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
W języku Pascal liczby w systemie szesnastkowym poprzedza się znakiem dolara $, a w
języku C znakami 0x.
1.11. Reprezentacja liczb w komputerze 13
Przykład 1.16 Zapis $A1 oznacza liczbę w systemie szesnastkowym, która w systemie
dziesiÄ™tnym ma postać $A1 = 10 · 16 + 1 = (161)10
Dzięki temu, że 16 jest potęgą dwójki, prosta jest zamiana postaci liczby z systemu dwój-
kowego na szesnastkowy, i na odwrót. Przy zamianie z systemu szesnastkowego na dwój-
kowy wystarczy zamieniać kolejne cyfry przedstawienia na grupy odpowiednich czterech
bitów według powyższej tabeli.
Przykład 1.17 Liczba, która w systemie szesnastkowym wygląda tak $A91 w systemie
dwójkowym ma postać 1010|1001|0001.
Przy zamianie z postaci dwójkowej na postać szesnastkową postępujemy odwrotnie. Za-
stępujemy grupy po cztery bity pojedynczymi cyframi.
Przykład 1.18 (1110|0011|1011|0000)2 = $E3B0.
Jeżeli liczba cyfr w postaci dwójkowej nie dzieli się przez 4, to uzupełniamy ją zerami na
poczÄ…tku.
Przykład 1.19 (110|1111|0110|0010)2 = (0110|1111|0110|0010)2 = $6F 62.
W ten sposób możemy używać zapisu szesnastkowego do zwięzłego przedstawiania dłu-
gich ciągów bitów.
1.11 Reprezentacja liczb w komputerze
W wielu językach każda zmienna ma swój typ, który jest deklarowany na początku pro-
gramu. Sposób przechowywania wartości zmiennej zależy od jej typu.
1.11.1 Integer
Zmienne typu integer przechowywane są zwykle w dwóch bajtach. Jeden bajt (ang. by-
te) zawiera osiem bitów, tak więc 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ą, to ujemna.
Jeżeli liczba jest dodatnia, to pozostałe piętnaście bitów stanowi binarny zapis tej
liczby. Na przykład liczba 15 jest przechowywana jako:
0000|0000|0000|1111.
Największą liczbę dodatnią, jaką można przechować w zmiennej typu integer, jest:
0111|1111|1111|1111,
czyli zero i piętnaście jedynek. Jest to:
215 - 1 = (32767)10.
14 Rozdział 1. Arytmetyka
Liczby ujemne są przechowywane w tak zwanym systemie uzupełnieniowym. Liczba
ujemna x o wartości bezwzględnej |x| jest przedstawiana jako liczba:
216 - |x|
w postaci binarnej. Na przykład 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ą można zmieścić do zmiennej typu integer, to:
1000|0000|0000|0000,
czyli jedynka i piętnaście zer, która koduje liczbę:
-215 = (-32768)10.
Często nie ma żadnego zabezpieczenia przed przekroczeniem maksymalnego lub mini-
malnego zakresu liczb typu integer. Jeżeli, na przykład, do liczby 32767, która jest prze-
chowywana jako:
0111|1111|1111|1111,
dodamy jedynkÄ™, to otrzymamy:
1000|0000|0000|0000,
która koduje liczbę -32768, i komputer nie zakomunikuje tego przekroczenia.
1.11.2 Real
Liczby typu real są zapisywane w dwóch notacjach:
" stałopozycyjnej,
" zmiennopozycyjnej.
Liczby w notacji stałopozycyjnej to, na przykład:
0.10, 11.023, 12.0,
czyli notacja dziesiętna. Zwróćmy uwagę, że kropka oddziela część całkowitą liczby od
części ułamkowej.
W notacji zmiennopozycyjnej liczba przedstawiona jest w postaci:
mEc,
gdzie m jest mantysą, liczbą w postaci dziesiętnej z przedziału 1 d" m < 10 lub -10 <
m d" -1, a c, zwana cechą, jest liczbą całkowitą. Zapis mEc oznacza liczbę:
m · 10c.
W poniższej tabeli mamy kilka liczb w postaci stało- i zmiennopozycyjnej.
1.12. Wyrażenia arytmetyczne w języku Pascal 15
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ędzie
przedstawiony szczegółowo.
1.11.3 Inne typy całkowite
W języku Pascal, oprócz integer, można używać innych typów całkowitych; są to:
" shortint, zawiera liczby całkowite z przedziału od -128 do 127,
" byte, zawiera liczby całkowite z przedziału od 0 do 255,
" word, zawiera liczby całkowite z przedziału od 0 do 65535,
" longint, zawiera liczby całkowite z przedziału od -2147483648 do 2147483647.
Elementy typu byte i shortint przechowywane są w jednym bajcie (osiem bitów) pa-
mięci, typu word  w dwóch bajtach, a typu longint  w czterech bajtach pamięci.
Liczby typu shortint i longint mogą być dodatnie lub ujemne i są zapamiętywane w po-
staci uzupełnieniowej z pierwszym bitem oznaczającym znak (podobnie jak liczby typu
integer). Elementy typu byte i word mogą być tylko dodatnie i są przechowywane w po-
staci dwójkowej.
1.12 Wyrażenia arytmetyczne w języku Pascal
W języku Pascal wyrażeniami arytmetycznymi są stałe liczbowe, na przykład:
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ą operatorów arytmetycznych i nawiasów. JeżeliUorazWsą dwoma wyrażenia-
mi arytmetycznymi, to wyrażeniami arytmetycznymi są także:
U+W, U-W, U*W, U/W, (U), U div V, U mod V.
Gwiazdka " reprezentuje tutaj znak mnożenia, a operacjedivorazmodto iloraz i reszta
z dzielenia całkowitoliczbowego (są one opisane dokładnie w rozdziale o teorii liczb).
Na przykład, wyrażeniami arytmetycznymi są:
-(2-3)/2+7*4, (2-3)/(3*2), 7 div 2, 7 mod 2.
Jeżelixorazysą zmiennymi liczbowymi, to wyrażeniami arytmetycznymi są także:
2*x, x*x-2/y.
Dla danego wyrażenia możemy obliczyć jego wartość. Robi się to według zwykłych reguł
znanych ze szkoły. Najpierw oblicza się wyrażenia w nawiasach, potem mnożenie i dzie-
lenie (od lewej do prawej), a na końcu dodawanie i odejmowanie (od lewej do prawej).
16 Rozdział 1. Arytmetyka
1.13 Poszukiwania binarne (binary search)
Znana jest gra w dwadzieścia pytań. W tej grze za pomocą dwudziestu pytań, na które
odpowiedzią może być  tak lub  nie , należy odgadnąć pomyślaną przez przeciwnika
rzecz. Zobaczymy, jak można wykorzystać binarny system zapisu liczb do opracowania
strategii wygrywajÄ…cej w tej grze.
Uprośćmy nieco tę grę. Załóżmy, że możemy zadać tylko trzy pytania i że odgadujemy
liczbÄ™ naturalnÄ… x ze zbioru:
A = {0, 1, 2, 3, 4, 5, 6, 7}.
Aby odgadnąć liczbę należy postępować w następujący sposób: Najpierw dzielimy zbiór
na połowy: na liczby mniejsze od 4:
{0, 1, 2, 3}
i na liczby większe lub równe 4:
{4, 5, 6, 7}
i pytamy, do której połowy należy odgadywana liczba (dokładniej pytamy, czy liczba
należy do górnej połowy). Po uzyskaniu odpowiedzi mamy dwa razy węższy przedział
poszukiwań i postępujemy z nim podobnie jak w pierwszej turze, dzielimy go na połowy
i pytamy, w której połowie jest szukana liczba. Po drugiej odpowiedzi przedział poszuki-
wań jest już cztery razy krótszy i zawiera dwie liczby. W trzecim pytaniu, znowu dzielimy
przedział na polowy i pytamy, w której połowie znajduje się szukana liczba. Po trzeciej
odpowiedzi przedział poszukiwań jest już osiem razy krótszy od wyjściowego i zawiera
jedną liczbę, która jest tą szukaną.
Prześledz
my ten algorytm w przypadku, gdy szukanÄ… liczbÄ… x jest 5. Po odpowiedzi
na pierwsze pytanie wiemy, że x jest w zbiorze {4, 5, 6, 7}. W drugiej rundzie dzieli-
my ten zbiór na połowy: {4, 5} oraz {6, 7} i pytamy, czy x jest w górnej połowie. Po
negatywnej odpowiedzi wiemy, ze x jest w {4, 5}. W trzeciej rundzie pytamy, czy x = 5.
Strategię gry w trzy pytania można przedstawić za pomocą ukorzenionego drzewa,
patrz rysunek 1.1. Grę rozpoczynamy w korzeniu (wierzchołku z etykietą ). Z tym wierz-
chołkiem związany jest cały zbiór {0, 1, 2, 3, 4, 5, 6, 7}. Z synami korzenia związane są
połówki tego zbioru, z wierzchołkiem 1 związany jest zbiór {4, 5, 6, 7}, a z wierzchoł-
kiem 0 zbiór {0, 1, 2, 3}. Jeżeli po odpowiedzi na pierwsze pytanie dowiemy się, że szu-
kana liczba jest w górnej połowie, to przechodzimy do wierzchołka 1, w przeciwnym
przypadku przechodzimy do 0. Ogólnie, jeżeli z wierzchoÅ‚kiem z etykietÄ… É zwiÄ…zany
jest zbiór AÉ i ten zbiór ma wiÄ™cej niż jeden element, to prawy syn tego wierzchoÅ‚ka ma
etykietÄ™ É1 i jest z nim zwiÄ…zana górna poÅ‚owa zbioru AÉ, a lewy syn ma etykietÄ™ É0 i
jest z nim zwiÄ…zana dolna poÅ‚owa zbioru AÉ. Jeżeli w toku gry trafimy do wierzchoÅ‚ka z
etykietÄ… É, to pytamy, czy szukany element znajduje siÄ™ w górnej, czy w dolnej poÅ‚owie
zbioru AÉ i po uzyskaniu odpowiedzi przechodzimy do odpowiedniego syna. Wierzcho-
łek jest liściem, jeżeli związany z nim zbiór ma tylko jeden element.
Jeżeli szukanym elementem jest 5, to z wierzchołka  przejdziemy do wierzchołka 1,
potem do 10, a na koniec trafimy do wierzchołka 101, który jest związany ze zbiorem jed-
noelementowym {5}. Nie jest przypadkiem, że etykieta wierzchołka odpowiada postaci
1.13. Poszukiwania binarne (binary search) 17
Rysunek 1.1:

0 1
00 01 10 11
000 001 010 011 100 101 110 111
dwójkowej liczby, którą zawiera. Tak dobraliśmy bowiem zbiór wyjściowy A. Możemy
powiedzieć, że zawiera on wszytkie liczby trzy bitowe
A = {000, 001, 010, 011, 100, 101, 110, 111}.
Liczby ze zbioru A1 = {100, 101, 110, 111} związanego z wierzchołkiem 1 mają pierw-
szy bit równy 1, a liczby ze zbioru A0 = {000, 001, 010, 011} związanego z wierzchoł-
kiem 0 majÄ… pierwszy bit równy 0, i ogólnie liczby ze zbioru AÉ zwiÄ…zanego z wierzchoÅ‚-
kiem É majÄ… swoje pierwsze bity równe É. Na przykÅ‚ad z wierzchoÅ‚kiem 10 zwiÄ…zany jest
zbiór A10 = {100, 101}.
Zauważmy także, że kolejne pytania, są pytaniami o kolejne bity szukanej liczby.
W pierwszym pytaniu pytamy o pierwszy, w drugim o drugi, a w trzecim o trzeci bit
szukanej liczby. Oczywiście taka zgodność pomiędzy bitami szukanej liczby i etykietami
wierzchołków drzewa nie wystąpi przy innym ponumerowaniu elementów wyjściowego
zbioru.
Jak zobaczyliśmy trzeba trzy razy kolejno dzielić zbiór na połowy, aby z początko-
wego zbioru 8 elemntowego dojść na końcu do zbiorów jednoelementowych. A ile trzeba
podziałów, jeżeli na początku mamy n = 2k elementów? Po pierwszym podziale nasz
zbiór będzie miał 2k-1 elementów, po drugim 2k-2, a po i-tym 2k-i. Jak widać, potrzeba
k = log2 n kolejnych podziałów, aby dojść do zbioru jednoelementowego. Tak więc jeżeli
mamy do dyspozycji 20 pytań, to możemy odnalez
ć jedną spośród 220 liczb całkowitych
z przedziału od 0 do 220 - 1 = 1 048 575.
18 Rozdział 1. Arytmetyka
1.13.1 Poszukiwanie pierwiastka
Metodę poszukiwań binarnych można zastosować do stwierdzenia, czy jakaś liczba natu-
ralna n jest kwadratem (lub jakąś inną ustaloną potęgą) innej liczby naturalnej. Inaczej,
czy istnieje liczba naturalna k taka, że k2 = n, lub ogólniej, czy istnieje liczba naturalna
k taka, że ką = n.
Poniżej przedstawiamy taki algorytm. Algorytm ten używa dwoch dodatkowych zmien-
nych kd i kg, wartości tych zmiennych przybliżają pierwiastek stopnia ą z n od dołu i od
góry. W trakcie wykonywania algorytmy przybliżeniaa te są coraz lepsze
Algorytm sprawdzający, czy dana liczba naturalna n jest potęgą o wykładniku ą jakiejś
liczby naturalnej.
Dane wejściowe: liczba naturalna n.
Dane wyjściowe: pierwiastek stopnia ą z n, (liczba naturalna m, taka że mą = n) lub
informacja, że n nie ma naturalnego pierwiastka stopnia ą.
kd := 1; kg := n;
Powtarzaj aż do skutku:
jeżeli kg - kd d" 1, to
koniec, n nie ma pierwiastka.
w przeciwnym przypadku
kd+kg
j :=
2
jeżeli ją = n , to koniec, n jest potęgą j.
jeżeli ją > n , to kg := j
jeżeli ją < n , to kd := j.
1.14 Zadania
1. Zwiększ o jeden liczby: a) (11010011)2, b) (111111)2, c) (2012)3, d) (2013)4.
2. Porównaj pary liczb: a) (110011)2, (110100)2, b) (11010)2, (1110)2, c) (12121)3,
(12201)3, d) (33132)4, (33201)4.
3. Dodaj (odejmij, pomnóż) następujące pary liczb: a) (110011)2, (110100)2; b)
(11010)2, (1110)2; c) (11101)2, (1111)2.
4. Dodaj w postaci trójkowej liczby (2101)3 oraz (1212)3.
5. Napisz dokładny algorytm odejmowania dwóch liczb w postaci dwójkowej.
6. Liczby (81)10, (126)10, (200)10, (257)10, (258)10, (1025)10, (1023)10 przedstaw
w postaci dwójkowej i ósemkowej.
7. Jak liczby 4, 20, -4, -20 będą reprezentowane w komputerze jako stałe typu inte-
ger (byte, word)?
8. Liczby $B1, $FF przedstaw w postaci dziesiętnej, dwójkowej i ósemkowej.
1.15. Problemy 19
9. Liczby (80)10, (120)10 przedstaw w postaci trójkowej.
10. Liczby (10001101)2, (100101)2, przedstaw w postaci: dziesiętnej, szesnastkowej i
ósemkowej.
11. Liczby (1023)8, (713)8 przedstaw w postaci dwójkowej i dziesiętnej.
12. Ułamki (0.5625)10, (0.140625)10 przedstaw w postaci dwójkowej.
13. Ułamki (0.1101)2, (0.01101)2, (0.0011)2 przedstaw w postaci dziesiętnej.
14. Opisz algorytm zamiany ułamka z postaci dziesiętnej na postać dwójkową.
15. Ile maksymalnie pytań z odpowiedziami TAK/NIE trzeba zadać, aby odgadnąć licz-
bę: a) z przedziału od 0 do 100 000 b) z przedziału od 0 do 1 000 000?
16. Zastosuj algorytm" " pierwiastków do znalezienia nastÄ™pujÄ…cych pier-
wyznaczania
" "
2 2 3 4
wiastków: 256, 1000, 512, 256.
17. Sprawdz
, czy liczby 111, 1111 są potęgami liczb całkowitych.
1.15 Problemy
1.15.1 Uzupełnieniowy zapis liczb ujemnych
Aby całkowitą liczbę ujemną x z przedziału od -32768 do -1 przedstawić w postaci
uzupełnieniowej na dwóch bajtach:
" zapisz wartość bezwzględną |x| w postaci dwójkowej na szesnastu bitach.Jeżeli
zapis jest krótszy niż szesnaście bitów, uzupełnij go na początku zerami.
" Zamień wszystkie szesnaście bitów: 0 na 1, a 1 na 0,
" Dodaj 1.
Wypróbuj ten sposób na kilku liczbach. Udowodnij, że działa on prawidłowo.
1.15.2 Liczby w postaci ósemkowei i szesnastkowej w języku C
Jak w języku C można zapisać liczby (stałe) w systemie ósemkowym lub szesnastkowym.
Jak w C zadać format, aby liczba całkowita została wydrukowana w systemie ósemko-
wym lub szesnastkowym.
1.15.3 Sumy potęg dwójki
Udowodnij, że jeżeli liczby a1, ... ,ak są różnymi potęgami dwójki, to dla każdego pod-
zbioru I ‚" {1, 2, . . . , k} suma
ai
i"I
jest inna. Pokaż, że tak nie musi być w przypadku dowolnego ciągu różnych liczb.
20 Rozdział 1. Arytmetyka
1.15.4 Waga
Wyobraz
my sobie wagę szalkową. Na jednej szalce, lewej, kładziemy jakiś przedmiot do
zważenia, a następnie na obu szalkach kładziemy odważniki. Jeżeli waga jest w równowa-
dze, to ważony przedmiot ma wagę równą sumie (nominałów) odważników położonych
na prawej szalce minus suma odważników położonych na lewej szalce, obok ważonego
przedmiotu. Na przykład, jeżeli na prawej szalce leżą odważniki 2 i 20 gramowe, a na
lewej odważniki 4 i 5 gramowe, to przedmiot waży 13 = (20 + 2) - (5 + 4) gramów.
Interesujące nas pytanie brzmi: jakie powinny być nominały poszczególnych odważ-
ników, aby można było zważyć każdy ciężar o wadze od 1 do N, przy jak najmniejszej
liczbie odważników. Zakładamy, że ważymy tylko przedmioty o wagach będących dodat-
nimi liczbami naturalnymi.
Pokaż, że
3k-1
(1) Za pomocą k odważników można zważyc co najwyżej różnych ciężarów.
2
(2) Jeżeli nominały odważników są kolejnymi potęgami trójki, to znaczy ci = 3i dla
0 d" i d" k - 1, to za ich pomocą można zważyć każdy ciężar o nominale od 1 do
3k-1
.
2
(3) Jak należy ułożyć na szalkach odważniki o nominałach 1, 3, 9, 27, aby odważyc
ciężar: a) 35, b) 29?
(4) Ile potrzeba odważników, aby zważyć każdy ciężar a) od 1 do 100, b) od 1 do 1000?
(5) Jak należy ułożyć na szalkach odważniki o nominałach będących potęgami trójki
aby odważyc ciężar: a) 50, b) 200, c) 500?
Wskazówki:
(1) Ponieważ każdy odważnik może się znajdować na prawej lub lewej szalce, lub na
stole, to mamy 3k różnych położeń odważników. Wśród tych położeń jest takie, gdzie
wszystkie odważniki leżą na stole (wtedy ważymy zerowy ciężar). Ponadto jeżeli od-
ważniki leżą na szalkach i odważają ciężar W , to zamieniwszy położenia odważników
na szalkach (odważniki z lewej przekładamy na prawą szalkę, i na odwrót), będziemy
odważać ciężar -W .
(2) Rozłożenie odważników przy ważeniu ciężaru W odpowiada przedstawieniu W w
postaci
k-1
W = di3i, (1.5)
i=0
gdzie di " {-1, 0, 1}. Aby przedstawić ciężar W w postaci (1.5), najpierw przedstawia-
3k-1 3k-1
my liczbę W + w systemie trójkowym: W + = (ek-1 . . . e1e0)3, a następnie
2 2
od każdej cyfry odejmujemy jedynkę: di = ei - 1.