Ćwiczenie VII

1. Pojęcia

            Algorytm sortowania przez scalanie

            Algorytm Hornera

            Systemy liczbowe

            Zapis dziesiętny, dwójkowy, szesnastkowy

            Kod znak-moduł

            Kod U2

 

2. Wiadomości

 

2.1 Sortowanie przez scalanie

 

Algorytm scalania dwóch ciągów uporządkowanych można opisać w następujący sposób:

 

Dane: Dwa uporządkowane ciągi X oraz Y.

 

Wynik: Uporządkowany ciąg Z, będący połączeniem ciągów X, Y.

 

Krok 1. Dopóki oba ciągi X i Y są niepuste wykonuj następującą operację: przenieś mniejszy z najmniejszych elementów z ciągów X i Y do ciągu Z.

 

Krok 2. Do końca ciągu Z dopisz elementy pozostałe w jednym z ciągów X lub Y.

 

Przykład:

 

          5  13        21                 31    45    88   95           107

                               5  13  21  31  45  88  95  107

 

 

            Podana metoda może zostać wykorzystana do posortowania ciągu elementów poprzez scalanie. Podany algorytm zajmuje jednak dużo pamięci – nie jest wykonywany w miejscu, z tego względu sortowanie szybkie jest lepszym rozwiązaniem.

 

 

 

 

2.2 Zapis formalny systemów liczbowych

 

            Najbardziej rozpowszechnioną formą zapisu liczbowego jest zapis w postaci tzw. jednorodnego rozwinięcia systematycznego będącego rozwinięciem liczby L na sumę potęg wybranej liczby q, w ogólnej postaci:

L = Ckqk+...+C0q0=CkCk=1...C0.

·         Dziesiętny gdzie q = 10,

·         Dwójkowy ( binarny ) gdzie q = 2,

·         Ósemkowy ( oktalny ) gdzie q = 8

·         Szesnastkowy ( heksadecymalny ) gdzie  q = 16.

Podstawowe cechy każdego systemu pozycyjnego można scharakteryzować w sposób następujący:

 

·   Stosuje się ograniczoną liczbę cyfr, które posiadają kolejne wartości 0,1,2,... Pomimo tego, system pozycyjny nie jest w żaden sposób ograniczony co do wielkości zapisywanych liczb.

 

·   Każdy system pozycyjny ma przypisaną pewną wartość charakterystyczną, którą nazywamy podstawą systemu. Liczba cyfr jest równa wartości podstawy. Dla systemu dziesiętnego mamy zbiór 10 cyfr, bo podstawa wynosi 10. W systemie szóstkowym cyfr będzie 6 {0, 1, 2, 3, 4, 5}. W systemach o podstawie większej niż 10 potrzebujemy więcej cyfr, niż zdefiniowano dla systemu dziesiętnego. Problem ten rozwiązujemy przyjmując za dodatkowe cyfry kolejne literki alfabetu. Np. w systemie dwunastkowym musimy posiadać dwanaście cyfr {0,1,...,8,9,A,B}. Cyfra A ma wartość 10, a cyfra B ma wartość 11.

 

·   Wartość cyfry w zapisie zależy od jej pozycji, stąd pochodzi nazwa "system pozycyjny". Każda pozycja ma przypisaną wagę. Wagi pozycji są równe kolejnym potęgom podstawy systemu liczonym od strony prawej.

 

·   Wartość liczby w zapisie pozycyjnym obliczamy jako sumę iloczynów cyfr przez wagi swoich pozycji.

 

 

dziesiętny

dwójkowy

ósemkowy

szesnastkowy

0

0

0

0

1

1

1

1

2

10

2

2

3

11

3

3

4

100

4

4

5

101

5

5

6

110

6

6

7

111

7

7

8

1000

10

8

9

1001

11

9

10

1010

12

A

11

1011

13

B

12

1100

14

C

13

1101

15

D

14

1110

16

E

15

1111

17

F

 

 

2.3 Algorytm Hornera obliczania wartości liczby całkowitej

 

n - liczba cyfr w zapisie pozycyjnym danej liczby
p - podstawa systemu pozycyjnego, w którym jest zapisana liczba
ci - cyfra stojąca na i-tej pozycji. Pozycja o numerze 0 jest pierwszą pozycją od strony prawej.
w - obliczana wartość liczby

  1. w ¬ 0
  2. i ¬ n - 1
  3. w ¬ ci + w x p
  4. jeśli i = 0, to koniec, w zawiera wartość liczby
  5. i ¬ i - 1
  6. wróć do punktu 3

 


Obliczyć przy pomocy algorytmu Hornera wartość liczby 742031 zapisanej w systemie pozycyjnym o podstawie p=8.

·        w ¬ 0

·        w ¬ 7 + 0 x 8 = 7

·        w ¬ 4 + 7 x 8 = 60

·        w ¬ 2 + 60 x 8 = 482

·        w ¬ 0 + 482 x 8 = 3856

·        w ¬ 3 + 3856 x 8 = 30851

·        w ¬ 1 + 30851 x 8 = 246809 i kończymy, ponieważ osiągnęliśmy ostatnią cyfrę


Obliczyć przy pomocy algorytmu Hornera wartość liczby 2210112 zapisanej w systemie pozycyjnym o podstawie p=3.

·        w ¬ 0

·        w ¬ 2 + 0 x 3 = 2

·        w ¬ 2 + 2 x 3 = 8

·        w ¬ 1 + 8 x 3 = 25

·        w ¬ 0 + 25 x 3 = 75

·        w ¬ 1 + 75 x 3 = 226

·        w ¬ 1 + 226 x 3 = 679

·        w ¬ 2 + 679 x 3 = 2039 i kończymy, gdyż osiągnęliśmy już ostatnią cyfrę

·         

2.4 Algorytm zamiany liczby naturalnej z systemu dziesiętnego na system dwójkowy

 

Liczba naturalna n w systemie dwójkowym przyjmuje postać:

 

ci ... c1 c0       gdzie  ci   przyjmuje wartość 1 lub 0

 

Liczbę dziesiętną n oblicza się wg wzoru:

n = ci*2i +  ... + c1*21 + c0*20

Przykład:

Liczba 83 w systemie dwójkowym:
83 : 2  1
41 : 2  1
20 : 2  0
10 : 2  0
  5 : 2  1
  2 : 2  0
  1 : 2  1

83 10= 1010011NB

Liczba 21 w systemie dwójkowym:

 

21 : 2  1          c0

10 : 2  0          c1

  5 : 2  1          c2

  2 : 2  0          c3

  1 : 2  1          c4

  0 : 2  0          c5

 

2110 = 010101NB

 

 

Zera przed jedynką z lewej nie mają wpływu na wartość liczby

 

2.5 Naturalny kod binarny


System dwójkowy posiada specjalne znaczenie, ponieważ jest podstawą wszystkich obliczeń wykonywanych przez komputer.

Cechy charakterystyczne dwójkowego systemu pozycyjnego, to:

p = 2, zbiór cyfr c - {0,1}

Wartość liczby całkowitej w zapisie dwójkowym obliczamy według wzoru podstawowego lub poznanym wcześniej algorytmem Hornera

 


Obliczyć wartość liczby dwójkowej 110111(2) za pomocą wzoru potęgowego i algorytmu Hornera.

 

Wzór potęgowy.

 

p = 2, c - {0,1}

110111(2) = 1 x 20 + 1 x 21 + 1 x 22 + 0 x 23 + 1 x 24 + 1 x 2 5
110111(2) = 1 x 1 + 1 x 2 + 1 x 4 + 0 x 8 + 1 x 16 + 1 x 32
110111(2) = 1 + 2 + 4 + 16 + 32
110111(2) = 55(10)

 

Algorytm Hornera

 

w ¬ 0
w ¬ 1 + 0 x 2 = 1
w ¬ 1 + 1 x 2 = 3
w ¬ 0 + 3 x 2 = 6
w ¬ 1 + 6 x 2 = 13
w ¬ 1 + 13 x 2 = 27
w ¬ 1 + 27 x 2 = 55 (koniec, wyczerpano wszystkie cyfry)

110111(2) = 55(10)

 

2.5 System szesnastkowy

 

P=16 C= 0, 1, 2, ... 9, A, B, C, D, E, F

 

Przykłady zapisu liczb heksadecymalnych:

1116= 1* 161 + 1* 160 = 1710

C916= 12* 161 + 9* 160 = 20110

(4F)16= 4* 161 + 15* 160 = (79)10

 

Za pomocą liczb heksadecymalnych można w prosty sposób zapisywać długie liczby binarne.

Grupa 4 bitów może być zapisana za pomocą jednej cyfry heksadecymalnej zgodnie z następującą tabelą:

 

 

System D

System B

System H

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

10

1010

A

11

1011

B

12

1100

C

13

1101

D

14

1110

E

15

1111

F

 

Liczbę dwójkową dzielimy na grupy , każda po 4 bity począwszy od najmłodszego bitu np.:

1100110NB= 6616

Przekształcenie odwrotne: 3A816= 1110101000NB

Jeden bajt może być przedstawiony za pomocą dwóch liczb heksadecymalnych od 0 do FF.

FF16= 25510= 1111111116

 

2.6 Kod ZNAK-MODUŁ

W systemie tym stosujemy bardzo prostą metodę kodowania liczb ze znakiem. Najstarszy bit liczby jest bitem znaku. Reszta bitów określa wartość bezwzględną (moduł) liczby: Jeśli przyjmiemy do zapisu liczb format całkowity n-bitowy, to liczby w kodzie znak-moduł mają następującą postać:

cn-1

cn-2cn-3...c2c1c0

znak

moduł

Wartość n-bitowej, całkowitej liczby w dwójkowym kodzie znak-moduł obliczamy wg wzoru:

cn-1cn-2cn-3...c2c1c0 = (1 - 2 x cn-1) x

n-2

i=0

ci2i

 

Wyrażenie (1 - 2 x bit znaku) przyjmuje odpowiednio wartość 1, gdy bit znaku jest równy 0, a  -1, gdy bit znaku ma wartość 1, czyli określa liczbę ujemną. W dalszej części wzoru mamy obliczanie wartości pozostałych bitów, czyli modułu. Moduł jest przemnażany przez wyrażenie znakowe i w efekcie otrzymujemy wartość dodatnią lub ujemną w zależności od stanu bitu znaku.


n = 4 bity

0110(z-m) = (1 - 2 x 0) x (0 x 20 + 1 x 21 + 1 x 22)
0110(z-m) = (1 - 2 x 0) x (0 x 1 + 1 x 2 + 1 x 4)
0110(z-m) = 1 x ( 2 + 4)
0110(z-m) = 6(10)

1011(z-m) = (1 - 2 x 1) x (1 x 20 + 1 x 21 + 0 x 22)
1011(z-m) = (1 - 2 x 1) x (1 x 1 + 1 x 2 + 0 x 4)
1011(z-m) = -1 x (1 + 2)
1011(z-m) = -3(10)


 

Jeśli chcemy daną wartość przedstawić w dwójkowym kodzie znak-moduł, to najpierw znajdujemy przedstawienie dwójkowe modułu tej wartości, następnie uzupełniamy bity do zadanego formatu i dodajemy bit znaku 0 dla wartości dodatniej lub 1 dla ujemnej

2.7 Kod U2

Kod Uzupełnień do 2 (lub Uzupełnień do Podstawy), w skrócie U2. Budowa liczby w kodzie U2 jest podobna do kodu znak-moduł. Jednak teraz pozycja znakowa (najstarszy bit) posiada swoją wagę i uczestniczy w wartości liczby jak każda inna pozycja. Waga pozycji znakowej jest ujemna:

 

-2n-1
cn-1

2n-22n-3...222120
cn-2cn-3...c2c1c0

znak

moduł

 

Wartość n-bitowej liczby zapisanej w kodzie U2 obliczamy w standardowy sposób: sumując kolejne iloczyny cyfr przez wagi pozycji.

cn-1cn-2cn-3...c2c1c0 = cn-1(-2n-1) +

n-2

i=0

ci2i

Przykład


n = 4 bity

0110(U2) = 0 x (-23) + 0 x 20 + 1 x 21 + 1 x 22
0110(U2) = 0 x (-8) + 0 x 1 + 1 x 2 + 1 x 4
0110(U2) = 2 + 4
0110(U2) = 6(10)

1110(U2) = 1 x (-23) + 0 x 20 + 1 x 21 + 1 x 22
1110(U2) = 1 x (-8) + 0 x 1 + 1 x 2 + 1 x 4
1110(U2) = -8 + 2 + 4
1110(U2) = -2

 

3. Zadania i ćwiczenia

 

Zadanie 1

Wstawić do tablicy n-elementowej na pozycję k ciąg element o wartości m.

 

Zadanie 2

Wstawić do tablicy n-elementowej na pozycję k ciąg m elementów

 

Zadanie 3

Dana jest tablica a[] n zawierająca ciąg n elementów o wartościach nie mniejszych niż n. W tablicy wyzerowanej b[], zapisać 1 jeżeli dany element o wartości n występuje w tablicy a[].

 

Zadanie 4

Program zamieniający liczbę w systemie 10 na liczbę w dowolnym systemie liczenia

 

Zadanie 5

Program zamieniający liczbę z dowolnego systemu na liczbę w systemie 10 z wykorzystaniem wzoru potęgowego.

 

Zadanie 6

Program zamieniający liczbę z dowolnego systemu na liczbę w systemie 10 z wykorzystaniem algorytmu Hornera.

 

Zadanie 7

Program zapisujący liczbę(system 10) w kodzie znak-moduł.

 

 

Zadanie dodatkowe (1 pkt)

 

Właściwości zbioru

 

Dane:             Liczba elementów w zbiorze – n;

                        Kolejne wartości rzeczywiste  zmiennej a;

Wyniki:           Minimum i maksimum zbioru – min. max;

                        Rozpiętość zbioru – rz;

                        Średnią zbioru – srednia;

                        Częstość każdego elementu;

                        Modalną zbioru (miarę centralności).

 

Objaśnienia:

ð      Częstość elementu zbioru – liczba powtórzeń ;

ð      Maksimum zbioru – największy element;

ð      Rozpiętość zbioru – różnica między maksimum i minimum;

ð      Średnia zbioru – Średnia arytmetyczna elementów zbioru;

ð      Częstość – liczba powtórzeń elementu w zbiorze;

ð      Modalna – element o największej częstości.

 

 

Projekt

 

1) Dzielenie dwóch liczb zapisanych jako ciąg znaków, realizowane jako odejmowanie.