Zamiana liczby dziesiętnej na dowolny system o podstawie p w Pythonie

powrót

Zamiana liczby całkowitej dziesiętnej na dowolny system liczbowy o podstawie p (algorytm)

Algorytm zostanie omówiony na przykładzie zamiany liczby 1834 na liczbę w systemie ósemkowym.

W pierwszej kolumnie poniższej tabeli wykonujemy dzielenie całkowite przez podstawę p, natomiast w drugiej kolumnie wyznaczamy resztę z dzielenia liczby stojącej po lewej stronie przez podstawę p. Czynności te wykonujemy do momentu otrzymania wartości 0 w lewej kolumnie. Poniżej zamienimy liczbę $$1834$$ na liczbę zapisaną w systemie ósemkowym (p = 8):

Następnie wynik spisujemy od końca z prawej kolumny tabeli:

$$1834=(3452)_8$$

Złożoność algorytmu

Ponieważ w każdym kolejnym kroku algorytmu wykonujemy dzielenie liczby n przez liczbę p, to łatwo jest stwierdzić, że złożoność czasowa wynosi $$O(\log n)$$

Zadanie

Dla podanej liczby całkowitej dodatniej n oraz liczby całkowitej p, zamień liczbę n na liczbę zapisaną w systemie o podstawie p.

Wejście

Dwie całkowite n i p, gdzie p należy do przedziału [2..36].

Wyjście

Liczba n zapisana w systemie o podstawie

Wejście:
10 2

Wyjście:
1010

#******************algorytm.edu.pl*******************************
def zamien(n, p): #zamień liczbę n na liczbę zapisaną w systemie o podstawie p
    if n > 0:
        zamien(n//p, p)
        print('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[n%p], end='') # pobieraj kolejne cyfry

#******************Główna część programu**************************
n, p = map(int, input("Podaj liczbę n oraz system liczbowy, na który chcesz ją zamienić [2..36]: ").split())
if n == 0: print('0')
else: zamien(n, p)