Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 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:

przedstawia liczbę składającą się z jednej setki, siedmiu dziesiątek i ośmiu jedności. Mo-
żemy to zapisać w postaci:

albo inaczej:

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:

a zapis:


oznacza liczbÄ™:




(1.1)
którą możemy też zapisać w postaci:







(1.2)

3
4 Rozdział 1. Arytmetyka




gdzie są cyframi należącymi do zbioru .
Liczby można też zapisywać w systemach z inną bazą. Jeżeli za bazę systemu wybie-
rzemy liczbÄ™ , to potrzebujemy cyfr, a zapis:



oznacza w systemie z bazÄ… liczbÄ™:




(1.3)
którą możemy też zapisać w postaci:







(1.4)

1.2 System dwójkowy
W informatyce bardzo ważnym systemem jest system dwójkowy (binarny), gdzie pod-

stawą jest liczba i gdzie mamy tylko dwie cyfry, 0 i 1 (cyfry w systemie dwójkowym
nazywa siÄ™ bitami). Zapis:



oznacza liczbÄ™:





lub:








Przykład 1.1 Zapis oznacza w systemie dwójkowym liczbę:


czemu w systemie dziesiętnym odpowiada . Podobnie zapis:


oznacza w systemie dziesiętnym liczbę .
Poniżej w pierwszej tabeli przedstawiono siedemnaście kolejnych liczb w postaci dwój-
kowej i dziesiętnej, a w drugiej jedenaście pierwszych potęg liczby 2 w postaci dwójkowej
i dziesiętnej.
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
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
Algorytm zwiększania liczby o jeden. Aby zwiększyć o jeden liczbę zapisaną w syste-
mie dwójkowym:

wskazujemy na ostatni bit,

powtarzamy, co następuje:

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

jeżeli jest on równy jeden, to zamieniamy go na zero i wskazujemy następny
bit w lewo; jeżeli nie ma następnego bitu w lewo, to stawiamy jedynkę na początku
liczby i kończymy algorytm.
6 Rozdział 1. Arytmetyka
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 to .
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 jest liczba .
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.
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ępujemy w następujący sposób:

jeżeli zapisy liczb nie są tej samej długości, to większą jest liczba z dłuższym zapi-
sem (zakładamy tu, że zapis liczby różnej od zera nie ma zer na początku),

jeżeli zapisy liczb są równej długości, to porównujemy bit po bicie od lewej strony
do prawej:

jeżeli bity są takie same, to przechodzimy do następnego bitu w prawo,

jeżeli bity są różne, to kończymy i stwierdzamy, że większa jest ta liczba,
która ma większy bit na tej pozycji,

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


Przykład 1.4 . 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, i prostsze sÄ… operacje na pojedynczych cyfrach.
Zacznijmy od tabliczki dodawania i mnożenia. Wyglądają one tak:
+ 0 1 * 0 1
0 0 1 0 0 0
1 1 10 1 0 1
1.5. Operacje arytmetyczne w systemie dwójkowym 7
Przypuśćmy, że chcemy dodać dwie liczby w postaci dwójkowej. Zakładamy tu, że obie
liczby są tej samej długości. Jeżeli nie są, to krótszą z nich uzupełniamy na początku
zerami.
Algorytm dodawania. Aby dodać dwie liczby w postaci binarnej:






dla kolejnych pozycji od 0 do obliczamy bit sumy oraz  tak zwany bit przenie-
sienia do następnej pozycji:


najpierw obliczamy oraz :





(czyli jest resztÄ… z dzielenia przez 2),



,



następnie po kolei, dla każdego od 1 do , obliczamy:







,




, jeżeli co najmniej dwa spośród bitów , oraz są jedynkami,




na końcu obliczamy najbardziej znaczący bit sumy .
Wynikiem dodawania jest liczba






(może się zdarzyć, że ).

Przykład 1.5 Dodawanie liczb i wygląda następująco:
1 0 1 0 1
+ 1 1 1
1 1 1 0 0
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 i wygląda następująco:
1 0 1 0 1

1 1 1
1 1 1 0
8 Rozdział 1. Arytmetyka
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 i :
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 2 oznacza dopisanie
jednego zera na końcu liczby. Podobnie pomnożenie liczby przez -tą potęgę 2 oznacza

dopisanie na końcu liczby zer.

Przykład 1.8 pomnożone przez daje wynik .
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
Jeżeli liczba jest podzielna przez 2, to ma w postaci binarnej zero na końcu, a jeżeli dzieli

się przez -tą potęgę dwójki, to ma na końcu zer. Podzielenie liczby przez 2 oznacza
skreślenie w jej postaci binarnej jednego zera z końca.

Przykład 1.9 podzielone przez 2 daje .
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Ä… oznaczymy przez:



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ę


1.6. Zamiana systemu 9
w postaci dziesiętnej, korzystamy ze wzoru (1.3):



i wykonujemy wszystkie rachunki w systemie dziesiętnym:



Podobnie możemy postępować przy zamianie w odwrotną stronę, z systemu dziesiętnego
na dwójkowy. Najpierw korzystamy ze wzoru (1.1):



następnie przedstawiamy cyfry i podstawę systemu 10 w postaci dwójkowej i wykonuje-
my wszystkie działania w systemie dwójkowym:



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 ),
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:

Teraz już łatwo zapisać naszą liczbę w postaci dwójkowej:



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
10 Rozdział 1. Arytmetyka
Reszty zapisane w odwrotnej kolejności:





tworzą binarny zapis liczby . Poprawność działania tego algorytmu wynika z fak-

tu, że jeżeli podzielimy liczbę









przez 2, to reszta z dzielenia wyniesie , a iloraz całkowitoliczbowy wyniesie:











następne dzielenie przez 2 da resztę oraz iloraz:









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ą . Należy tylko dzielić przez . Jeżeli chcemy, na przykład,

przedstawić liczbę w systemie trójkowym, to 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: .
1.7 Długość liczby

Zastanówmy sie ile cyfr zawiera zapis dziesietny liczby naturalnej . Cztery cyfry w
¸ ¸



systemie dziesietnym a od do , a cyfr
¸ posiadaj liczby
¸



posiadaja od do . Tak wiec liczba ma cyfr wtedy i tylko wtedy
¸ liczby ¸





gdy , czyli gdy . Mamy więc




Lemat 1.10 Liczba naturalna ma w systemie dziesietnym (w przybliżeniu
¸



) cyfr.




Podobnie w systemie z podstaw¸ , liczba ma cyfr wtedy i tylko wtedy gdy
a



, czyli:
1.8. Duże liczby 11




Lemat 1.11 W systemie o podstawie liczba naturalna ma (w przybliżeniu



) cyfr.
Korzystajac z tego faktu możemy ustalać przybliżona liczbe cyfr potrzebna do zapisu
¸ ¸ ¸ ¸
liczb.




Wniosek 1.12 Liczba, posiadajaca cyfr w systemie dziesietnym ma około
¸ ¸


bitów w systemie dwójkowym, a liczba majaca bitów w postaci dwójkowej ma
¸


około cyfr w postaci dziesietnej.
¸




Dowód: Jeżeli liczba ma w postaci dziesiętnej cyfr, to . W dwój-
postaci





kowej ma około bitów, ,
a




ponieważ .


Podobnie, jeżeli liczba ma w postaci
dwójkowej bitów, to w postaci dziesiętnej




ma około .
1.8 Duże liczby
Aby sie zorientować jak duże moga być liczby przedstawione za pomoca systemu dziesietnego
¸ ¸ ¸ ¸
lub dwójkowego przypatrzmy sie poniższej tabeli:
¸


Liczba sekund w roku


Wiek układu słonecznego w latach


Wiek układu słonecznego w sekundach


Liczba cykli w roku (100 MHz)



Liczba ciagów 64 bitowych
¸



Liczba ciagów 128 bitowych
¸


Liczba ciagów 256 bitowych
¸


Liczba atomów na Ziemi


Liczba atomów w naszej galaktyce
Dane do tabeli zaczerpnieto z ksiażki A. Menezes, P. van Oorschot and S. Vanstone,
¸ ¸
Handbook of Applied Cryptography. oraz z ksiażki B. Schneier, Applied Cryptography.
¸
Tabela ta pozwala ocenić niektóre algorytmy.

Przykład 1.13 Rozważmy prosty algorytm sprawdzajacy, czy liczba naturalna jest pierw-
¸

sza. Algorytm ten dzieli przez kolejne liczby od 2 do . Jeżeli ma 120 bitów, to


potrzeba dzieleń. Jeżeli założymy, że komputer potrafi wykonać milionów


dzieleń w ciagu sekundy i w ciagu roku, to bedzie liczył około 300 lat. W rozdziale
¸ ¸ ¸
o teorii liczb bedziemy mówić o szybszych algorytmach sprawdzajacych pierwszość liczb
¸ ¸
majacych po kilkaset bitów.
¸
Przykład 1.14 Przypuśćmy, że chcemy zaprojektować tablice, która dla każdego ciagu
¸ ¸
złożongo z ośmiu liter przechowuje jakaś informacje (jeden bajt). W przypadku 26 liter
¸ ¸
takich ciagów mamy
¸


zatem potrzebowalibyśmy wiecej niż 100 gigabajtów pamieci.
¸ ¸
12 Rozdział 1. Arytmetyka
1.9 UÅ‚amki
Przypomnijmy najpierw krótko, jak przedstawia się ułamek w systemie dziesiętnym. Na
przykład,

oznacza:


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:



oznacza liczbÄ™:



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









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:



oznacza liczbÄ™:




lub inaczej:







Przykład 1.15



W poniższej tabeli przedstawiono kilka pierwszych ujemnych potęg liczby 2 w systemie
dwójkowym i dziesiętnym.



















1.10. System szesnastkowy 13
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 :


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

Przykład 1.16 Zapis oznacza liczbę w systemie szesnastkowym, która w systemie


dziesiętnym ma postać
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, w systemie szesnastkowym wygląda tak w systemie
która

dwójkowym ma postać .
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 .
14 Rozdział 1. Arytmetyka
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 .
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 jest przechowywana jako:


Największą liczbę dodatnią, jaką można przechować w zmiennej typu integer, jest:


czyli zero i piętnaście jedynek. Jest to:





Liczby ujemne są przechowywane w tak zwanym systemie uzupełnieniowym. Liczba

ujemna o wartości bezwzględnej jest przedstawiana jako liczba:





w postaci binarnej. Na przykład liczba jest przedstawiona jako:




czyli szesnaście jedynek. A liczba jako:


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


1.11. Reprezentacja liczb w komputerze 15
czyli jedynka i piętnaście zer, która koduje liczbę:





Często nie ma żadnego zabezpieczenia przed przekroczeniem maksymalnego lub mini-

malnego zakresu liczb typu integer. Jeżeli, na przykład, do liczby , która jest prze-
chowywana jako:


dodamy jedynkÄ™, to otrzymamy:




która koduje liczbę , 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:

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:





gdzie jest mantysą, liczbą w postaci dziesiętnej z przedziału lub



, a , zwana cechą, jest liczbą całkowitą. Zapis oznacza liczbę:



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


4837.92



0.034


Sposób przechowywania wartości zmiennych typu real jest skomplikowany i nie będzie
przedstawiony szczegółowo.
16 Rozdział 1. Arytmetyka
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 do ,


byte, zawiera liczby całkowite z przedziału od do ,


word, zawiera liczby całkowite z przedziału od do ,



longint, zawiera liczby całkowite z przedziału od do .
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:


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).
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.
1.13. Poszukiwania binarne (binary search) 17
Najpierw uprośćmy nieco tę grę. Załóżmy, że możemy zadać tylko cztery pytania i że

odgadujemy liczbÄ™ naturalnÄ… ze zbioru:



Wtedy należy zadać następujące cztery pytania:



Czy liczba należy do zbioru ?



Czy należy do zbioru ?



Czy należy do zbioru ?



Czy należy do zbioru ?
Dlaczego te cztery pytania wystarczą? Sprawa stanie się jasna, jeżeli przedstawimy liczby
w postaci binarnej. Każdą za pomocą czterech bitów (z zerami na początku). Wtedy nasz
zbiór wygląda tak:




A pytania wyglÄ…dajÄ… teraz tak:




Czy należy do zbioru




Czy należy do zbioru




Czy należy do zbioru




Czy należy do zbioru


Zauważmy, że zbiór zawiera wszystkie liczby z pierwszym bitem równym jedynce,


w są wszystkie liczby z drugim bitem równym jedynce, i tak dalej. Tak więc nasze
pytania są w rzeczywistości pytaniami o kolejne bity odgadywanej liczby. Na przykład w
pierwszym pytaniu pytamy, czy pierwszy bit odgadywanej liczby jest jedynkÄ….
Ale można do tych pytań podejść inaczej. Najpierw dzielimy zbiór na połowy: na
liczby mniejsze od ośmiu i na liczby większe lub równe ośmiu, 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ń. Przypuśćmy, że
odgadywaną liczbą jest 11. W drugim etapie dzielimy przedział


na połowy, górną:


i dolnÄ…:


18 Rozdział 1. Arytmetyka
i pytamy, do której połowy należy szukana liczba. Po drugiej odpowiedzi przedział po-
szukiwań jest już cztery razy krótszy. Po dwóch kolejnych pytaniach przedział zawęża się
do jednej liczby. Drugi sposób jest całkowicie równoważny pierwszemu, tutaj też pytamy
o kolejne bity i otrzymujemy takie same odpowiedzi.
Potrzeba cztery razy kolejno dzielić zbiór na połowy, aby z początkowej długości

16 przejść na końcu do długości 1. A ile trzeba podziałów, jeżeli na początku
mamy



elementów? Po pierwszym podziale nasz zbiór będzie miał długość , po



drugim , a po -tym . Jak widać, potrzeba kolejnych podziałów, aby
dojść do 1. Tak więc jeżeli mamy do dyspozycji pyta to możemy odnalez
ć jedną
Å„,


spośród liczb całkowitych z przedziału od do .
Metodę poszukiwań binarnych można zastosować do stwierdzenia, czy jakaś liczba

naturalna jest kwadratem (lub jakąś inną ustaloną potęgą) innej liczby naturalnej. Ina-



czej, czy istnieje liczba naturalna taka, że , lub ogólniej, czy istnieje liczba



naturalna taka, że .
Poniżej przedstawiamy taki algorytm. Algorytm ten używa dwoch dodatkowych zmien-



nych i , wartości tych zmiennych przybliżają pierwiastek stopnia z od dołu i od
góry. W trakcie wykonywania algorytmy przybliżeniaa te są coraz lepsze

Algorytm sprawdzający, czy dana liczba naturalna jest potęgą o wykładniku jakiejś
liczby naturalnej.

Dane wejściowe: liczba naturalna .


Dane wyjściowe: pierwiastek stopnia z , (liczba naturalna , taka że ) lub

informacja, że nie ma pierwiastka stopnia .






Powtarzaj aż do skutku:



jeżeli , to koniec, nie ma pierwiastka.









jeżeli , to koniec, jest potęgą .



jeżeli , to




jeżeli , to .
1.14 Zadania


1. Zwiększ o jeden następujące liczby zapisane w postaci dwójkowej: a)

b) .


2. Porównaj następujące pary liczb: a) , b) , .

3. Dodaj w postaci dwójkowej następujące pary liczb: a) ,
(odejmij, pomnóż)

b) , .
1.15. Problem: Waga 19
4. Napisz dokładny algorytm odejmowania dwóch liczb w postaci dwójkowej.
5. Liczby 81, 126 przedstaw w postaci dwójkowej. Jak będą one reprezentowane w
komputerze jako stałe typu integer (byte, word)?
6. Następujące liczby przedstaw w postaci dwójkowej: 6.75, 5.625, $B1, $FF.
7. Następujące liczby przedstaw w postaci trójkowej: 80, 120.
8. Następujące liczby w postaci dwójkowej, 10001101, 100101, przedstaw w postaci:
a) dziesiętnej, b) szesnastkowej.
9. Opisz algorytm zamiany ułamka z postaci dziesiętnej na postać dwójkową.
10. Ile maksymalnie pytań z odpowiedziami TAK/NIE trzeba zadać, aby odgadnąć licz-
bę z przedziału od 0 do 100 000?
11. Zastosuj algorytm wyznaczania pierwiastków do znalezienia pierwiastka stopnia 3
z liczby 512.
1.15 Problem: 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żą i gramowe, a na
odważniki



lewej odważniki i gramowe, to przedmiot waży 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 do , przy jak najmniejszej
liczbie odważników. Zakładamy, że ważymy tylko przedmioty o całkowitych wagach.
Pokaż, że




(a) Za pomocą odważników można zważyc co najwyżej różnych ciężarów.

(b) Jeżeli nominały odważników są kolejnymi potęgami trójki, to znaczy dla


, to za ich pomocą można zważyć każdy (całkowity) ciężar o nominale




od 1 do .
Wskazówki:
(a) Ponieważ każdy odważnik może się znajdować na prawej lub lewej szalce, lub na stole,

to mamy 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 odważniki leżą
na szalkach i odważają ciężar , 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

.
20 Rozdział 1. Arytmetyka
(b) Rozłożenie odważników przy ważeniu ciężaru odpowiada przedstawieniu w

postaci







(1.5)






gdzie . Aby przedstawić ciężar w postaci (1.5), przedstawia-
najpierw








my liczbę w systemie trójkowym: ,



a następnie od każdej cyfry odejmujemy jedynkę: .