Что проверяет задание

Дан алгоритм, который преобразует натуральное число: переводит его в другую систему счисления, меняет цифры, дописывает биты, считает сумму цифр. Нужно найти исходное число, результат или количество подходящих исходных чисел.

Определения

Система счисления с основанием q, способ записи числа, в котором каждая позиция, степень q. Допустимые цифры: от 0 до q − 1.

Двоичная запись, запись по основанию 2. Цифры только 0 и 1. Их называют битами.

Старший бит, крайняя левая значащая цифра двоичной записи. Младший бит, крайняя правая.

Сумма двоичных цифр, количество единиц в двоичной записи. Её же называют весом Хэмминга двоичного слова.

Чётность числа единиц, свойство «чётное или нечётное количество единиц». Часто по нему дописывают контрольный бит.

Алгоритм-преобразователь, конечная последовательность шагов: перевод, отрезание/дописывание цифр, арифметика над цифрами, обратный перевод в десятичную систему.

Результат алгоритма R(n), число, которое получается, если подать на вход n.

Обратная задача, по значению R(n) или по ограничению на R(n) восстановить n. Поскольку шаги алгоритма не всегда взаимно однозначны, подходящих n может быть несколько.

Что обычно делают с записью

• отбросить первую или последнюю цифру;
• дописать справа 0 или 1;
• дописать бит чётности;
• заменить число его суммой цифр;
• переставить цифры;
• перейти из одной системы счисления в другую.

Каждый такой шаг меняет либо сам набор цифр, либо их позиционные веса. Поэтому после цепочки шагов результат уже нельзя читать «как исходное число».

Общий алгоритм решения

1. Выписать шаги преобразователя по порядку, не пропуская переводы между системами.
2. Понять, прямой это поиск (по n найти R) или обратный (по R найти n).
3. Если диапазон входов невелик по смыслу условия, перебрать допустимые n и отфильтровать по требованию на R(n).
4. Если перебор велик, идти с конца: по последнему шагу восстановить, какими могли быть предыдущие записи.
5. Следить за тем, что ведущие нули после отрезания старшей цифры меняют длину записи.
6. Записать ответ в той форме, которую просит условие: само число, минимум, максимум или количество.

Программа построчно

Почти любое задание 5 решается программой из двух частей.

1. Функция algo повторяет алгоритм из условия для одного числа: получает N и возвращает R.
2. Цикл перебирает числа N одно за другим, для каждого вызывает algo и проверяет требование вопроса.

Разберём программу на таком условии:

Строится двоичная запись числа N. Если N чётное, справа дописывается 10, иначе 01. Полученная запись - двоичная запись числа R. Укажите наименьшее N, для которого R больше 129.

def algo(n):
    s = bin(n)[2:]
    if n % 2 == 0:
        s = s + "10"
    else:
        s = s + "01"
    return int(s, 2)

for n in range(1, 10000):
    r = algo(n)
    if r > 129:
        print(n)
        break

Функция: алгоритм для одного числа

def algo(n):

Слово def объявляет функцию - именованный кусок программы, который можно вызывать много раз. algo - её имя (можно любое), n в скобках - входное значение: то число N, которое мы подаём на вход алгоритма.

Зачем функция: алгоритм из условия по одному числу N строит одно число R. В цикле нам нужно проделать это для тысяч разных N. Удобно один раз записать алгоритм в функцию, а потом просто писать algo(5), algo(6), algo(n).

Все строки функции записаны с отступом в 4 пробела - так Python понимает, что они принадлежат функции.

s = bin(n)[2:]

Это пункт «строится двоичная запись числа N». Строка выполняется в два действия:

1. bin(n) переводит число в двоичную запись, но возвращает её строкой с приставкой 0b. Например, bin(13) даёт строку '0b1101'.
2. [2:] - срез: «взять строку, начиная с символа номер 2». Символы нумеруются с нуля: '0' - номер 0, 'b' - номер 1, дальше идут цифры записи. Срез отбрасывает приставку, остаётся '1101'.

Результат кладём в переменную s. Почему именно строкой: в задании 5 с записью делают «посимвольные» действия - дописывают цифры справа, отрезают последнюю, считают единицы. Со строкой всё это делается одной короткой командой, а с числом пришлось бы считать степени двойки вручную.

if n % 2 == 0:

Это пункт «если N чётное». Знак % - остаток от деления: 13 % 2 равно 1, 14 % 2 равно 0. Чётное число делится на 2 без остатка, поэтому «N чётное» записывается как «остаток от деления N на 2 равен нулю»: n % 2 == 0. Двойное == - это проверка «равно ли», а одинарное = - присваивание значения переменной, их нельзя путать.

Если условие верно, выполняются строки с отступом под if. Если нет - строки под else.

s = s + "10"

Это «справа дописывается 10». Знак + у строк не складывает, а склеивает: '1101' + '10' даёт '110110'. Новые цифры встают после старых - это и есть «дописать справа». Цифры "10" записаны в кавычках: нам нужны два символа «1» и «0», а не число десять.

else: и s = s + "01"

else означает «иначе» - эта часть работает, когда условие в if оказалось ложным, то есть N нечётное. Тогда дописываем "01".

return int(s, 2)

Это пункт «полученная запись - двоичная запись числа R». Запись s - строка из нулей и единиц. Функция int(строка, 2) читает её как число в двоичной системе и возвращает обычное (десятичное) число:

int('110110', 2) = 1·2⁵ + 1·2⁴ + 0·2³ + 1·2² + 1·2¹ + 0·2⁰ = 32 + 16 + 4 + 2 = 54.

return возвращает результат из функции: там, где написано algo(13), окажется число 54. Возвращаем именно число, а не строку, потому что дальше R будем сравнивать с 129 - сравнивать числа как числа.

Цикл: перебор и проверка вопроса

for n in range(1, 10000):

range(1, 10000) - последовательность чисел 1, 2, 3, …, 9999. Правая граница не входит: последнее число 9999, а не 10000. Цикл for по очереди кладёт каждое из этих чисел в переменную n и выполняет строки с отступом под ним.

Почему начинаем с 1: N - натуральное число, а натуральные числа начинаются с 1. Если в условии сказано «N > 1» или «пятизначное число», начало меняют: range(2, …) или range(10000, 100000).

Почему до 10000: это граница «с запасом». Ответ в задании 5 обычно двух- или трёхзначный, а R растёт вместе с N. Если ответ вдруг получится у самой границы (например, 9999) - значит, границы не хватило, и её нужно увеличить.

r = algo(n)

Вызываем функцию для текущего N и запоминаем результат в r. Для n = 13 получим r = 54.

if r > 129:

Это требование вопроса «R больше 129». Как переводить слова условия в знаки:

• «больше 129» - r > 129;
• «не меньше 129» (больше или равно) - r >= 129;
• «меньше 129» - r < 129;
• «не превышает 129», «не больше 129» (меньше или равно) - r <= 129;
• «равен 129» - r == 129.

print(n)

Выводит найденное число. В вопросе спрашивают N, поэтому печатаем n. Если бы спрашивали R («укажите наименьшее число R…»), печатали бы r.

break

Немедленно прерывает цикл. Числа перебираются по возрастанию: 1, 2, 3… Значит, первое N, для которого условие выполнилось, - наименьшее из подходящих, и дальше искать незачем.

Как это работает на числах: для n = 31 получаем запись '11111', N нечётное, дописываем '01' → '1111101' = 125 - это не больше 129, идём дальше. Для n = 32 получаем '100000', N чётное, дописываем '10' → '10000010' = 130 - больше 129. Печатаем 32 и останавливаемся. Ответ: 32.

Как меняется цикл под вопрос

Функция algo зависит только от правил алгоритма. От вопроса зависит только цикл после неё. Ниже - каждый вид вопроса отдельно.

Наименьшее N, для которого выполняется условие

for n in range(1, 10000):
    r = algo(n)
    if r > 129:
        print(n)
        break

Перебираем N по возрастанию и останавливаемся на первом подходящем - оно и есть наименьшее. Это программа из разбора выше.

Наибольшее N, для которого выполняется условие

for n in range(100, 0, -1):
    r = algo(n)
    if r == 117:
        print(n)
        break

У range появилось третье число - шаг. Шаг -1 значит «идти назад»: range(100, 0, -1) даёт 100, 99, 98, …, 1 (правая граница 0 по-прежнему не входит).

Почему так: теперь мы идём сверху вниз, и первое найденное N оказывается наибольшим из подходящих. Можно сразу печатать его и выходить из цикла.

Откуда начало 100: если в условии сказано «наибольшее число, не превышающее 100», то больше 100 брать нельзя - начинаем со 100. Если ограничения нет, начинают с заведомо большого числа, например range(10000, 0, -1).

Наименьшее R, которое больше X

Здесь спрашивают не N, а сам результат R. Важная ловушка: R растёт с N неравномерно. Пусть алгоритм такой: если N нечётное, в начало и в конец двоичной записи дописывается 11, если чётное - в начало 1, в конец 0. Тогда:

• N = 5: '101' → '11' + '101' + '11' = '1110111' = 119;
• N = 6: '110' → '1' + '110' + '0' = '11100' = 28.

У большего N получилось меньшее R. Поэтому нельзя остановиться на первом R, которое больше X: при пороге 97 первым по порядку N найдётся R = 119 (при N = 5), а наименьшее подходящее R = 100 получается только при N = 18. Нужно посчитать R для всех N и выбрать из подходящих наименьшее:

results = []
for n in range(1, 10000):
    r = algo(n)
    if r > 97:
        results.append(r)
print(min(results))

Разбор:

• results = [] - пустой список, сюда будем складывать все подходящие R.
• Цикл перебирает все N без break: останавливаться нельзя, наименьшее R может встретиться где угодно.
• if r > 97: - проверяем условие из вопроса.
• results.append(r) - append добавляет число в конец списка. После цикла в списке окажутся все R, которые больше 97.
• min(results) - наименьшее число из списка. Его и печатаем.

Для «наибольшего R, которое меньше X» всё то же самое, только условие r < X и в конце max(results).

Тот же поиск можно записать и без списка - запоминая лучшее найденное R:

best = None
for n in range(1, 10000):
    r = algo(n)
    if r > 97:
        if best is None or r < best:
            best = r
print(best)

best = None - «пока ничего не найдено» (None в Python означает «нет значения»). Для каждого подходящего R проверяем: если это первое найденное (best is None) или оно меньше уже запомненного (r < best), запоминаем его. В конце в best останется наименьшее.

Сколько N, для которых выполняется условие

count = 0
for n in range(1, 10000):
    r = algo(n)
    if r <= 37:
        count += 1
print(count)

• count = 0 - счётчик, сначала подходящих чисел ноль.
• count += 1 - сокращённая запись count = count + 1: увеличить счётчик на один. Строка выполняется только для тех N, у которых выполнилось условие.
• После цикла печатаем, сколько набралось.

Пример на алгоритме из разбора (чётному N дописываем 10, нечётному 01): R(1) = 5, R(2) = 10, …, R(8) = 34, R(9) = 37 - все не больше 37, а R(10) = 42 уже больше. Счётчик насчитает 9 чисел: N = 1, 2, …, 9.

Сколько разных значений R на отрезке [a; b]

Если спрашивают, сколько разных чисел может получиться, одинаковые R нужно считать один раз: разные N иногда дают один и тот же R. Для этого используют множество (set) - набор, в котором каждое значение хранится не больше одного раза.

values = set()
for n in range(1, 10000):
    r = algo(n)
    if 9 <= r <= 92:
        values.add(r)
print(len(values))

• values = set() - пустое множество.
• 9 <= r <= 92 - «R принадлежит отрезку [9; 92]», то есть одновременно r >= 9 и r <= 92. Python позволяет записать двойное неравенство как в математике.
• values.add(r) - добавляет R в множество. Если такое значение там уже есть, ничего не меняется: если добавить 10, 12 и снова 10, в множестве останется два числа: {10, 12}.
• len(values) - количество элементов, то есть количество разных R.

Чему равно R при заданном N

print(algo(17))

Перебор не нужен: N уже дано в вопросе, достаточно один раз вызвать функцию и напечатать результат.

Инструменты, которые встречаются в решениях

Перевод в двоичную систему: bin(n)[2:]

s = bin(13)      # '0b1101'
s = s[2:]        # '1101'

bin умеет только двоичную систему и всегда добавляет приставку 0b («это двоичная запись»). Срез [2:] оставляет только цифры. Иногда в решениях встречается bin(n)[3:] - это срез с символа номер 3: убирается приставка и первая цифра записи (у двоичной записи она всегда 1). Например, bin(13)[3:] = '101'. Так записывают пункт «удаляется первая единица».

Обратный перевод: int(s, основание)

int('1101', 2)   # 13
int('111', 8)    # 73
int('ff', 16)    # 255

Второе число - основание системы, в которой записана строка. Функция складывает цифры, умноженные на степени основания:

• '1101' в двоичной: 1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 8 + 4 + 1 = 13;
• '111' в восьмеричной: 1·8² + 1·8¹ + 1·8⁰ = 64 + 8 + 1 = 73.

Основание может быть от 2 до 36; цифры больше 9 записываются буквами: a = 10, b = 11, …, f = 15.

Перевод в любую систему: функция perevod(n, ss)

Для системы с основанием 3, 5, 8 и т. д. готовой функции нет. В решениях используется такая:

from string import printable

def perevod(n, ss):
    res = ''
    while n > 0:
        res = printable[n % ss] + res
        n //= ss
    return res or '0'

from string import printable - подключаем готовую строку printable из стандартного модуля string. Её начало - '0123456789abcdefghijklmnopqrstuvwxyz…': все цифры, затем буквы. Она нужна как «таблица цифр»: printable[5] - символ '5', printable[10] - 'a', printable[15] - 'f'. Так одна функция работает и для систем с основанием больше 10.

def perevod(n, ss): - функция с двумя входами: n - число, которое переводим, ss - основание системы счисления.

res = '' - пустая строка. В неё будем собирать цифры записи.

while n > 0: - цикл «пока»: строки под ним повторяются, пока число n больше нуля. Число каждый раз уменьшается, и когда от него ничего не останется, цикл закончится.

res = printable[n % ss] + res - главная строка перевода. n % ss - остаток от деления числа на основание; это последняя (правая) цифра записи. printable[...] превращает её в символ. Этот символ ставим перед уже собранными цифрами (символ + res): цифры находятся справа налево, поэтому каждая следующая должна встать левее предыдущих.

n //= ss - сокращение для n = n // ss. Знак // - деление нацело (без остатка): 9 // 8 = 1. Так мы отбрасываем уже записанную последнюю цифру и переходим к следующей.

return res or '0' - возвращаем готовую запись. or '0' нужен для единственного особого случая - числа 0: цикл while для него не выполнится ни разу, res останется пустой строкой, а пустая строка в Python считается «ложью» - тогда вместо неё вернётся '0'.

Как функция работает на примерах.

perevod(9, 8):

1. n = 9: остаток 9 % 8 = 1 → res = '1'; n = 9 // 8 = 1.
2. n = 1: остаток 1 % 8 = 1 → res = '1' + '1' = '11'; n = 1 // 8 = 0.
3. n = 0 - цикл закончился. Результат '11'. Проверка: 1·8 + 1 = 9.

perevod(10, 3):

1. n = 10: 10 % 3 = 1 → res = '1'; n = 10 // 3 = 3.
2. n = 3: 3 % 3 = 0 → res = '0' + '1' = '01'; n = 3 // 3 = 1.
3. n = 1: 1 % 3 = 1 → res = '1' + '01' = '101'; n = 0.

Результат '101'. Проверка: 1·9 + 0·3 + 1·1 = 10.

perevod(255, 16): 255 % 16 = 15 → printable[15] = 'f', n = 15; 15 % 16 = 15 → ещё 'f', n = 0. Результат 'ff'.

Обратно в десятичную систему запись переводит int(res, ss): int('101', 3) = 10.

Сумма цифр числа

В решениях встречаются три записи одного и того же.

Способ 1. sum(map(int, str(n))) - так устроена функция sum_digits:

def sum_digits(n):
    return sum(map(int, str(n)))

Читается изнутри наружу:

1. str(n) превращает число в строку цифр: str(9575) = '9575'. Если на вход уже подана строка-запись (например, '11' из перевода), str оставит её как есть.
2. map(int, ...) применяет int к каждому символу строки: '9' → 9, '5' → 5, '7' → 7, '5' → 5.
3. sum(...) складывает получившиеся числа: 9 + 5 + 7 + 5 = 26.

Важно: так можно складывать только цифры от 0 до 9. Запись вроде 'ff' (шестнадцатеричная) так не сложится - int('f') выдаст ошибку.

Способ 2. sum(int(d) for d in s) - то же самое, но вместо map перебор символов прямо внутри sum: «для каждого символа d строки s взять int(d) и всё сложить». sum(int(d) for d in '63179') = 6 + 3 + 1 + 7 + 9 = 26.

Способ 3. Через остатки от деления на 10, без строк:

def sum_digits(n):
    total = 0
    while n > 0:
        total += n % 10
        n //= 10
    return total

n % 10 - последняя цифра числа, n //= 10 - отбросить её. Для 9575: прибавляем 5 (остаётся 957), затем 7 (остаётся 95), затем 5 (остаётся 9), затем 9 (остаётся 0). Сумма 5 + 7 + 5 + 9 = 26 - та же, что у первых двух способов. Это тот же приём, что в переводе, только основание 10.

Сумма цифр двоичной записи и количество единиц: s.count('1')

s = '1101'
s.count('1')     # 3
s.count('0')     # 1

count считает, сколько раз символ встречается в строке. У двоичной записи цифры только 0 и 1, поэтому сумма цифр равна количеству единиц: 1 + 1 + 0 + 1 = 3 = s.count('1').

Частая запись в решениях - s += str(s.count('1') % 2): посчитать единицы, взять остаток от деления на 2 (0 - чётное количество, 1 - нечётное) и дописать эту цифру справа. str(...) превращает число в символ, потому что к строке можно приклеить только строку. Для '1101': единиц 3, 3 % 2 = 1, получится '11011'.

Если пункт условия повторяется для новой записи («то же действие выполняется над полученной записью»), строку пишут второй раз - count во второй раз считает единицы уже вместе с дописанной цифрой.

Срезы строки

Срез s[начало:конец] берёт кусок строки; символы нумеруются с нуля, конец не включается, отрицательные номера считаются с конца строки. Для s = '1101':

• s[:-1] = '110' - всё, кроме последнего символа: «удаляется последняя цифра»;
• s[1:] = '101' - всё, начиная со второго символа: «удаляется первая цифра»;
• s[-1] = '1' - последний символ, s[0] = '1' - первый;
• s[::-1] = '1011' - строка задом наперёд (шаг -1): «запись переворачивается».

Дописывание в начало и в конец

• s = s + '10' (или s += '10') - дописать справа;
• s = '11' + s - дописать слева, в начало;
• s = '1' + s + '0' - сразу и в начало, и в конец.

Условие в одну строку: x if условие else y

s += '1' if s.count('1') % 2 == 0 else '0'

Читается как «дописать '1', если количество единиц чётное, иначе дописать '0'». Это та же конструкция if … else, просто записанная в одну строку. Для '1101' единиц 3 - нечётно, допишется '0' → '11010'.

Замена цифр на противоположные

s = ''.join('1' if c == '0' else '0' for c in s)

Для каждого символа c строки: если это '0', берём '1', иначе берём '0'. ''.join(...) склеивает полученные символы в одну строку без разделителей. '1101' превращается в '0010'.

Цифры десятичного числа по отдельности

В задачах «автомат получает пятизначное число и складывает его цифры» переводов нет:

s = str(n)                              # '63179'
k1 = int(s[0]) + int(s[2]) + int(s[4])  # 6 + 1 + 9 = 16
k2 = int(s[1]) + int(s[3])              # 3 + 7 = 10

s[0] - первая цифра (нумерация с нуля!), s[2] - третья, s[4] - пятая. int(...) превращает символ-цифру в число, чтобы цифры можно было складывать: без int получилась бы склейка строк '6' + '1' = '61'.

Записать суммы «в порядке неубывания» (сначала меньшая):

first = str(min(k1, k2))    # '10'
second = str(max(k1, k2))   # '16'
result = first + second     # '1016'

min и max выбирают меньшее и большее число, str превращает их в строки, + склеивает. Результат '1016' - строка, поэтому и сравнивать её нужно со строкой: if result == '925':.

Две наибольшие суммы из трёх, по убыванию:

sums = [k1, k2, k3]
sums_sorted = sorted(sums, reverse=True)
result = str(sums_sorted[0]) + str(sums_sorted[1])

sorted(..., reverse=True) сортирует числа по убыванию; [0] и [1] - две самые большие. Для 9575: суммы 14, 12, 12 → [14, 12, 12] → '14' + '12' = '1412'.

Наименьшая сумма удаляется:

sums.remove(min(sums))
sums.sort()

remove удаляет из списка указанное значение (одно, первое найденное), sort() сортирует список по возрастанию. Для 1984: суммы 10, 17, 12 → удаляем 10 → [17, 12] → после сортировки [12, 17] → '1217'.

Подходят не все числа. Если в условии сказано «на вход подаются числа только с нечётными цифрами», лишние числа пропускают проверкой:

if all(int(d) % 2 == 1 for d in s):

all(...) истинно, только если условие выполнено для каждой цифры. Для '7511' - да, для '7512' - нет (цифра 2 чётная).

Шаг алгоритма повторяется несколько раз

def transform_steps(n, steps=5):
    value = n
    for _ in range(steps):
        value = step_output_value(value)
    return value

Когда в условии сказано «алгоритм применяется несколько раз подряд», один шаг записывают отдельной функцией (step_output_value), а затем применяют его в цикле нужное число раз. _ вместо имени переменной значит «номер повторения нам не нужен». Результат каждого шага становится входом следующего: value = step_output_value(value).

Строки print с текстом

print(f"Найденное число: {i}")

Буква f перед кавычками разрешает вставлять значения переменных прямо в текст: на месте {i} окажется число. На экзамене в ответ записывают только само число.

Проверка себя

Перед перебором вызовите algo для числа из примера в условии: print(algo(13)) должно дать то же R, что в примере. Если не совпало - ошибка в функции, и перебор её не исправит.