Wprowadzenie do informatyki - ć wiczenia Systemy liczbowe
dr inż . Izabela Szczęch
WSNHiD 2010/2011
Ćwiczenia z wprowadzenia do informatyki
Plan zaję ć
n
Sy
S stem
y
y lic
y
z
lic bo
z
we
bo
n
addy
add t
y ywne
y
(
wne niepozy
niepoz c
y yjne)
n
poz
po y
z c
y yj
y ne
j
n
Konw
Kon ersja
w
n
konw
on ersja
w
na sy
s ste
y
m
ste dz
d iesi
z
ęt
ę ny (algoryt
y m Hornera)
n
konw
on ersja
w
z syste
y
mu
u dziesi
z
ę
iesi tn
ę e
tn go
n
konw
on ersje:
w
n
dwó
dw jkowo
jko
-ó semkowa,
w
n
ó semkowo
semko
-dwó
dw jkow
jko a
w
n
dwó
dw jkowo-szesnastkowa
w
n
szesnastkowo
szesnastko
-dwó
dw jkowa
2
Izabela Szczęch
1
Wprowadzenie do informatyki - ć wiczenia Systemy liczbowe
System liczbowy
§ System liczbowy to zbió r reguł do jednolitego zapisywania i nazywania liczb.
Do zapisywania liczb uż ywa się pewnego skoń czonego zbioru znakó w, zwanych cyframi (np. arabskimi, rzymskimi), któ re moż na zestawiać ze sobą na ró ż ne sposoby otrzymując nieskoń czoną liczbę kombinacji.
4
Izabela Szczęch
2
Wprowadzenie do informatyki - ć wiczenia System liczbowy
§ Najbardziej prymitywnym systemem liczbowym jest jedynkowy system liczbowy, w któ rym występuje tylko jeden znak (np. 1 albo pionowa kreska). W systemie tym kolejne liczby są tworzone przez proste powtarzanie tego znaku.
Przykładowo, 3 w tym systemie jest zapisywana jako 111, a pięć 11111.
§ Ogó lnie, wśró d systemó w liczbowych moż na wyró ż nić :
§ systemy addytywne (niepozycyjne)
§ systemy pozycyjne
§ Zadanie domowe: określić czy system jedynkowy jest systemem addytywnym czy pozycyjnym.
5
Systemy
Systemy addytywne
§ Systemy addytywne (zwane też niepozycyjnymi)
to systemy liczbowe, w któ rych wartość przedstawionej liczby jest sumą wartości jej znakó w (cyfr).
§ Przykład - rzymski system liczbowy
Jeśli "X"=10,"V"=5,"I"=1
to XVI = 10+5+1 = 16
Aby wyznaczyć wartość dziesiętną liczby zapisanej w systemie rzymskim należ y odejmować wartości znakó w stojących przed znakami większymi , a dodawać wartości znakó w stojących za znakami większymi lub ró wnymi co do wartości.
6
Izabela Szczęch
3
Wprowadzenie do informatyki - ć wiczenia
Systemy
Systemy pozycyjne
§ Pozycyjnym systemem liczbowym nazywamy parę ( P; C), gdzie P jest liczbą naturalną zwaną podstawą systemu, a C jest skoń czonym zbiorem znakó w {0, 1, … , P-1}
zwanych cyframi.
§ W systemie pozycyjnym liczbę przedstawia się jako ciąg cyfr, przy czym wartość tej liczby zależ y zaró wno od cyfr jak i miejsca, na któ rym się one znajdują w tym ciągu.
§ Jeśli P=10, to otrzymujemy dziesiętny system liczbowy, w któ rym występują cyfry ze zbioru {0,… ,9},
dla P = 2 dwó jkowy (binarny) z cyframi ze zbioru {0, 1}, dla P=8 ó semkowy (oktalny) z cyframi ze zbioru {0,… ,7}, itd.
7
Systemy
Systemy pozycyjne
§ Liczba całkowita L zapisana w systemie pozycyjnym o podstawie P w postaci ciągu cyfr
c
… c c
n-1
1 0 ( P)
ma wartość liczbową
w = c
Pn-1 + c
Pn-2 +… + c P 1 + c
n-1
n-2
1
0
gdzie c
,… , c c ∈ C, oraz P jest podstawą systemu.
n-1
1, 0
§ Przykład
§ Liczba 5004 w dziesiętnym systemie liczbowym:
5 x 103 + 0 x 102 + 0 x 101 + 4 x 100 = 5 x 1000 + 4 x 1
8
Izabela Szczęch
4
Wprowadzenie do informatyki - ć wiczenia System dziesię
dziesi tny
(decymalny, arabski )
(decymalny, arabski
§ Podstawę systemu dziesiętnego stanowi liczba 10.
§ Zapis liczby tworzymy za pomocą cyfr o przypisanych wartościach od 0 do 9.
Przykład
126
= 1x102 + 2x101 + 6x100
(10)
9
System dwó
dw jkowy (binarny)
§ Podstawę systemu binarnego stanowi liczba 2.
§ Zapis liczby tworzymy za pomocą cyfr o przypisanych wartościach 0 i 1.
Przykład
1010
= 1x23 + 0x22 + 1x21+ 0x20 = 8 + 2 = 10
(2)
(10)
10
Izabela Szczęch
5
Wprowadzenie do informatyki - ć wiczenia cyfra
warto
w
ść
System szesnastkowy
dziesiętna
0
0
(hexadecymalny)
1
1
§ Podstawę systemu szesnastkowego
2
2
stanowi liczba 16.
3
3
4
4
§ Zapis liczby tworzymy za pomocą cyfr o
5
5
przypisanych wartościach od 0 do 9 oraz
6
6
kolejnych liter alfabetu łaciń skiego A – F
7
7
o przypisanych wartościach od 10 do 15.
8
8
9
9
Przykład
A
10
A1F
= Ax162 + 1x161 + Fx160= 10x256 +
B
11
(16)
C
12
1x16 + 15x1 = 2591(10)
D
13
E
14
F
15
11
Po co jest system szesnastkowy?
§ Jedna cyfra kodu szesnastkowego odpowiada dokładnie czterocyfrowej liczbie systemu dwó jkowego. Ponieważ bajt informacji składa się z 8 bitó w, zatem każ dy bajt danych daje się w sposó b jednoznaczny przedstawić za pomocą dwu cyfr kodu szesnastkowego, co upraszcza kwestię konwersji
§ System szesnastkowy jest wygodny przy zapisie duż ych liczb jak np. adresy pamięci
§ Adresy IP np. w wersji 6 są podawane szesnastkowo 12
Izabela Szczęch
6
Wprowadzenie do informatyki - ć wiczenia Zadania
Z definicji wyznacz dziesiętną wartość poniż szych liczb:
§
421
= ???
(7)
(10)
§
2102
= ???
(3)
(10)
§
AGF63B
= ???
(17)
(10)
13
Konwersja
na
na system
system dziesię
dziesi tny
Izabela Szczęch
7
Wprowadzenie do informatyki - ć wiczenia Konwersja na system
Konwersja na system dziesię
dziesi tny
Algorytm Hornera obliczania wartości dziesiętnej liczby całkowitej zapisanej w innym systemie pozycyjnym
n - liczba cyfr w zapisie pozycyjnym konwertowanej liczby P - podstawa systemu pozycyjnego konwertowanej liczby
c - cyfra konwertowanej liczby stojąca na i-tej pozycji i
Pozycja o numerze 0 to pierwsza pozycja od strony prawej.
w - obliczana dziesiętna wartość konwertowanej liczby 1.
w ← 0
2.
i ← n - 1
3.
w ← c + w * P
i
4.
jeśli i = 0, to koniec, w zawiera wartość liczby 5.
i ← i - 1
6.
wró ć do punktu 3
15
Konwersja na system
Konwersja na system dziesię
dziesi tny
Przykład:
Obliczyć przy pomocy algorytmu Hornera dziesiętną wartość liczby 742031
zapisanej w systemie pozycyjnym
(8)
o podstawie P=8.
w ← 0
w ← 7 + 0 * 8 = 7
w ← 4 + 7 * 8 = 60
w ← 2 + 60 * 8 = 482
w ← 0 + 482 * 8 = 3856
w ← 3 + 3856 * 8 = 30851
w ← 1 + 30851 * 8 = 246809 koń czymy, ponieważ osiągnęliśmy ostatnią cyfrę konwertowanej liczby 16
Izabela Szczęch
8
Wprowadzenie do informatyki - ć wiczenia Konwersja na system
Konwersja na system dziesię
dziesi tny
Zadanie:
Obliczyć przy pomocy algorytmu Hornera
wartość dziesiętną liczby 2210112(3)
zapisanej w systemie pozycyjnym o podstawie P=3.
17
Konwersja
z systemu dziesię
z systemu dziesi tnego
Izabela Szczęch
9
Wprowadzenie do informatyki - ć wiczenia Konwersja z systemu
Konwersja z systemu dziesię
dziesi tnego
Sformułowanie problemu:
znalezienie kolejnych cyfr zapisu liczby dziesiętnej L
w dowolnym systemie docelowym o podstawie P.
Zgodnie z definicją wartość liczby dziesiętnej L wynosi: L = c
Pn-1 + c
Pn-2 + ... + c P 2 + c P + c n-1
n-2
2
1
0
Przykładowo, konwersja liczby L= 6
z systemu
(10)
dziesiętnego na dwó jkowy polega na znalezieniu kolejnych cyfr c czyli cyfr 110
i
(2)
6
= 1*22 + 1*21 + 0*20 =110
(10)
(2)
19
Konwersja z systemu
Konwersja z systemu dziesię
dziesi tnego
Do wydobycia poszczegó lnych cyfr c , i = 0, 1, 2, ..., n-1, i
są nam potrzebne dwa działania:
§ div - dzielenie całkowitoliczbowe - określa ile całkowitą ilość razy dzielnik mieści się w dzielnej,
np.: 9 div 4 = 2, gdyż 4 mieści się w 9 dwa razy
§ mod - reszta z dzielenia całkowitoliczbowego,
np: 9 mod 4 = 1, gdyż 4 mieści się w 9 dwa razy, co daje 8 i pozostawia resztę 1
20
Izabela Szczęch
10
Wprowadzenie do informatyki - ć wiczenia Konwersja z systemu
Konwersja z systemu dziesię
dziesi tnego
Algorytm konwersji liczby z systemu dziesiętnego na system o podstawie P:
w - wartość liczby w systemie dziesiętnym
P - podstawa docelowego systemu pozycyjnego
c - cyfra na i-tej pozycji w systemie pozycyjnym o podstawie p i
1.
i ← 0
2.
c ← w mod P
i
3.
w ← wynik dzielenia całkowitego w div P
4.
jeśli w = 0, to koń czymy, wszystkie cyfry znalezione
5.
i ← i + 1
6.
wró ć do punktu 2.
21
Konwersja z systemu
Konwersja z systemu dziesię
dziesi tnego
Przykład:
Przeliczyć wartość 12786
na system piątkowy.
(10)
w ← 12786 / 5 = 2557 i reszta 1
w ← 2557 / 5 = 511 i reszta 2
w ← 511 / 5 = 102 i reszta 1
w ← 102 / 5 = 20 i reszta 2
w ← 20 / 5 = 4 i reszta 0
w ← 4 / 5 = 0 i reszta 4 (koniec obliczeń , ponieważ otrzymaliśmy wartość 0)
12786
= 402121
(10)
(5)
22
Izabela Szczęch
11
Wprowadzenie do informatyki - ć wiczenia Konwersja z systemu
Konwersja z systemu dziesię
dziesi tnego
Zadania:
§ Przedstawić w systemie dwó jkowym liczbę 865
.
(10)
§ Przedstawić w systemie tró jkowym liczbę 3257
.
(10)
§ Przedstawić w systemie czwó rkowym liczbę 2743
.
(10)
23
Konwersje
2-8, 8-2, 2-16, 16-2
Izabela Szczęch
12
Wprowadzenie do informatyki - ć wiczenia Konwersja dwójkowo-ósemkowa
wartoś ć
cyfra
binarna
110101111011010101011101(2)
0
000(2)
110 101 111 011 010 101 011 101
1
001
(2)
(2)
2
010(2)
110 101 111 011 010 101 011 101
3
011
0
(2)
4
100(2)
6 5 7 3 2 5 3 5
5
101(2)
6
110
1
(2)
7
111(2)
110101111011010101011101(2) =
65732535(8)
25
Konwersja ósemkowo-dwójkowa
wartoś ć
cyfra
binarna
0
000(2)
7 5 2 4 0 1
1
001(2)
2
010(2)
111 101 010 100 000 001
3
011
0
(2)
4
100(2)
752401(8) =
5
101(2)
111101010100000001
6
110
1
(2)
(2)
7
111(2)
26
Izabela Szczęch
13
Wprowadzenie do informatyki - ć wiczenia wartoś ć
cyfra
binarna
Konwersja dwó
dw jkowo-
0
0000(2)
szesnastkowa
1
0001(2)
2
0010(2)
110101111011010101011101(2)
3
0011
0
(2)
4
0100(2)
5
0101
1101 0111 1011 0101 0101 1101
(2)
(2)
6
0110
1
(2)
7
0111(2)
D 7
B 5 5
D
8
1000(2)
9
1001(2)
A
1010(2)
B
1011
0
(2)
110101111011010101011101
C
1100
(2) =
(2)
D
1101
D7B55D
(2)
(16)
E
1110
1
(2)
27
F
1111(2)
wartoś ć
cyfra
binarna
Konwersja szesnastkowo-
0
0000(2)
dwó
dw jkowa
1
0001(2)
2
0010(2)
3
0011
0
(2)
D 7 B 5 5
D
4
0100(2)
5
0101(2)
6
0110
1
(2)
1101 0111 1011 0101 0101 1101
7
0111(2)
8
1000(2)
D7B55D
9
1001
(16)
(2)
A
1010(2)
=110101111011010101011101 (2)
B
1011
0
(2)
C
1100(2)
D
1101(2)
E
1110
1
(2)
28
F
1111(2)
Izabela Szczęch
14