Ćwiczenie IX

 

1. Pojęcia

            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

2. Wiadomości

 

2.1 Pojęcie struktury kopca

            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

 

Sortowanie

Po utworzeniu kopca następuje właściwe sortowanie. Polega ono na usunięciu wierzchołka kopca, zwierającego element maksymalny (minimalny), a następnie wstawieniu w jego miejsce elementu z końca kopca i odtworzenie porządku kopcowego. W zwolnione w ten sposób miejsce, zaraz za końcem zmniejszonego kopca wstawia się usunięty element maksymalny. Operacje te powtarza się aż do wyczerpania elementów w kopcu. Wygląd tablicy można tu schematycznie przedstawić następująco:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2 Zamiana reprezentacji liczb w systemach 2, 4, 8 i 16.

 

 

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

 

 

2.2 Zamiana liczb na ułamkowy NKB

 

 

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

 

2.2 Dodawanie i odejmowanie liczb ułamkowych U2

 

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

 

2.3 Mnożenie liczb cyfrowe

 

 

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

 

 

3. Zadania i ćwiczenia

 

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

 

 

Przykłady

 

 

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