Перевод числа из десятичной системы счисления

С клавиатуры вводятся два целых положительных числа: 1 < p < 10 — основание системы счисления и n — десятичное число. Задача — перевести n в систему счисления с основанием p и вывести результат на экран.

Для этого можно использовать алгоритм деления с остатком. Будем делить n на p до тех пор, пока результат деления не станет нулем. Остатки от деления запишем в обратном порядке — это и будет представление числа n в системе счисления с основанием p.

Здесь важно показать на примере, что такое обратный порядок сбора остатков.

Реализация алгоритма

# Перевод числа из десятичной системы в p-ичную (p ≤ 10)

# Ввод данных
p = int(input("Введите основание системы счисления (p ≤ 10): "))
n = int(input("Введите число в десятичной системе: "))

result = 0  # здесь будем собирать результат в p-ичной системе
w = 1       # вес разряда (десятичный множитель для построения числа)

while n > 0:
    result += (n % p) * w  # берём остаток от деления на p — это цифра в p-ичной системе
    n //= p                # убираем обработанный разряд
    w *= 10                # сдвигаем вес на следующий разряд

print(result)

Реализация алгоритма с демонстрацией каждого шага

p = int(input("Введите основание системы счисления p (2 ≤ p ≤ 10): "))
n = int(input("Введите число в десятичной системе: "))

if not (2 <= p <= 10):
    print("Основание p должно быть от 2 до 10.")
else:
    if n == 0:
        print("\nЧисло 0 в любой системе — это 0.")
    else:
        print(f"\nПереводим {n} в систему с основанием {p}. Начинаем сбор остатков (с младшего разряда).")
        step = 1
        result_integer = 0  # собираем число в виде десятичной записи цифр p-ичной системы
        weight = 1          # 1, 10, 100, ... — место для следующей цифры в decimal-форме результата
        digits = []         # здесь сохраняем остатки (младший разряд первым)

        while n > 0:
            current = n
            remainder = current % p
            print(f"\nШаг {step}:")
            print(f"  Текущее n = {current}")
            print(f"  Остаток от деления на {p} = {remainder}  (это следующая цифра в p-ичной записи, снизу вверх)")

            # добавляем цифру в числовой результат (как в оригинальном алгоритме)
            add = remainder * weight
            result_integer += add
            print(f"  Добавляю в результат: {remainder} × {weight} = {add}  → промежуточный numeric-результат = {result_integer}")

            digits.append(remainder)    # запомним цифру
            weight *= 10                # переходим к следующему разряду decimal-результата
            n //= p                     # уменьшаем n (удаляем младший разряд)
            print(f"  После целочисленного деления n теперь = {n}")

            step += 1

        # digits сейчас в порядке от младшего разряда к старшему — перевернём для читабельности
        digits_str = ''.join(map(str, digits[::-1]))

        print("\n✅ Перевод завершён!")
        print(f"p-ичная запись (как строка): {digits_str}")
        print(f"p-ичная запись (в виде числа, собранного по алгоритму) : {result_integer}")

Заметьте: остаток добавляется в результат слева, то есть мы каждый раз приклеиваем старший разряд. У этого алгоритма также линейная сложность.