Matma Dyskretna. Vol.2 Arytmetyka(zadania+przyklady), uniwersytet gdański, Matematyka dyskretna

[ Pobierz całość w formacie PDF ]
§2 Arytmetyka
Niech b = d
r
d
r−1
. . . d
1
d
0
będzie zapisem liczby w systemie dwójkowym. Zamiana zapisu liczby b
na system dziesiętny odbywa się poprzez wykonanie dodawania
d
r
∗2
r
+ d
r−1
∗2
r−1
. . . d
1
∗2
1
+ d
0
∗2
0
,
przy czym dodawanie to jest wykonywane w systemie o podstawie 10.
Przykład 2.1. Liczbę 10010 zapisaną w systemie dwójkowym przedstaw w systemie dziesięt
nym.
Odpowiedź 2.1. (10010)
2
= 1∗2
4
+ 0∗2
3
+ 0∗2
2
+ 1∗2
1
+ 0∗2
0
= (18)
10
.
Zadanie 2.2. Podane niżej liczby zapisane w systemie dwójkowym przedstaw w systemie dziesięt
nym:
a) 101011.
b) 111101.
c) 101111.
Algorytm zwiększania liczby o „1”:
€
wskaż ostatni bit rozważanej liczby.
€
powtarzaj, co następuje:
– jeżeli wskazywany bit to „0”, to zamień go na „1” i Koniec;
– w przeciwnym przypadku zamień go na „0” i wskaż kolejny bit na lewo; jeżeli nie ma
następnego bitu w lewo, to wstaw „1” i Koniec
Przykład 2.3. Prześledź działanie algorytmu dodawania „1” dla liczb (a) 10010 oraz (b) 101011.
Odpowiedź 2.3.
a) 10010 + 1 = 10011, bo 10010→(= 0)→10011 (Koniec).
b) 101011 + 1 = 101100,
bo 101011→(= 1)→101010→(= 1)→101000→(= 0)→101100 (Koniec).
Zadanie 2.4. Prześledź działanie algorytmu dodawania „
1
” dla następujących liczb:
a) 111110.
b) 101111.
c) 10011.
1
Algorytm porównywania liczb:
€
jeżeli liczby są różnej długości, to większą jest liczba o dłuższym zapisie,
€
jeżeli liczby są tej samej długości, to porównujemy bit po bicie od lewj strony do prawej:
– jeżeli bity są takie same, to przechodzimy do następnego bitu w prawo;
– jeżeli bity są różne, to więszą jest liczba o większym bicie na rozważanej pozycji i Koniec.
€
jeżeli wszystkie bity są takie same, to porównywane liczby są równe i Koniec.
Przykład 2.5. Prześledź działanie algorytmu porównywania liczb dla następujących par liczb:
a) 101101 i 11110.
b) 1011101 i 1011001.
Odpowiedź 2.5.
a) Jako że długość (liczba bitów) pierwszej liczby jest większa od długości liczby drugiej, otrzy
mujemy 101101 > 11110.
b) (1011101 ? 1011001)→(=)→(1011101 ? 1011001)→(=)→
(1011101 ? 1011001)→(>)→, a zatem 1011101 > 1011001.
Zadanie 2.6. Prześledź działanie algorytmu porównywania liczb dla następujących par liczb:
a) 1111 i 10001.
b) 11010 i 10111.
c) 1111001 i 1111011.
Algorytm dodawania liczb:
Aby dodać do siebie dwie liczby zapisane w systemie dwójkowym, dodajemy bit po bicie od
prawej do lewej, dodając jednocześnie w każdym z kroków bit przeniesienia z poprzedniej
kolumny.
Przykład 2.7. Wykonaj dodawanie 10101 + 111.
Odpowiedź 2.7. 10101 + 111 = 11100, ponieważ
01010
10101
.
+
111
11100
Zadanie 2.8. Wykonaj dodawanie:
a) 1111 + 1110.
b) 10011 + 1100.
c) 110111 + 110011.
d) 101 + 111 + 111.
e) 1011 + 1011 + 111.
2
Algorytm odejmowania liczb:
Aby odjąć od siebie dwie liczby zapisane w systemie dwójkowym, odejmujemy bit po bicie od
prawej do lewej, a w przypadku, gdy trzeba odjąć bit większy od mniejszego, „pożyczamy”
dwójkę z następnej (w lewo) pozycji.
Przykład 2.9. Wykonaj odejmowanie:
a) 10101 111.
b) 111000 11111.
Odpowiedź 2.9.
a) 10101−111 = 1110, ponieważ
012
2
1002
10101
− 111
1110
.
b) 111000−11111 = 11001, ponieważ
02
0112
102
112
110112
111000
− 11111
11001
.
Zadanie 2.10. Wykonaj odejmowanie:
a) 10011 1100.
b) 110111 110011.
c) 1010001 101110.
d) 1011100 1010111.
Algorytm mnożenia liczb:
Aby pomnożyć dwie liczby (zapisane dwójkowo), mnożymy pierwszą liczbę przez poszczególne
bity drugiej, a otrzymane wyniki, każdy kolejno przesunięty o jedną kolumnę w lewo, na
koniec sumujemy.
Przykład 2.11. Wykonaj mnożenie 10101101.
Odpowiedź 2.11. 10101101 = 1101001, ponieważ
10101
101
10101
00000
1
10101
01
1101001
.
Zauważmy, że aby ułatwić sobie mnożenie liczb, mając na uwadze przemienność mnożenia, wygod
niej jest mnożyć liczbę o większej jedynek przez liczbę o mniejszej liczbie jedynek, tzn. ropztrywać
iloczyn 10101101 raczej niż iloczyn 10110101.
3
Zadanie 2.12. Wykonaj mnożenie:
a) 101111.
b) 1111111.
c) 100111100.
d) 111000111.
Przykład 2.13. Wykonaj dzielenie 1101001 : 101.
Odpowiedź 2.13. 1101001 : 101 = 10101, ponieważ
10101
1101001 : 101
101
1001
00110
01
101
01
00101
00101
0
.
Zadanie 2.14. Wykonaj dzielenie:
a) 100011 : 101.
b) 1101001 : 111.
c) 110001 : 111.
d) 11000 : 1000.
e) 1010001 : 1001.
Uwaga 1. Liczba jest podzielna przez 2 (lub 10), jeśli ostatni bit równy jest
0
.
Uwaga 2. Liczba jest podzielna przez 2
i
| {z }
i
zer
), jeśli ma na końcu i bitów równych 0.
Niech b będzie liczbą zapisaną w systemie dziesiętnym. Zamiana zapisu liczby b na system
dwójkowy odbywa się poprzez rozłożenie b na sumę kolejnych potęg dwójki:
b = d
r
∗2
r
+ d
r−1
∗2
r−1
. . . d
1
∗2
1
+ d
0
∗2
0
,
gdzie d
i
∈{0, 1}. Wówczas b = (d
r
d
r−1
. . . d
1
d
0
)
2
.
Przykład 2.15. Zamień zapis z dziesiętnego na dwójkowy liczby 81.
Odpowiedź 2.15.
(81)
10
= (64 + 16 + 1) = 1∗2
6
+ 0∗2
5
+ 1∗2
4
+ 0∗2
3
+ 0∗2
2
+ 0∗2
1
+ 1∗2
1
= (1010001)
2
.
Zadanie 2.16. Zamień zapis z dziesiętnego na dwójkowy liczb:
a) 111.
b) 169.
c) 411.
4
(1
0...0
Drugi sposób polega na kolejnym dzieleniu liczby w sposób całkowity przez 2 i zapamiętywaniu
reszt z dzielenia. Reszty te, zapisane w odwrotnej kolejności, tworzą zapis binarny liczby.
Przykład 2.17. Korzystając z w/w opisanego sposobu zamień zapis z dziesiętnego na dwójkowy
liczby 81.
liczba iloraz reszta
169
84 1
84
42 0
42
21 0
Odpowiedź 2.17. (81)
10
= (1010001)
2
, ponieważ
21
10 1
.
10
5 0
5
2 1
2
1 0
1
0 1
Zadanie 2.18. Korzystając z w/w opisanego sposobu zamień zapis z dziesiętnego na dwójkowy
liczb z Zadania 2.16.
W systemie szesnastkowym używa się następujących „cyfr”: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
Przyjmijmy notację, że liczbę zapisaną w systemie szesnastkowym poprzedza znak dolara $.
Przykład 2.19. Zamień zapis liczby $A1 z szesnastkowego na dziesiętny.
Odpowiedź 2.19. $A1 = 10∗16
1
+ 1∗16
0
= 160 + 1 = (161)
10
.
Zadanie 2.20. Zamień zapis z szesnastkowego na dziesiętny liczb:
a) $A91.
b) $C2.
c) $FCA.
Przykład 2.21. Zamień zapis liczby 33 z dziesiętnego na szesnastkowy.
Odpowiedź 2.21. 33 = 2∗16
1
+ 1∗16
0
= $21.
Zadanie 2.22. Zamień zapis z dziesiętnego na szesnastkowy liczb:.
a) 82.
b) 321.
c) 855.
Przykład 2.23. Zamień zapis liczby $A1 z szesnastkowego na binarny.
Odpowiedź 2.23. $A1 = (10110001)
2
, ponieważ
A 1
1011 0001
.
5
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • mement.xlx.pl

    • Tematy