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