W ostatnim poście pokazałem, jak można stosować cechę podzielności, ale nie wskazałem szybkiego sposobu przechodzenia z systemu na system. Za to użyłem takiego przy konwertowaniu z systemu dziesiątkowego na ósemkowy.
Zatem dodatek: szybki sposób konwersji systemów pozycyjnych.
Zanim go jednak przedstawię, oto różnica między liczbą a cyfrą.
CYFRA danego systemu liczbowego to liczba mieszcząca się między 0 włącznie oraz podstawą systemu liczbowego p, czyli w przedziale [0, p). Stanowi zarazem podstawowy składnik konstrukcji liczb. Dla małych podstaw cyfry mają własne symbole graficzne.
LICZBA [w systemie pozycyjnym] to [uporządkowany] ciąg cyfr a_n .. a_1 a_0.
W algorytmie poniższym cyfry są traktowane jako liczby, oraz w czasie początkowych przekształceń ignorujemy nałożone nań ograniczenia na wielkość.
Mając liczbę a_n...a_0 w systemie p, chcemy ją zapisać w systemie o podstawie p+r (p+r>1), stosujemy oparty na schemacie Hornera zapisu liczb
(...(a_n*p+a_{n-1})...)*p+a_0
następujący algorytm:
inicjacja: sprawdzamy przyrost r, załóżmy ze jest r>0 Bierzemy a_n, pozostałe cyfry czekają w kolejce [a_{n-1} , ... , a_0]
1) pobieramy cyfrę a_j z kolejki;
2) każdą cyfrę a_i (zaczynając od i=j, zwiększając do i=n ) modyfikujemy do liczby a_i := a_i - r*a_{i+1}, kiedy nie ma wartości i+1, traktujemy ją jako 0;
3) powstałe liczby sprowadzamy do cyfr dodając t razy (p+r) - pożyczamy od cyfr bardziej znaczących, aby liczba stojąca na miejscu cyfry była w odpowiednim przedziale;
4) poprzedzającą cyfrę a_{i+1} zmniejszamy o znalezione w 3) t;
powtarzamy 3) 4) tak długo, aż liczba będzie się składała tylko z prawidłowych w danym systemie cyfr;
5) kiedy kolejka cyfr jest pusta, uzyskujemy postać liczby w systemie (p+r), w przeciwnym przypadku wracamy do 1)
Na zakończenie modyfikujemy aktualną krotność cyfr, gdyż wartość ta może się zmienić.
Kiedy r jest dodatnie, w 2) dodajemy zamiast odejmować, zaś liczbę sprowadzamy do cyfry przez przekazywanie nadmiarów (p+r) cyfrom bardziej znaczącym.
Sposób nie jest tak szybki jak konwersje między systemami o podstawach będących potęgami jednej liczby a, w których liczbę zapisujemy przy podstawie a, a następnie cyfra powstaje z paczki odpowiedniej długości, np. konwersja z systemu o podstawie 27 na system o podstawie 9 przez system o podstawie 3:
22 2 4_{27} = 211 002 011_3 = 2 11 00 20 11_3 = 24064_9,
ale i tak znacznie szybszy niż stosowanie definicji systemów.
Przykład: przekonwertujemy szesnastkowe 0xBACA na system dziesiętny.
cyfry początkowe: [ 0xB=11, 0xA=10, 0xC=12, 0xA=10]
Początek to lista 11, mamy przyrost 10-16=-6, czyli do poszczególnych cyfr będziemy dodawać iloczyny 6
zaczynamy pierwszą iterację:
11 10+6*11
11 76
na pozycji jedności mamy liczbę! 76, którą należy zmniejszyć, aby na powrót stała się cyfrą systemu, tym razem dziesiątkowego
(11+t) (76-t*10) t=7
18 6
teraz cyfra dziesiątek jest za duża. Przenosimy nadmiar tworząc następną cyfrę, cyfrę setek.
1 8 6
Dla sprawdzenia, 11*16+10 = 186 = 1*10^2 + 8*10 + 6,
Kolejna iteracja, dołączamy cyfrę 0xC=12
1 8 6 12
1[+0] 8+6*1 6+6*8 12+6*6
1 14 54 48
przenosimy nadmiary (od razu wynik) (11*16+10)*16+12 = 2988
2 9 8 8
Ostatnia cyfra, czyli ostatnia iteracja
2 9 8 8 10
2[+0] 9+6*2 8+6*9 8+6*8 10+6*8
2 21 62 56 58
Przenosimy nadmiary
4 7 8 1 8
Zatem szesnastkowe 0xBACA to dziesiętne 47818.
W drugą stronę podobnie, lecz mamy 5 iteracji, przyrost 6. Pierwsza jest postaci
4[-0] 7-6*4
4 -17
naprawa polega na dodawaniu docelowej podstawy 16, czyli
4-2 -17+2*16
2 15
Kolejna iteracja
2 15 8
2 15-6*2 8-6*15
2 3 -82
1 13 14
Kolejna iteracja
1 13 14 1
1 13-6*1 14-6*13 1-6*14
1 7 -64 -83
1 2 10 13
Ostatnia iteracja
1 2 10 13 8
1 2-6*1 10-6*2 13-6*10 8-6*13
1 -4 -2 -47 -70
0 11 10 12 10
Ostatecznie przekształcamy te szesnastkowe cyfry na liczbę 0xBACA.
Brak komentarzy:
Prześlij komentarz