Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

1

Systemy liczbowe

Systemy liczbowe

dr inż . Izabela Szczęch
WSNHiD
Ćwiczenia z wprowadzenia do informatyki

n

n

Systemy liczbowe

Systemy liczbowe

n

n

addytywne (

addytywne (niepozycyjne

niepozycyjne))

n

n

pozycyjne

pozycyjne

n

n

Konwersja

Konwersja

n

n

konwersja

konwersja na

na system dziesiętny (algorytm

system dziesiętny (algorytm Hornera

Hornera))

n

n

konwersja

konwersja zz systemu dziesiętnego

systemu dziesiętnego

n

n

konwersje:

konwersje:

n

n

dwó jkowo

dwó jkowo--ó semkowa,

ó semkowa,

n

n

ó semkowo

ó semkowo--dwó jkowa

dwó jkowa

n

n

dwó jkowo

dwó jkowo--szesnastkowa

szesnastkowa

n

n

szesnastkowo

szesnastkowo--dwó jkowa

dwó jkowa

Plan zaję ć

Plan zaję ć

2

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

2

Systemy liczbowe

Systemy liczbowe

System liczbowy

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

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

3

System liczbowy

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 addytywne

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

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

4

Systemy pozycyjne

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 pozycyjne

Systemy pozycyjne

§

Liczba całkowita L zapisana w systemie pozycyjnym o
podstawie P w postaci ciągu cyfr

c

n-1

… c

1

c

0 (P)

ma wartość liczbową

w = c

n-1

P

n-1

+ c

n-2

P

n-2

+… + c

1

P

1

+ c

0

gdzie c

n-1

,… ,c

1,

c

0

Î

C, oraz P jest podstawą systemu.

§

Przykład

§

Liczba 5004 w dziesiętnym systemie liczbowym:

5 x 10

3

+ 0 x 10

2

+ 0 x 10

1

+ 4 x 10

0

= 5 x 1000 + 4 x 1

8

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

5

System dziesię tny

System 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

(10)

= 1x10

2 +

2x10

1

+ 6x10

0

9

System dwójkowy (binarny)

System 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

(2)

= 1x2

3 +

0x2

2

+ 1x2

1

+ 0x2

0

= 8 + 2 = 10

(10)

10

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

6

System szesnastkowy

System szesnastkowy

((hexadecymalny

hexadecymalny))

§

Podstawę systemu szesnastkowego
stanowi liczba 16.

§

Zapis liczby tworzymy za pomocą cyfr o
przypisanych wartościach od 0 do 9 oraz
kolejnych liter alfabetu łaciń skiego A – F
o przypisanych wartościach od 10 do 15.

Przykład

A1F

(16)

= Ax16

2 +

1x16

1

+ Fx16

0

= 10x256 +

1x16 + 15x1 = 2591

(10)

cyfra

cyfra

wartość

wartość
dziesiętna

dziesiętna

00

00

11

11

22

22

33

33

44

44

55

55

66

66

77

77

88

88

99

99

A

A

10

10

B

B

11

11

C

C

12

12

D

D

13

13

E

E

14

14

F

F

15

15

11

Po co jest system szesnastkowy?

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

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

7

Zadania

Zadania

Z definicji wyznacz dziesiętną wartość poniż szych liczb:

§

421

(7)

= ???

(10)

§

2102

(3)

= ???

(10)

§

AGF63B

(17)

= ???

(10)

13

Konwersja

Konwersja

na system dziesię tny

na system dziesię tny

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

8

Konwersja na system dziesię tny

Konwersja na system 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

i

- cyfra konwertowanej liczby stojąca na i-tej pozycji

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

i

+ w * P

4.

jeśli i = 0, to koniec, w zawiera wartość liczby

5.

i

←

i - 1

6.

wró ć do punktu 3

15

Konwersja na system dziesię tny

Konwersja na system dziesię tny

Przykład:
Obliczyć przy pomocy algorytmu Hornera dziesiętną wartość
liczby 742031

(8)

zapisanej w systemie pozycyjnym

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

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

9

Konwersja na system dziesię tny

Konwersja na system dziesię tny

Zadanie:

Obliczyć przy pomocy algorytmu Hornera
wartość dziesiętną liczby 2210112

(3)

zapisanej w systemie pozycyjnym o podstawie P=3.

17

Konwersja

Konwersja

z systemu dziesię tnego

z systemu dziesię tnego

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

10

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

n-1

P

n-1

+ c

n-2

P

n-2

+ ... + c

2

P

2

+ c

1

P + c

0

Przykładowo, konwersja liczby L= 6

(10)

z systemu

dziesiętnego na dwó jkowy polega na znalezieniu kolejnych
cyfr c

i

czyli cyfr 110

(2)

6

(10)

= 1*2

2

+ 1*2

1

+ 0*2

0

=110

(2)

19

Konwersja z systemu dziesię tnego

Konwersja z systemu dziesię tnego

Do wydobycia poszczegó lnych cyfr c

i

, i = 0, 1, 2, ..., n-1,

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

Konwersja z systemu dziesię tnego

Konwersja z systemu dziesię tnego

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

11

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

i

- cyfra na i-tej pozycji w systemie pozycyjnym o podstawie p

1. i ← 0
2. c

i

←

w mod P

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 dziesię tnego

Konwersja z systemu dziesię tnego

Przykład:
Przeliczyć wartość 12786

(10)

na system piątkowy.

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

(10)

= 402121

(5)

22

Konwersja z systemu dziesię tnego

Konwersja z systemu dziesię tnego

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

12

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

Konwersja z systemu dziesię tnego

Konwersja z systemu dziesię tnego

Konwersje

Konwersje

22--8, 8

8, 8--2, 2

2, 2--16, 16

16, 16--22

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

13

Konwersja dwójkowo

Konwersja dwójkowo--ósemkowa

ósemkowa

110101111011010101011101

(2)

110 101 111 011 010 101 011 101

(2)

110 101 111 011 010 101 011 101

6 5 7 3 2 5 3 5

110101111011010101011101

(2)

=

65732535

(8)

25

cyfra

cyfra

w

warto

artośś ćć

binarna

binarna

00

000

000

(2)

(2)

11

001

001

(2)

(2)

22

010

010

(2)

(2)

33

011

011

(2)

(2)

44

100

100

(2)

(2)

55

101

101

(2)

(2)

66

110

110

(2)

(2)

77

111

111

(2)

(2)

Konwersja ósemkowo

Konwersja ósemkowo--dwójkowa

dwójkowa

7 5 2 4 0 1

111 101 010 100 000 001

752401

(8)

=

111101010100000001

(2)

26

cyfra

cyfra

w

warto

artośś ćć

binarna

binarna

00

000

000

(2)

(2)

11

001

001

(2)

(2)

22

010

010

(2)

(2)

33

011

011

(2)

(2)

44

100

100

(2)

(2)

55

101

101

(2)

(2)

66

110

110

(2)

(2)

77

111

111

(2)

(2)

Wprowadzenie do informatyki - ć wiczenia

Izabela Szczęch

14

Konwersja dwójkowo

Konwersja dwójkowo--

szesnastkowa

szesnastkowa

110101111011010101011101

(2)

1101 0111 1011 0101 0101 1101

(2)

D 7

B 5 5

D

110101111011010101011101

(2)

=

D7B55D

(16)

27

cyfra

cyfra

w

warto

artośś ćć

binarna

binarna

00

00000

000

(2)

(2)

11

000001

01

(2)

(2)

22

00010

010

(2)

(2)

33

00011

011

(2)

(2)

44

00100

100

(2)

(2)

55

00101

101

(2)

(2)

66

00110

110

(2)

(2)

77

00111

111

(2)

(2)

88

11000

000

(2)

(2)

99

11001

001

(2)

(2)

A

A

11010

010

(2)

(2)

B

B

11011

011

(2)

(2)

C

C

11

1100

00

(2)

(2)

D

D

1110

1011

(2)

(2)

E

E

11110

110

(2)

(2)

F

F

1111

1111

(2)

(2)

Konwersja szesnastkowo

Konwersja szesnastkowo--

dwójkowa

dwójkowa

28

D 7 B 5 5

D

1101 0111 1011 0101 0101 1101

D7B55D

(16)

=110101111011010101011101

(2)

cyfra

cyfra

w

warto

artośś ćć

binarna

binarna

00

00000

000

(2)

(2)

11

000001

01

(2)

(2)

22

00010

010

(2)

(2)

33

00011

011

(2)

(2)

44

00100

100

(2)

(2)

55

00101

101

(2)

(2)

66

00110

110

(2)

(2)

77

00111

111

(2)

(2)

88

11000

000

(2)

(2)

99

11001

001

(2)

(2)

A

A

11010

010

(2)

(2)

B

B

11011

011

(2)

(2)

C

C

11

1100

00

(2)

(2)

D

D

1110

1011

(2)

(2)

E

E

11110

110

(2)

(2)

F

F

1111

1111

(2)

(2)