Systemy liczbowe – Część 2. Algorytm zamiany liczb między systemami

Systemy liczbowe – Część 2. Algorytm zamiany liczb między systemami

1. Pseudokod

Spróbujmy teraz napisać odpowiedni program zamieniający liczby z dowolnego systemu liczbowego na dziesiętny i odwrotnie. Na początku opracujmy algorytm w pseudokodzie. Pseudokod nie jest istniejącym językiem programowania. Jest to język zbliżony do języka naturalnego, jak najbardziej zwięzły i musi być czytelny dla czytającego. W naszym przypadku będziemy używali polskich wyrazów, ale bez polskich liter.

Nie będziemy się też przejmować typem zmiennych – założymy że zmienne dla każdej operacji mają odpowiedni typ. Czym jest typ zmiennej? Otóż w zależności od potrzeb zmienne mogą być typu całkowitego (czyli mogą mieć przypisane wyłącznie liczby całkowite), rzeczywistego (mogą przechowywać tylko liczby rzeczywiste), czy tekstowego (mogą mieć przypisany dowolny tekst a każdy znak będzie traktowany wyłącznie jako znak, nawet jeśli będzie jakąś cyfrą, co oznacza, że nie można by było na zmiennej tekstowej mającej przypisane same cyfry dokonywać jakiejś operacji matematycznej). Ponieważ w tym artykule będziemy pisać w pseudokodzie, nie będziemy musieli zajmować się problemami typowymi dla danego języka programowania, jak wspomniany wyżej typ zmiennej i zmiana typu w zależności od potrzeb. Założymy też, że potrzebne instrukcje są już wbudowane – nie będziemy musieli ich tworzyć na nasze potrzeby.

2. Zamiana liczb z systemu dwójkowego na dziesiętny.

Z pierwszej części Matematyka i programowanie – systemy liczbowe – Część 1. Teoria wiemy, że liczba dwójkowa składa się tylko z dwóch cyfr: 0 i 1. I odpowiednich potęg liczby 2. Na przykład liczba dziesiętna 10 w systemie dwójkowym zostanie zapisana jako 1010(2). Czyli:

1010(2) = 1 * 23 +  0 * 22 + 1 * 21 + 0 * 20= 8 + 0 + 2 + 0 = 10(10)

Mamy więc liczbę dwójkową jako ciąg znaków, w tym wypadku cyfr. W żadnym razie nie możemy ot tak po prostu podać jej dziesiętnej reprezentacji. Musimy ją policzyć według powyższego schematu. I właśnie ten schemat będzie nam pomocny do napisani algorytmu zamiany liczby dwójkowej na dziesiętną. Mamy więc zmienną:

liczba_2 = „1010”

Zastosowałem cudzysłów, by wiadomo było, że nie jest to zwykła liczba dziesiętna 1010, lecz ciąg tekstowy z kolejnymi znakami: 1,0,1,0. Jest to tablica znaków, a więc:

liczba_2[0] = „1”

liczba_2[1] = „0”

liczba_2[2] = „1”

liczba_2[3] = „0”

Należy pamiętać, że indeksy tablicowe zaczynają się od 0. I zawsze od lewej. W pseudokodzie przyjąłem konwencję z języków programowania. Każdy łańcuch znakowy to tablica, której indeks zerowy wskazuje na pierwszy znak. Na przykład jeżeli zmienna tekst ma wartość

tekst = „To jest tekst”;

oznacza to, że tablica ma 13 elementów typu znakowego:

tekst[0] = „T”

tekst[1] = „o”

tekst[2] = ” ”   (spacja)

tekst[3] = „j”

tekst[4] = „e”

tekst[5] = „s”

tekst[6] = „t”

tekst[7] = ” ” (spacja)

tekst[8] = „t”

tekst[9] = „e”

tekst[10] = „k”

tekst[11] = „s”

tekst[12] = „t”

Spacje też traktowane są jako znaki, należy o tym pamiętać. Jeżeli teraz do tablicy dodalibyśmy jeszcze jeden znak, na przykład kropkę, to spowodowałoby zwiększenie rozmiaru tablicy do 14 znaków, a nowy znak miałby indeks 13:

tekst[13] = „.”

Cały łańcuch znakowy miałby wartość:

tekst = „To jest tekst.”;

W jaki sposób w powyższym zapisie tablicowym przyporządkować indeksy tablicowe poszczególnym potęgom liczby 2?

Spójrzmy na poniższą tabelę:

Należy zatem zrobić:

  1. obliczyć ilość cyfr danej liczby dwójkowej: ilosc_cyfr = liczba_2.dlugosc (parametr dlugosc oznacza ilość znaków w tekście, w naszym wypadku: 4)
  2. brać po kolei każdą cyfrę, mnożąc ją przez 2 do potęgi ((ilosc_cyfr-1) – indeks), gdzie indeks – numer danej cyfry w ciągu tekstowym [u nas dla pierwszej cyfry (liczba_2[0] = 1): 1 * 2 (ilosc_cyfr – 1) – 0 ]
  3. zsumować wszystkie wyniki z punktu 2

W wyniki otrzymamy:

liczba_2[0] = „1” => 1 * 2(4-1) – 0 = 1 * 23 = 8

liczba_2[1] = „0” => 0 * 2(4-1) – 1 = 0 * 22 = 0

liczba_2[2] = „1” => 1 * 2(4-1) – 2 = 1 * 22 = 2

liczba_2[3] = „0” => 0 * 2(4-1) – 3 = 0 * 20 = 0

Po zsumowaniu otrzymujemy liczbę dziesiętną 10.

W pseudokodzie początek i koniec jakiegoś bloku będziemy oznaczali nawiasami klamrowymi. Ułatwi nam to czytanie kodu.

Teraz pora by napisać pierwszy algorytm. Będzie to funkcja z jednym argumentem – liczbą w systemie dwójkowym, założenie: zmienna liczba jest stringiem.

Średniki oznaczają koniec jakiejś instrukcji. Można się bez nich obejść, jako że w zasadzie nowe instrukcje piszemy w następnych linijkach.

Mamy już funkcję, która zamienia liczbę dwójkową na liczbę dziesiętną. Zakładamy oczywiście, że zmienna liczba jest podana poprawnie, to znaczy przy użyciu wyłącznie znaków 1 i 0. Sprawdzanie poprawności danych wprowadzimy później. Teraz skupmy się na meritum, to znaczy działaniu funkcji.

Przyjmijmy, że funkcja została wywołana z argumentem „1010”, to znaczy w miejsce zmiennej liczba wpisujemy wartość „1010”:

A więc mamy teraz takie oto zmienne:

linijka 1 liczba = „1010” (argument funkcji)
linijka 2liczba_10 = 0 (wartość początkowa zmiennej)
linijka 3mamy pętlę w której zmiennej na starcie przypisujemy wartość 0, w każdym obrocie pętli zwiększamy jej wartość o 1 i wykonywanie pętli ma trwać dopóki wartość zmiennej i będzie mniejsza od liczba.dlugosc.
linijka 4po prawej stronie znaku przypisania stara wartość zmiennej liczba_10

 

obliczanie wartości dziesiętnej liczby liczba[i] i dodanie do starej wartości zmiennej liczba_10 i przypisanie wyniku do zmiennej liczba_10

linijka 6funkcja kończy działanie i zwraca wynik zapisany w zmiennej liczba_10

Zatrzymajmy się na linijce 4. Mamy tak taki kod:

liczba_10 = liczba_10 + liczba[i] * 2 ^ (ilosc_cyfr – 1 – i)

Prześledźmy teraz zmiany dla kolejnych wartości zmiennej i w pętli:

Wynik: 10. Czyli liczba dwójkowa 1010(2) to 10(10).

3. Zamiana liczb z systemu dowolnego na dziesiętny.

Teraz spróbujmy napisać kod zamieniający liczbę w dowolnym systemie liczbowym na dziesiętny.  Funkcję z listingu 1 zmienimy tak, by można było zamienić liczbę z dowolnego systemu liczbowego na liczbę w systemie dziesiętnym. Na listingu mamy nieco zmienioną funkcję.

Kod jak by się rozrósł. W rzeczywistości zmiany są niewielkie. Zobaczmy:

linijki 3-10wprowadziliśmy zmienną cyfry_hex, która jest tablicą zamieniającą cyfry systemu szesnastkowego na ich wartość dziesiętną
linijka 12sprawdzamy czy liczba jest podana w systemie szesnastkowym oraz czy cyfra liczba[i] jest z zakresu od A do F, jeśli tak, to  liczba[i] przypisujemy odpowiednią wartość dziesiętną, która jest użyta w linijce 15
linijka 15wprowadziliśmy funkcję calk(liczba), która liczbę z postaci tekstowej zamienia na liczbę typu całkowitego

Dlaczego było nam to potrzebne? Ponieważ zakładamy, że nasz język pseudokodu „zna” tylko liczby dziesiętne. Działania matematyczne właśnie na tych liczbach są przeprowadzane (z punktu widzenia programisty). Tak więc liczbowy typ zmiennej, na przykład typ całkowity oznacza, że zmiennej przypisujemy całkowitą liczbę dziesiętną. Na przykład:

jakas_liczba = 345

automatycznie oznacza, że zmiennej jakas_liczba przypisujemy dziesiętną liczbę 345. Jeśli chcielibyśmy, aby była to liczba ósemkowa, musielibyśmy przypisać zmiennej wartość „345” – jako tekst zawierający właśnie te cyfry. Do jakichkolwiek obliczeń musielibyśmy zamienić ową liczbę na liczbę dziesiętną, tak by była typu całkowitego. Do tego właśnie służy nasza funkcja zamien_SYSTEM_na10.

Oczywiście w tym przypadku w linijce 15 liczba[i] musi zmienić wartość tekstową cyfry na liczbę. Możemy przyjąć w pseudokodzie, ze dzieje się tak automatycznie, ale w językach programowania tak nie jest. Wprowadźmy więc funkcję calkowita(liczba), która zwraca wartość całkowitą liczby liczba. Na przykład:

calkowita(„123”)

da nam liczbę dziesiętną 123. Niestety, wartość argumentu traktowana jest jako tekstowy zapis liczby dziesiętnej. Tak więc, gdybyśmy uznali, że „123” jest podana w systemie ósemkowym, to i tak funkcja calk() będzie traktowała ją jako tekstową reprezentację liczby dziesiętnej. Taki sam efekt uzyskamy, gdybyśmy podali w argumencie nie tekst, ale liczbę dziesiętną:

calkowita(123)

Dla naszych potrzeb wystarczy, że funkcja calk() zamienia tylko cyfry (a nie całe liczby) na postać dziesiętną. Ponieważ ta funkcja nie „zna” cyfr innych niż te z systemu dziesiętnego, musieliśmy wcześniej wprowadzić zmienną cyfry_hex dla liczb zapisanych w systemie szesnastkowym.

Spróbujmy teraz przeanalizować działanie funkcji dla liczby szesnastkowej „AA”. Wywołamy funkcję z argumentami:

zamien_SYSTEM_na_10(„AA”, 16)

Przeanalizujmy linijki od 11 do 16 (blok pętli).

Ostatecznie mamy:

AA(16) = 170(10)

Co jest wynikiem prawidłowym.

3. Zamiana liczb z systemu dowolnego na dziesiętny – obsługa błędów.

Można uznać, że mamy gotową funkcję zamieniającą liczbę w dowolnym systemie liczbowym na liczbę w systemie dziesiętnym. Brakuje jeszcze sprawdzenia czy wprowadzana liczba rzeczywiście jest zgodna z podanym systemem liczbowym. Może się okazać, że jakiś dowcipniś postanowi sprawdzić, co się stanie, kiedy wywołamy funkcję z takimi argumentami:

zamien_SYSTEM_na_10(„AA”, 2)

Widzimy, że liczba podana jest w systemie szesnastkowym, zaś drugi argument wskazuje że liczba podana jest w systemie dwójkowym. Mamy sprzeczność argumentów. W takim wypadku funkcja nie zadziała prawidłowo.

W linijce 12 mamy warunek, że jeżeli zmienna system jest równa 16 i liczba[i] jest znakiem z zakresu <A-F>, to wtedy w linijce 13 zmiennej liczba[i] przypisujemy dziesiętną wartość odpowiadającą znakowi z systemu szesnastkowego. Jednakże w naszym przypadku zmienna system ma wartość 2 a więc warunek z linijki 12 jest fałszywy i kod z linijki 13 się nie wykona, wobec czego zmiennej liczba[i] w dalszym ciągu będzie przypisany znak „A”.

Ponieważ zmienna liczba[i] ma wartość tekstową „A”, to kod zatrzyma się na linijce 15, gdyż funkcja calk(„A”) zatrzyma cały kod, wskazując na błąd argumentu.

Innego rodzaju błąd pojawi się, gdy wywołamy funkcję następująco:

zamien_SYSTEM_na_10(„13”, 2)

Nie wyskoczy nam błąd, gdyż wszelkie wyliczenia będą możliwe do przeprowadzenia. Tyle tylko, ze otrzymamy błędny wynik. Jaki? To już zależy. Jeżeli uznamy, że liczba „13” miała być zapisana w systemie 10, to po prostu powinniśmy otrzymać w wyniku 13. Jeżeli uznalibyśmy, że liczba miałaby być zapisana w systemie ósemkowym, to powinniśmy otrzymać w wyniku 11, jeżeli miałaby to być liczba w systemie szesnastkowym, to w wyniku otrzymamy 19. Czyli:

13(10) = 13(10)

13(8) = 11(10)

13(16) = 19(10)

Mamy jednak pewność, że liczby 13(2) nie ma, gdyż jedynymi cyframi w systemie dwójkowym są 1 i 0. Algorytm jednak o tym „nie wie” i przeprowadzi stosowne obliczenia. Przeanalizujmy:

Otrzymaliśmy w wyniku liczbę dziesiętną 5. Z matematycznego punktu widzenia operacje są możliwe do przeprowadzenia i nie powstanie żaden błąd w rodzaju niezgodności typów danych. W takich przypadkach możemy się nawet nie zorientować, że coś źle działa, o ile nie przetestujemy dokładnie kodu dla różnych zmiennych. Musimy zatem zabezpieczyć się przed tego rodzaju błędami.

Czego musimy dopilnować? Po pierwsze, musimy dopilnować, by zmienna liczba rzeczywiście zawierała jakąś liczbę (musi zawierać tylko cyfry od 0 do 9 i ewentualnie dodatkowo  litery od A do F, jeśli jest zapisana w systemie szesnastkowym). Po drugie, zmienna system musi zawierać podstawę jakiegoś systemu liczbowego, czyli sama być liczbą – w naszym przypadku dziesiętną. Po trzecie, trzeba dopilnować, by obie zmienne były ze sobą kompatybilne – zmienna liczba musi rzeczywiście być liczbą mogącą być przedstawioną w systemie liczbowym określonym przez zmienną system. Przyjmijmy, że będziemy rozpatrywali tylko cztery systemy liczbowe: dwójkowy, ósemkowy, dziesiętny, szesnastkowy. Można brać pod uwagę dowolną podstawę systemu liczbowego, byleby była to liczba większa od 1. Jednak w praktyce używa się wyżej wymienionych.

Jak to zrobić? Przyjrzyjmy się listingowi 3.

Przeanalizujmy. Myślę, że linijki 3-5 są zrozumiałe. Zmienna system musi być liczbą i to liczbą konkretną: 2 lub 8 lub 10 lub 16. Jeśli nie, funkcja kończy działanie i zwraca komunikat „System liczbowy musi być liczbą: 2, 8, 10, 16”.

Jeśli chodzi o linijki 7-18, być może są mniej zrozumiałe. Użyto w nich tak zwanych wyrażeń regularnych, z pomocą których sprawdzamy, czy tekst zawiera tylko znaki podane we wzorcu.

W linijce 9 podano wzorzec, któremu mają odpowiadać liczby w systemach mniejszych od 11, przyjmują one cyfry o wartościach od 0 do system-1 ( wzorzec = /^[0-(system-1)]+$/ oznacza, że liczby w powyższych systemach muszą zawierać tylko cyfry z zakresu od 0 do wartości: system -1). Czyli w naszym przypadku dotyczy to liczb w systemie dwójkowym, ósemkowym, dziesiętnym.

Natomiast w linijce 12 podano wzorzec dla liczb w systemie szesnastkowym (wzorzec = /^[0-9ABCDEF]+$/ oznacza że liczby w systemie szesnastkowym mogą zawierać tylko cyfry z zakresu od 0 do 9 oraz litery A,B,C,D,E,F).

W linijce 16 sprawdzamy, czy liczba odpowiada podanemu wzorcowi. Jeśli nie, funkcja kończy działanie, zwracając komunikat „Liczba podana niezgodnie z przyjętym systemem liczbowym”.

4. Zamiana liczb z systemu dziesiętnego na dowolny.

Zajmiemy się teraz zamianą liczb dziesiętnych na inne systemy liczbowe. Przypomnijmy sobie z części teoretycznej w jaki sposób to robiliśmy.

Weźmy pod uwagę liczbę dziesiętna 12345 i spróbujmy znaleźć jej odpowiednik w systemie dwójkowym.

Liczbę dzielimy przez 2 i otrzymujemy całkowity iloraz oraz resztę z dzielenia. Operację powtarzamy, tym razem dzieląc otrzymany w poprzednim kroku iloraz i znowu otrzymujemy całkowity iloraz oraz resztę z dzielenia. Powtarzamy czynność dopóki iloraz jest różny od zera.

Liczbę odczytujemy zaczynając od ostatniej reszty. Jest to liczba: 11000000111001(2).

Jak przedstawić powyższe operacje za pomocą pseudokodu? Napiszemy nową funkcję zamien_10_na_SYSTEM(). Wykorzystamy część kodu z poprzedniej funkcji.

W linijce 30 użyliśmy funkcji zamieniającej każdą zmienną na postać tekstową czyli string:

reszta.jakoString();

Uznajmy, że taka funkcja w naszym pseudokodzie istnieje. W różnych językach programowania są funkcje zamieniające różne zmienne na stringi. Nie muszą to być funkcje wbudowane w obiekty (zmienne), jak w naszym przykładzie. Jeżeli sama zmienna będzie stringiem, to funkcja zwróci nam po prostu jej wartość.

Natomiast w linijce 32 użyliśmy funkcji odrzucającej cześć ułamkową z liczby rzeczywistej:

zaokraglaj_w_dol(liczba / system)

Gdybyśmy jej nie użyli, otrzymalibyśmy liczbę rzeczywistą, co nie jest naszą intencją.

Sprawdźmy jak działa funkcja wywołana jak poniżej:

funkcja zamien_10_na_SYSTEM(2737, 16)

W wyniku powinniśmy otrzymać AB1. Czyli:

2737(10) = AB1(16)

Sprawdźmy czy rzeczywiście tak otrzymamy.

Otrzymaliśmy prawidłowy wynik.

A co z sytuacją, kiedy liczba wejściowa jest równa 0? Czyli mamy wywołanie funkcji:

zamien_10_na_SYSTEM(0,2)

Sprawa się komplikuje, gdyż w linijce 23 mamy pętlę, która „działa” wtedy, kiedy zmienna liczba jest większa od 0. Czyli kiedy zmienna liczba na wejściu ma wartość 0, pętla nie wykona się ani razu. Zresztą, nie ma po co, wiadomo bowiem, że w każdym systemie liczbowym wartość 0 jest taka sama i wynosi…  właśnie 0. Jak temu zaradzić? Należy na początku funkcji sprawdzić, czy zmienna liczba jest zerem. Jeśli tak, funkcja ma zwrócić wartość 0. Czyli teraz nasza funkcja po uwzględnieniu powyższego wygląda tak:

W następnej części pokażemy pełny kod w JavaScript.

Dodaj komentarz

Close Menu