Algorytm sortowania przez scalanie
Algorytm Hornera
Systemy liczbowe
Zapis dziesiętny, dwójkowy, szesnastkowy
Kod znak-moduł
Kod U2
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.
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 |
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
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ę
·
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
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)
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
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 |
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
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 |
2n-22n-3...222120 |
|
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 |
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
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.
