Konwersja ułamków między systemami

Szerzej o systemie pozycyjnym

Ułamki możemy zapisać w dowolnym systemie. Zasada zapisu jest identyczna z dotychczasowymi zasadami systemu pozycyjnego. Spójrzmy na przykład w systemie dziesiętnym:

10.25 = 1·10 + 0·10⁰ + 2·10^-1 + 5·10^-2 = 10 + 0 + 0.2 + 0.05

Przy rozpisywaniu warto pamiętać, że jedność zawsze ma bazę podniesioną do potęgi 0 (czyli mnożnik 1). "Idąc" w lewo zwiększamy potęgę podstawy, a "idąc" w prawo zmniejszamy. Każdy jeden krok to odpowiednia zmiana o 1.

Systemu dziesiętny na dowolny

Podczas przeliczania części dodatniej nie powinno być problemu, więc zajmijmy się częścią ułamkową. Należy pamiętać, że niektórych liczba nie da się łatwo przedstawić w innym systemie, dlatego czasem będzie trzeba przyjąć swojego rodzaju precyzje, która pozwoli na uzyskanie przybliżenia. Algorytm przeliczania części ułamkowej wygląda tak:

1. Mnożymy część ułamkową przez bazę
2. Część całkowitą dopisujemy na koniec dotychczasowego zapisu
3. Wracamy do punktu (1.) i za część ułamkową przyjmujemy ułamek z punktu (2.)

Weźmy przykładowo ułamek 0.375, który przeliczymy na system binarny:

Kończymy obliczenia, ponieważ część ułamkowa wynosi już 0. Odczytujemy wynik, że 0.375₁₀ = 0.011₂.

Odwołując się do uwagi do precyzji - sprawdźmy teraz przeliczanie ułamka 0.1:

Przerywamy obliczenia i analizujemy tabelkę. Łatwo zauważyć, że podążając ślepo za algorytmem nigdy nie skończymy wypisywać cyfr po przecinku, ponieważ będziemy w kółko wypisywać wyniki z kroków (2.) - (5.). Z matematycznego punktu widzenia możemy zapisać to jako: 0.0(0011). Sposobem na rozwiązanie tego problemu jest ustalenie precyzji. Precyzja określa ile cyfr po przecinku chcemy wypisać. Załóżmy, że chcemy wypisać przeliczenie 0.1₁₀ na system binarny z precyzją 7. Wynikiem będzie 0.0001100₁₀.

Dowolny system na dziesiętny

W celu przeliczania ułamka w bazie n na dziesiętny należy dla każdej kolejnej cyfry części ułamkowej wyliczyć jej wartość i wszystko razem zsumować. Rozpatrzmy przykładowo jeszcze raz 0.011₂:

Na sam koniec sumujemy wyliczone wartości i otrzymujemy, że 0.011₂ = 0.375₁₀.

Wróćmy teraz do drugiego przykładu 0.0001001₂.

Na koniec sumujemy wartości i otrzymujemy wynik 0.0001100₂ = 0.09375₁₀ co nie wynosi 0.1.

Weźmy jednak 0.1 w systemie binarnym z precyzją np. 13: 0.0001100110011₂ ~ 0.09997558594. Łatwo zauważyć, że im precyzja większa tym wynik jest dokładniejszy. Jest to problem znany od początku istnienia komputerów. Precyzja przechowywania danych przysparza wiele problemów każdemu kto chce przechować dane nie całkowitoliczbowe. Jednym ze sposobów jest przechowywanie liczb w postaci tekstu co nie prowadzi do utraty precyzji. Takie rozwiązanie zajmuje zdecydowanie więcej miejsca w pamięci.

Implementacja w C++

W zadaniu będę korzystać z kodu poprzedniego artykułu. W tej implementacji będziemy potrzebowali funkcji, która pozwoli nam znaleźć dowolny znak w tekście:

1. int findChar(char* s, char c){
2.   for(int i = 0; s[i]; i++)
3.     if(s[i] == c)
4.       return i;
5.   return -1;
6. }

(1.) Funkcja wyszuka nam znak c w podanej tablicy s. Jeśli nie znajdzie to (4.) zwróci -1.

Dowolny system na dziesiętny

1. double anyToDecimal(char* a, int n){
2.   double liczba = 0;
3.   int dotpos = findChar(a, '.');
4.   double pot = 1;
5.   for(int i = ((dotpos == -1) ? strlen(a) : dotpos) - 1; i >= 0; i--){
6.     liczba += getIntValue(a[i])*pot;
7.     pot *= n;
8.   }

(1.) Tym razem nasza funkcja będzie zwracała liczbę rzeczywistą, a nie całkowitą. Jako argumenty przyjmujemy liczbę zapisaną w tekście a oraz podstawę systemu n. (2.) Wynik będziemy też przechowywać w typie double. (3.) W tekście musimy wiedzieć, gdzie jest część całkowita i ułamkowa, dlatego wyznaczamy gdzie jest kropka. (4.) Wartości cyfr będą mnożone przez potęgi podstawy mniejsze od 1, więc będziemy potrzebowali double po raz kolejny. (5. - 8.) Przeliczanie części całkowitej wymaga tylko poprawy zakresu, gdzie znajduje się ta część. Do tej pory była to długość tekstu teraz jest to pozycja kropki. Poza tym kod bez zmian.

9.   if(dotpos != -1){
10.     pot = 1;
11.     for(int i = dotpos + 1; a[i]; i++){
12.       pot /= n;
13.       liczba += getIntValue(a[i])*pot;
14.     }
15.   }
16.   return liczba;
17. }

(9.) Upewniamy się, że we wczytanej liczbie jest część ułamkowa. (10.) Resetujemy potęgę na 1 i (11.) dla każdej cyfry z części ułamkowej (12.) wyliczamy potęgę (kolejno 1, , , ..), a wyliczoną wartość cyfry (13.) dodajemy do wyniku liczba. Na koniec (16.) zwracamy wyliczoną liczbę.

Dziesiętny na dowolny

Przeliczanie liczby do kropki pozostaje bez zmian.

1. char* decimalToAny(double a, int n, int prec){
2.   int dl = 0;
3.   double pot = 1;
4.   while(a > pot){
5.     pot*=n;
6.     dl++;
7.   }

(1.) Zmieniamy argumenty przyjmowane przez funkcje: a - liczba do skonwertowania, n - baza systemu oraz prec - precyzja z jaka będziemy wypisywać liczbę. (2. - 7.). Wyliczamy długość części całkowitej.

8.   int calkowita = int(a);
9.   a -= calkowita;
10.   char* wynik = new char[dl + prec + 2];
11.   for(int i = dl, pot = 1; i >= 0; i--){
12.     wynik[i - 1] = getCharValue(calkowita % n);
13.     calkowita /= n;
14.   }

Rozdzielamy podaną liczbę na (8.) część całkowitą oraz (9.) część ułamkową. (10.) Alokujemy pamięć pod tekst wynikowy. (11. - 13.) Kod konwertujący część całkowitą pozostaje bez zmian.

15.   wynik[dl]='.';
16.   for(int i = 0; i < prec; i++){
17.     a *= n;
18.     wynik[dl + i + 1] = getCharValue((int)(a));
19.     a -= (int)(a);

20.   }
21.   wynik[dl + prec + 1]='\0';
22.   return wynik;
23. }

(15.) Tam gdzie dopisalibyśmy \0 wstawiamy teraz kropkę "." i (16.) obliczamy kolejne cyfry części ułamkowej. Dla każdego znaku precyzji zgodnie z przeliczaniem: (17.) mnożymy przez podstawę, (18.) dopisujemy wyliczoną cyfrę i (19.) zmniejszamy część ułamkową o pobraną cyfrę. (20.) Dopisujemy znak \0 i (21.) zwracamy wynik.

Testowanie funkcji

Poniższa funkcje main() prezentuje zastosowanie napisanych funkcji.

1. int main () {
2.   char* a = "101.1";
3.   double b = anyToDecimal(a, 2);
4.   cout << b << endl;
5.   char* c = decimalToAny(b, 2, 1);
6.   cout << c << endl;
7.  
8.   system("pause");
9.   return 0;
10. }

Usuwanie zer z końca wyniku

W celu usunięcia zer z końca w pętli wyliczającej kolejne miejsca w której po stwierdzeniu, że część ułamkowa a wyniesie 0:

19.     if(a == 0){
20.       wynik[dl + i]='\0';
21.       return wynik;
22.     }

Pozwoli to uniknąć wypisywania zbędnych zer na końcu część ułamkowej, ale nie jeśli istnieje taka potrzeba.

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Zmodyfikuj funkcję, aby część ułamkową wprowadzało się przy pomocy przecinka ",", a nie kropki "."

Zadanie 2

Zmodyfikuj funkcję decimalToAny(), aby "ucinanie" zer było opcjonalne - ma być podawane jako dodatkowy argumenty, który jest domyślnie prawdziwy.

Zadanie 3