Zamienia liczbę dziesiętną na reprezentację binarną przez kolejne dzielenie przez 2.
Konwersja z systemu dziesiętnego na binarny polega na zapisie liczby dziesiętnej za pomocą cyfr 0 i 1.
Algorytm wykorzystuje dzielenie z resztą przez 2. Resztę zapisujemy jako kolejną cyfrę binarną (od najmłodszej), a wynik dzielenia całkowitego staje się nową wartością do podzielenia. Powtarzamy aż wartość osiągnie 0.
Przykład: liczba 13 w systemie binarnym to 1101.
Złożoność O(log n) wynika z faktu, że w każdej iteracji liczba jest dzielona przez 2 – liczba kroków odpowiada liczbie bitów w zapisie binarnym.
funkcja dziesietna_na_binarna(n): jeżeli n = 0: zwróć "0" wynik ← "" dopóki n > 0: reszta ← n mod 2 // dopisujemy resztę z lewej strony wynik ← reszta + wynik n ← n div 2 zwróć wynik
def dziesietna_na_binarna(n):
if n == 0:
return "0"
wynik = ""
while n > 0:
reszta = n % 2
wynik = str(reszta) + wynik
n = n // 2
return wynik
# Przykład użycia
print(dziesietna_na_binarna(11))
# Wynik: 1011
print(dziesietna_na_binarna(255))
# Wynik: 11111111O(log n)O(log n)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: