Pojęcie struktury kopca
Zamiana reprezentacji liczb w systemach 2, 4, 8 i 16.
Reprezentacja liczb ułamkowych w NKB
Zamiana liczby na postać ułamkową NKB
Mnożenie liczb (NKB) cyfrowe
Kopiec jest to tablica danych, która da się przedstawić graficznie w postaci drzewa binarnego. Każdy węzeł tego drzewa odpowiada jednemu elementowi tablicy (numery węzłów na rysunku oznaczone są liczbami po lewej stronie węzła). Tak więc dziesiąty element sortowanej tablicy nazwiemy węzłem numer 10. Dla każdego elementu możemy łatwo obliczyć jego "rodzica" (czyli na rysunku jest to element "wyższy" od danego i z nim związany), oraz jego "liście": prawy i lewy. Numer rodzica jest obliczany według wzoru: numer rodzica = bieżący element / 2 (dzielenie bez reszty). Bieżący element jest elementem, dla którego liczymy numer rodzica. Tak więc rodzicem dla węzła 5 jest węzeł 2, gdyż 5/2=2. Tylko dla jednego węzła nie możemy policzyć rodzica: dla węzła pierwszego.
Numer lewego liścia, jak można zauważyć spoglądając na rysunek jest równie łatwy do obliczenia: lewy = bieżący x 2.
Ostatni wzór jest oczywisty: prawy = bieżący x 2 + 1.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 23 | 18 | 7 | 16 | 9 | 6 | 5 | 1 | 13 | 3 |
W kopcu pierwszy węzeł jest elementem największym. Największy węzeł powinien się znaleźć na końcu posortowanej tablicy. Zamieniamy zatem ostatni węzeł z pierwszym, węzeł ostatni "odcinamy" od kopca (poprzez zmniejszenie zmiennej rozmiar) i wywołujemy procedurę kopiec w dół dla węzła nr 1. W efekcie w tablicy będziemy mieli nieco mniejszy kopiec, a ostatni element tablicy (nie należący już do kopca) będzie miał wartość najwyższą z wszystkich elementów tablicy. Pokazane jest to na rysunku obok. Część pierwsza rysunku to nasz kopiec. Niżej widzimy element 1 zamieniony z elementem ostatnim oraz "obcięcie" kopca, poprzez zmniejszenie wartości zmiennej rozmiar. Trzecia część rysunku to sytuacja po uruchomieniu procedury kopiec w dół.
Zamiana węzła pierwszego z ostatnim, "obcięcie" kopca, kopiec w dół (1). Kopiec znowu zmalał, a dwa ostatnie elementy są już posortowane. Jeżeli czynność powtórzymy dostateczną ilość razy, kopiec zupełnie "zniknie" a tablica będzie już posortowana
Zamiana liczb między systemami 2, 4, 8 i 16 może zostać wykonana bez konieczności zamiany całej liczby, poprzez podział poszczególnych grup cyfr na mniejsze (większe):
(202)10 = (11001010)2 = (11 00 10 10)2 = (3 0 2 2)4
(202)10 = (11001010)2 = (011 001 010)2 = (2 1 2)8
(202)10 = (11001010)2 = (1100 1010)2 = (C A)16
Zamianę można wykonywać również z pozostałych systemów:
(AB)16 = (1010 1011)2 = (171)10
1) Algorytm dotyczący jedynie części ułamkowej
Mnożenie liczby: Podstawa^Dokładność
Zwykły algorytm Hornera
Wynik zapisujemy w odwrotnej kolejności
Przykład:
0.125
0.125 * 2 | 0
0.250 * 2 | 0
0.5 *2 | 1
(0.125)10 = (0.001)2
Przykład:
0.625
0.625 * 2 | 1
0.250 * 2 | 0
0.500 * 2 | 1
(0.625)10 = (0.101)2
2) Uogólniony algorytm Hornera
I)
Liczbę 3.75 zamienić na postać ułamkową w NKB, dokładność 2 cyfry po przecinku
3.75 * 2^2 = 15.00 – część ułamkowa zostaje pominięta
Zamiana w zwykły sposób:
15 = 1111
Przecinek na pozycję drugą: 11,11
II)
10.875
Na trzech bitach
10.875 * 8 = 87
(87)10 = (1010,111)2
1010,111
Zamiana na system dowolny – np. ósemkowy
Obliczyć przy pomocy algorytmu Hornera wartość liczby 237,745 zapisanej w systemie pozycyjnym o podstawie p=8.
w 0
w 2
+ 0 x 8 = 2
w 3
+ 2 x 8 = 19
w 7
+ 19 x 8 = 159
w 7
+ 159 x 8 = 1279 (od tego momentu występują cyfry części ułamkowej)|
w 4
+ 1279 x 8 = 10236
w 5
+ 10236 x 8 = 81893 (ostatnia cyfra, kończymy)
w 81893 x 1/512 = 159 485/512 =
159,947265625
Podajemy liczby w systemie U2
W przypadku podania liczby w zapisie 10, należy przejść na zapis w U2
Odejmowanie
Polega na dodawaniu liczby przeciwnej
1.75 = 0001.1100
2.25 = 0010.0100
1.75 + 2.25 = 00100.0000
Algorytm mnożenia cyfrowego liczb:
Start
RH <= 0
M <= Mnożnik
RL <= Mnożna
STER <= N
R0 = 1
RL <= RL + M
Przesunięcie w lewo
N = N – 1
N = 0
STOP
0101
0110
0000
0101
0101
0000
=============================
00011110
Rejestr RH RL M
0 0 0 0 0 1 1 0 0 1 0 1
0 0 0 0
======
0 0 0 0 0 1 1 0
0 0 0 0 0 0 1 1
0 1 0 1
======
0 1 0 1 0 0 1 1
0 0 1 0 1 0 0 1
0 1 0 1
======
0 1 1 1 1 0 0 1
0 0 1 1 1 1 0 0
0 0 0 0
======
0 0 0 1 1 1 1 0
Zadanie 1
Podane liczby w systemie dziesiętnym zamienić na system dwójkowy, a następnie na system czwórkowy, ósemkowy i szesnastkowy (wykorzystując metodę bezpośredniego przeliczania):
(234)10 = (?)2 = (?)4 = (?)8 = (?)16
(164)10 = (?)2 = (?)4 = (?)8 = (?)16
(213)10 = (?)2 = (?)4 = (?)8 = (?)16
(100)10 = (?)2 = (?)4 = (?)8 = (?)16
Zadanie 2
Napisać program w Pascalu zamieniający pobraną liczbę ułamkową na liczbę w NKB
Zadanie 3
Zakoduj używając algorytmu Hornera:
1. liczbę 11.2222 w systemie trójkowym
2. liczbę 10.5 w systemie piątkowym
3. liczbę 0.0016 w systemie szesnastkowym
4. liczbę 2048.128 w systemie dziewiątkowym
Przelicz jedną z tych liczb z powrotem na system dziesiętny i sprawdź, jak duża niedokładność powstała w związku z obcięciem jej zakodowanej postaci do skończonej ilości cyfr po przecinku.
Zadanie 4
Dodać następujące liczby w U2 (na 8 bitach, arytmetyka 8 / 0)
(-100) + (-10)
(-67) + (-50)
(-101) + (90)
Zadanie 5
Wykonać obliczenia (operacje dodawania) w U2, (arytmetyka 4 / 4)
1.5 + 4.75
0.125 + 3.625
1.625 – 2.125
-80.5 + (-36.5)
Zadanie 6
Wykonać obliczenia (arytmetyka 8 / 4)
(-107.25)= (1110,1100,1100)U2
( 55.75) = (0011,0111,1100)U2
Zadanie 7
Wykorzystując algorytm mnożenia cyfrowego przemnożyć:
5 * 7
1) 8/4
(-80.5) = (1010,1111,1000)U2
(-36.5) = (1101,1011,1000)U2
======================
(1000,1011,0000)U2 = (-117.0)
2) 8/4
(-107.25)=(1110,1100,1100)U2
(55.75) = (0011,0111,1100)U2
======================
(0010,0100,1000)U2 = 36.5
3)
(1.75) = (0001,1100)U2
(-2.5)= (1101,1000)U2
==================
(1111,0100)U2 = -0.75
4)
(-3.75) = (1100,01000)U2
(-1.25)= (1110,1100)U2
===================
(1011,00)U2 = (5.0)U2