Алгоритм решения задания 5. Часть 1

О задании

Задание 5 ЕГЭ по информатике нацелено на проверку умений учащихся выполнять и анализировать простые алгоритмы.

В данном задании дан некий алгоритм – последовательность действий, которая:

Берёт обычное натуральное число (1, 2, 3, 4 и так далее)
Переводит его в заданную систему счисления (например, в двоичную, где есть только 0 и 1)
Обрабатывает полученную запись по определённым правилам (добавляет цифры, считает сумму, проверяет условия)
Выдаёт результат

Обычно в ответ требуется дать число, являющееся результатом работы данного алгоритма при определённых условиях, при этом выполнив перевод этого числа обратно в десятичную систему счисления.

Правда, в иных формулировках в ответ требуется дать исходное число, после обработки которого получается заданное число.

На этом принципе мы и разделим задания 5 на два типа:

В заданиях первого типа на вход алгоритма подаётся число N, а в ответ нужно дать минимальное или максимальное число N, после обработки которого с помощью алгоритма получается число R, удовлетворяющее заданному условию
В заданиях второго типа, напротив, нужно вывести результат работы алгоритма – число R – при некотором условии для исходного числа N, поступающего на вход алгоритма

Каждый из этих типов мы разберём в отдельной статье. Сегодня же мы вспомним, как работать с системами счисления в Python, научимся обрабатывать числа по заданному алгоритму и разберём основные алгоритмы решения первого типа задания 5.

Алгоритм решения

Первым делом внимательно читаем условие и выясняем, с какой системой счисления предстоит работать.

Python предоставляет нам встроенные функции для работы с популярными системами счисления:

bin() – для двоичной
oct() – для восьмеричной
hex() – для шестнадцатеричной

Но что делать, если нужна, например, пятеричная система? Тут придётся написать свою функцию перевода. Не волнуйтесь, это не так сложно, как кажется! В предыдущей статье мы подробно разбирали, как создать универсальную функцию для перевода в любую систему счисления.

Теперь начинается самое интересное – поиск нужного числа. Мы будем действовать методично, перебирая каждое число в цикле:

for N in range(1, верхняя_граница):

Важный момент: верхнюю границу диапазона придётся подбирать самостоятельно! Начните с небольших значений (например, 20), и, если ответ не находится – увеличивайте. Учтите, что правая граница в range() не входит в диапазон: range(1, 30) перебирает числа от 1 до 29.

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

for N in range(1, верхняя_граница)[::-1]:

Внутри цикла для каждого числа N выполняем следующие действия:

Переводим число в нужную систему счисления встроенными функциями или вызываем собственную.
Проверяем условия из задания. В задании обычно даются условия по типу: «Если число чётное, то…», «Если сумма цифр делится на 3, то…». Это развилки на нашем пути – в зависимости от условия мы идём по разным маршрутам обработки.
Выполняем требуемые преобразования. Может потребоваться вычислить сумму цифр этого числа, дописать к нему слева или справа какие-либо цифры или выполнить ещё какие математические действия.

Итог выполнения этих действий как раз и будет записью искомого числа R в заданной системе счисления. Останется лишь перевести эту запись обратно в десятичную систему и выполнить последнее условие. Для перевода будем пользоваться стандартной функцией int():

R = int(R_в_системе, основание_системы)

После чего требуется сравнить это число R с каким-либо другим и при выполнении этого условия вывести число N.

На этом все, словесное описание базового алгоритма решения задания 5 закончено. Давайте опробуем его на практике и решим пару заданий.

Пример 1

Начнём с такой формулировки:

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

Строится двоичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
- если число N делится на 3, то к этой записи дописываются её три последние двоичные цифры;
- если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
  Полученная таким образом запись является двоичной записью искомого числа R.
Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 1100100₂ = 100₁₀, а для исходного числа 4₁₀ = 100₂ это число 10011₂ = 19₁₀

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 200.

Открыть задание

Обратите особое внимание, что в заданиях 5 даются примеры! Обязательно проверяйте свои решения на числах из примеров, прежде чем давать ответ на это задание.

Итак, проанализируем условие. Работать мы будем с двоичной системой счисления – уже хорошо, не надо будет писать собственную функцию. Нам нужно будет определить делимость числа N на 3. Причём остаток от деления на 3 лучше выписать в отдельную переменную, так как он нам ещё понадобится: «…остаток от деления умножается на 3…».

Что же, приступим к решению. Первым делом напишем цикл for и создадим диапазон чисел от 1 до 30 (число 30 подобрано опытным путём, при необходимости верхнюю границу можно увеличить):

for N in range(1, 30):

Далее переведём наше число N в двоичную систему счисления. Для этого воспользуемся функционалом f-строк:

N_bin = f'{N:b}'

Найдём остаток от деления этого числа на 3:

remainder = N % 3

Тогда, если число делится на 3 без остатка, то есть он равен 0, будем выполнять действия из пункта а):

if remainder == 0:
        N_bin += N_bin[-3:]

В противном случае, если остаток не равен 0, то умножаем его на 3 и переводим через f-строку в двоичную систему:

else:
N_bin += f'{(remainder * 3):b}’

Осталось лишь перевести результат выполнения одного из условий в десятичную систему – это и будет искомое число R:

R = int(N_bin, 2)

В целом, задание почти решено. Но давайте для начала проверим наш алгоритм на числах из условия. Для этого воспользуемся условной конструкцией, в которой приравняем число N к 12 или 4 и выведем результат работы программы – R. По условию мы ожидаем увидеть значения 100 и 19, соответственно:

for N in range(1, 30):
    # Двоичная запись числа N
    N_bin = f'{N:b}'
    # Остаток от деления на 3
    remainder = N % 3
    if remainder == 0:
        # Дописываем 3 последние цифры
        N_bin += N_bin[-3:]
    else:
        # Остаток * 3 и переводится в 2-чную
        N_bin += f'{(remainder * 3):b}'
    # Результат переводится в 10-чную
    R = int(N_bin, 2)
    # Временная проверка алгоритма
    if N == 12 or N == 4:
        print(R)

Запускаем наш код и видим на экране два числа: 19 и 100. То есть мы все сделали верно и получили ожидаемые числа.

Теперь можем завершить нашу программу для получения ответа на задание. С помощью всё того же условного оператора определим момент, в который число R станет не меньше 200. Как только это неравенство выполнится – выведем исходное число N и завершим работу цикла:

if R >= 200:
    print(N)
    break

Весь наш код будет выглядеть так:

for N in range(1, 30):
    # Двоичная запись числа N
    N_bin = f'{N:b}'
    # Остаток от деления на 3
    remainder = N % 3
    if remainder == 0:
        # Дописываем 3 последние цифры
        N_bin += N_bin[-3:]
    else:
        # Остаток * 3 и переводится в 2-чную
        N_bin += f'{(remainder * 3):b}'
    # Результат переводится в 10-чную
    R = int(N_bin, 2)

    # Число R, не меньшее 200
    if R >= 200:
        print(N)
        break

В результате работы программы получаем число 26. Оно и будет ответом на это задание.

Пример 2

Следующим рассмотрим задание с такой формулировкой:

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

Строится троичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
- если число N делится на 3, то слева к двоичной записи числа N приписывается «1», а справа «02»;
- если число N на 3 не делится, то остаток от деления на 3 умножается на 4, переводится в троичную запись и дописывается в конец полученной ранее двоичной записи числа N.
  Полученная таким образом запись является троичной записью искомого числа R.
Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 11₁₀ = 102₃ результатом является число 10222₃ = 107₁₀, а для исходного числа 12₁₀ = 110₃ это число 111002₃ = 353₁₀

Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 100.

Открыть задание

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

# Перевод в 3-чную систему
def to_ternary(num):
    result = ''
    while num:
        result += str(num % 3)
        num //= 3
    return result[::-1]

Теперь, поскольку нам нужно найти максимальное значение N, в цикле будем перебирать натуральные числа «перевёрнутого» диапазона от 1 до 20 (точнее от 19 до 1):

for N in range(1, 20)[::-1]:

Строим троичную запись натурального числа N:

N_tern = to_ternary(N)

Всё так же находим остаток от деления на 3:

remainder = N % 3

Условие будет всё тем же, что и в прошлом задании – если остаток равен нулю, то выполняем действия из пункта а):

if remainder == 0:
    # Приписываем слева 1, справа 02
    N_tern = '1' + N_tern + '02'

Иначе умножаем остаток на 4 и переводим в троичную систему:

else:
    # Остаток * 4 и переводится в 3-чную
    N_tern += to_ternary(remainder * 4)

Осталось перевести R в десятичную систему и проверить наш алгоритм на числах из условия:

R = int(N_tern, 3)
# Временная проверка
if N == 11 or N == 12:
    print(R)

Весь код у нас записывается так:

# Перевод в 3-чную систему
def to_ternary(num):
    result = ''
    while num:
        result += str(num % 3)
        num //= 3
    return result[::-1]

# Ищем максимальное N
for N in range(1, 20)[::-1]:
    # Троичная запись числа N
    N_tern = to_ternary(N)
    # Остаток от деления на 3
    remainder = N % 3
    if remainder == 0:
        # Приписываем слева 1, справа 02
        N_tern = '1' + N_tern + '02'
    else:
        # Остаток * 4 и переводится в 3-чную
        N_tern += to_ternary(remainder * 4)
    # Результат переводится в 10-чную
    R = int(N_tern, 3)
    # Временная проверка
    if N == 11 or N == 12:
        print(R)

Запускаем его и получаем два числа: 353 и 107, которые совпадают с теми, что даны в условии. Значит, программа написана верно, можем дописывать последнее условие. Итоговый код выглядит следующим образом:

# Перевод в 3-чную систему
def to_ternary(num):
    result = ''
    while num:
        result += str(num % 3)
        num //= 3
    return result[::-1]

# Ищем максимальное N
for N in range(1, 20)[::-1]:
    # Троичная запись числа N
    N_tern = to_ternary(N)
    # Остаток от деления на 3
    remainder = N % 3
    if remainder == 0:
        # Приписываем слева 1, справа 02
        N_tern = '1' + N_tern + '02'
    else:
        # Остаток * 4 и переводится в 3-чную
        N_tern += to_ternary(remainder * 4)
    # Результат переводится в 10-чную
    R = int(N_tern, 3)
    # Число R, меньшее 100
    if R < 100:
        print(N)
        break

Запускаем его и получаем ответ на это задание – число 10.

Пример 3

Разберём ещё одно задание:

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

Из числа N вычитается остаток от деления N на 4
Строится двоичная запись полученного результата
К этой записи дописываются справа ещё два разряда по следующему правилу:
- складываются все цифры построенной двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
- над этой записью проводятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Результат переводится в десятичную систему и выводится на экран.

Полученная таким образом запись является двоичной записью искомого числа R.

Укажите такое наибольшее N, для которого результат работы данного алгоритма меньше числа 47.

В ответе это число запишите в десятичной системе счисления.

Открыть задание

Как вы могли заметить, эта формулировка немного отличается от двух предыдущих. Это же отразится и на решении.

Давайте по порядку. Цикл у нас стандартный с «перевёрнутым» диапазоном для поиска максимального N:

for N in range(1, 20)[::-1]:

Теперь в отдельной переменной сохраним результат первого пункта алгоритма: «из числа N вычитается остаток от деления N на 4»:

N_1 = N - N % 4

Переведём число N_1 в двоичную систему:

N_bin = f'{N_1:b}'

И дальше есть несколько способов записать нужные действия. Тут снова распишем все подробно и по порядку:

У нас двоичное число N_bin записано в виде строки
Чтобы сложить все цифры этого числа, их нужно сначала перевести в целые числа. Для этого применим функцию int() к каждому элементу строки N_bin с помощью функции map(): map(int, N_bin)
Результат работы map() теперь можно передать в функцию sum(), которая вернёт сумму всех цифр исходного числа N_bin
Найти остаток от деления несложно: sum(map(int, N_bin)) % 2
Но, чтобы дописать этот остаток к исходному числу N_bin, нужно перевести его в строчный тип данных: str(sum(map(int, N_bin)) % 2)
Теперь уже можно дописать в конце N_bin полученное значение: N_bin += str(sum(map(int, N_bin)) % 2)

Разберём простой пример, чтобы лучше понять только этот шаг алгоритма. Представим, что двоичная запись N_bin равна 10011, и последовательно выполним каждое действие с выводом результата на экран:

N_bin = '10011'
print(N_bin)
print(*map(int, N_bin))
print(sum(map(int, N_bin)))
print(sum(map(int, N_bin)) % 2)
print(str(sum(map(int, N_bin)) % 2))
N_bin+=str(sum(map(int, N_bin)) % 2)
print(N_bin)

>>>10011
>>>1 0 0 1 1
>>>3
>>>1
>>>1
>>>100111

То есть к исходной записи 10011 приписали остаток от деления суммы его цифр на 2 и получили число 100111, как это и было описано в условии.

Вернёмся к решению. На данный момент наша программа состоит из трех строчек:

for N in range(1, 20)[::-1]:
    N_1 = N - N % 4
    N_bin = f'{N_1:b}'

Добавим к ней только что разобранную запись:

for N in range(1, 20)[::-1]:
    N_1 = N - N % 4
    N_bin = f'{N_1:b}'
    N_bin += str(sum(map(int, N_bin)) % 2)

И далее в условии говорится: «над этой записью проводятся те же действия». Что же, не будем мудрить и просто продублируем последнюю строчку:

for N in range(1, 20)[::-1]:
    N_1 = N - N % 4
    N_bin = f'{N_1:b}'
    N_bin += str(sum(map(int, N_bin)) % 2)
    N_bin += str(sum(map(int, N_bin)) % 2)

Теперь переводим получившееся число N_bin в десятичную систему и проверяем, в какой момент это число будет меньше 47. После чего выводим исходное N и останавливаем программу. Весь код у нас будет таким:

for N in range(1, 20)[::-1]:
    # Вычитается остаток от деления на 4
    N_1 = N - N % 4
    # Двоичная запись числа N_1
    N_bin = f'{N_1:b}'
    # Складываются все цифры 2-чной записи,
    # остаток от деления суммы на 2
    # дописывается в конец
    N_bin += str(sum(map(int, N_bin)) % 2)
    # Проводятся те же действия
    N_bin += str(sum(map(int, N_bin)) % 2)
    # Результат переводится в 10-чную
    R = int(N_bin, 2)
    
    # Число R, меньшее 47
    if R < 47:
        print(N)
        break

После успешного завершения программы получаем ответ на это задание – число 11.

На этом мы завершим разбор алгоритма решения первого типа задания 5. В следующей же статье научимся решать задания второго типа.

Алгоритм решения задания 5. Часть 1

О задании

Алгоритм решения

Пример 1

Пример 2

Пример 3

Рекомендуемые статьи