Jakub Piskorowski on 24/10/2023 wersja: 1.0
Przedstawienie działania algorytmu zamiany liczby dziesiętnej na binarną.
Kod źródłowy: decimal-to-binary.cpp
📗 Poziom 2
Powrót do Algorytmika
System binarny lub system dwójkowy, to sposób zapisu liczby całkowitej oparty o zera i jedynki, wskazujące kolejne potęgi liczby 2 występujące na kolejnych pozycjach liczby całkowitej.
W systemie binarnym do zapisu liczby używamy cyfr 0 i 1 , w którym każda pozycja cyfr składających się na liczby jest określona kolejną potęgą dwójki (a po prawej stronie, jak w systemie dziesiętnym są cyfry z najmniejszą wagą pozycji).
Zapis liczby binarnej (liczby dwójkowej) tworzymy z cyfr będących do dyspozycji w systemie binarnym. Na przykład liczba 11010 w systemie binarnym będzie przedstawiona jako:
W systemie dwójkowym zapis liczby binarnej 11010 oznacza w systemie dziesiętnym 26. Jak to policzyliśmy? Jedynka na pozycji szesnastek potem jedynka na pozycji ósemek i jedynka na pozycji dwójek.
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | – liczba binarna (dziesiętnie 16+8+2=26) czyli:
Dla przykładu zamieńmy liczbę 20 na liczbę binarną.
W jednym kroku algorytmu wykonujemy dwie czynności:
- wyznaczamy resztę z dzielenia przez 2 konwertowanej liczby
- konwertowaną liczbę dzielimy przez 2 (dzielenie całkowite)
Daną czynność wykonujemy tak długo, jak długo liczba dziesiętna jest większa od 0.
Przykład zamiany liczby 20 jest przedstawiony poniżej:
Następnym krokiem jest spisanie reszt (z dołu do góry), czyli:
20 = (10100)^2
Do rozwiązania problemu posłużymy się tablicą, a następnie wyświetlimy jej zawartość w odwrotnej kolejności. Załóżmy, że typ int składa się z 4 bajtów, czyli maksymalnie możemy uzyskać 31 bitów (jeden bit przeznaczony jest na znak liczby).
Wejście:
liczba – liczba dziesietna
Lista kroków:
K1: tab[15] deklaracja tablicy o rozmiarze 31
K2: i ← 0 deklaracja iteratora
K3: dopóki liczba jest różna od zera
wykonuj kroki k4...k5
K4: tab[i++] ← liczba modulo 2 zapisujemy resztę z dzielenia w kolejnym elemencie tablicy
K5: liczba ← liczba / 2
K6: od j ← i-1 do j >=0
wykonuj krok k7
K7: wyświetl element tablicy z indeksem j
Wynik działania programu:
Podaj liczbe dziesietna: 26
Liczba 26 po zamianie na postac binarna: 11010
Kod źródłowy: decimal-to-binary.cpp