1. Введение

В задании №14 нужно работать с позиционными системами счисления. Обычно дано арифметическое выражение, его значение рассматривают в системе с основанием b, а затем исследуют цифры получившейся записи.

Задание проверяет умение:

  1. понимать, какие цифры допустимы в системе с основанием b;
  2. переводить целое число делением с остатком;
  3. получать отдельные цифры операциями % и //;
  4. перебирать числовой параметр x или неизвестную цифру;
  5. проверять количество цифр, сумму цифр, делимость и другие условия.

Важное различие: иногда x — обычное целое число, а иногда x обозначает ровно одну цифру записи. От этого зависит граница перебора и способ составления числа.

2. Теория систем счисления

Система счисления с основанием b использует цифры от 0 до b − 1. Например, в троичной системе разрешены только 0, 1 и 2; в пятеричной — 0, 1, 2, 3 и 4.

Значение цифры зависит от её позиции. Справа налево позиции имеют веса b⁰, b¹, b² и так далее.

1

Нижний индекс у числа показывает основание системы счисления: 2202₃ — троичная запись, а 74₁₀ — десятичная.

Для оснований больше 10 после цифры 9 используют буквы: A = 10, B = 11, … . В Python функция int(строка, основание) умеет читать записи с основаниями от 2 до 36.

Как перевести число в другую систему

  1. Делим число на основание новой системы.
  2. Записываем остаток — это очередная цифра справа.
  3. Целую часть результата снова делим на основание.
  4. Повторяем, пока частное не станет равно нулю.
  5. Читаем остатки в обратном порядке: снизу вверх.
1

Остатки читаем снизу вверх: последний найденный остаток становится первой цифрой новой записи.

Функция перевода

Для оснований больше 10 нужна последовательность символов: остаткам 10, 11, … соответствуют буквы A, B, … . Запишем цифры и буквы строкой, а функция sorted расставит их в правильном порядке.

alf = sorted('1234567890QWERTYUIOPASDFGHJKLZXCVBNM')

def to_base(n, base):
    if n == 0: return '0'
    s = ''
    while n > 0:
        s = alf[n % base] + s
        n //= base
    return s

print(to_base(74, 3))   # 2202
print(to_base(31, 16))  # 1F

После sorted переменная alf содержит символы 0–9 и A–Z по возрастанию. Выражение alf[n % base] выбирает символ, соответствующий очередному остатку. В исходной строке каждая цифра и буква должна встретиться ровно один раз.

Когда строку строить не нужно

1

Если спрашивают количество определённых цифр, сумму цифр, наибольшую цифру или число нулей, полная запись не нужна. Достаточно в цикле смотреть на n % base, после чего выполнять n //= base.

count = 0
while n > 0:
    digit = n % base
    if digit == needed:
        count += 1
    n //= base

3. Виды задач

1

Прототип 1. Найти количество цифр

Значение выражения 25¹⁸ · 5¹⁰ − 5⁶ − 25 записали в системе с основанием 5. Сколько цифр 4 содержится в этой записи?

Как рассуждать

  1. Вычисляем значение выражения в обычном целом типе Python.
  2. Остаток n % 5 показывает последнюю цифру пятеричной записи.
  3. Если остаток равен 4, увеличиваем счётчик.
  4. Операцией n //= 5 удаляем последнюю цифру и продолжаем цикл.
n = 25**18 * 5**10 - 5**6 - 25
count = 0

while n > 0:
    if n % 5 == 4:
        count += 1
    n //= 5

print(count)

Ответ: 43

Здесь функция перевода была бы лишней: мы всё равно рассматриваем цифры по одной. Такой вариант короче и не хранит огромную строку.

Прототип 2. Найти x, при котором выполняется условие

Значение 6²⁰³⁰ + 6¹⁰⁰ − x, где x — целое положительное число, не превышающее 2030, записали в шестиричной системе. Найдите минимальное количество нулей, которое может содержаться в этой записи.

Что меняется по сравнению с первым прототипом

  1. x — обычное число, поэтому перебираем все значения от 1 до 2030 включительно;
  2. для каждого x заново считаем количество нулевых остатков;
  3. сохраняем минимальное найденное количество, а не саму запись числа.
constant = 6**2030 + 6**100
best = 10**9

for x in range(1, 2031):
    n = constant - x
    zeros = 0
    while n > 0:
        if n % 6 == 0:
            zeros += 1
        n //= 6
    best = min(best, zeros)

print(best)

Ответ: 1930

Прототип 3. x обозначает цифру

В 21-ричной системе дано выражение 635x45₂₁ + 532x3₂₁ + 975x16768₂₁. Переменная x обозначает неизвестную цифру. Нужно найти наименьшую x, при которой сумма кратна 20, а затем вывести частное от деления суммы на 20.

1

На схеме под каждым символом указано его числовое значение.

В этом прототипе x — не произвольное число, а один символ из алфавита основания. Для основания 21 допустимы 0–9 и A–K.

Два способа собрать запись

# f-строка
n1 = int(f'635{x}45', 21)

# обычное сложение строк
n1 = int('635' + x + '45', 21)

Оба варианта дают одну строку. f-строка обычно читается легче, а сложение строк полезно, если такой синтаксис пока привычнее.

Полное решение

alphabet = '0123456789ABCDEFGHIJK'

for x in alphabet:
    n1 = int(f'635{x}45', 21)
    n2 = int(f'532{x}3', 21)
    n3 = int(f'975{x}16768', 21)
    total = n1 + n2 + n3
    if total % 20 == 0:
        print(total // 20)
        break

Наименьшая цифра x = 5. Ответ: 17674449812

Видео разбор

Так-же есть видео, в котором разбираются и объясняются с нуля все основные прототипы