Навигация по странице
Тип 2
В прошлой статье мы уже научились работать с различными системами счисления на языке Python и освоили алгоритм решения первого типа 5 заданий ЕГЭ по информатике.
Теперь же приступим к разбору алгоритма решения второго типа этих заданий. Напомним, что в прошлый раз нам необходимо было найти исходное число N, подходящее под условия. В заданиях второго типа от нас требуется вывести уже результат работы алгоритма – число R – при некотором условии для исходного числа N, поступающего на вход алгоритма.
Давайте рассмотрим, как этот момент отразится на алгоритме решения.
Алгоритм решения
Как и в заданиях прошлого типа, от нас потребуется вывести максимальное или минимальное значение некоторого числа R. Вот только в случае с исходным числом мы могли просто «перевернуть» диапазон натуральных чисел в цикле. Но для определения числа R такой способ не сработает.
Все дело в том, что никто не гарантирует линейное поведение заданного алгоритма! Иными словами, у нас нет абсолютно никакой уверенности, что минимальное R будет в начале работы алгоритма, а максимальное – в конце.
Давайте убедимся в этом на реальном примере. Рассмотрим такую формулировку:
«Строится двоичная запись натурального числа N.
Далее эта запись обрабатывается по следующему правилу:
- если число чётное, то к двоичной записи числа слева дописывается 10;
- если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Результат переводится в десятичную систему. Нужно найти минимальное R, при условии, что N меньше 10»
Пока не будем расписывать программное решение, обратимся только к результатам работы такого алгоритма. При передачи в него значений от 1 до 9, числа R будут следующими: 13, 10, 29, 20, 53, 22, 61, 40, 101.
Как нетрудно догадаться, минимальным здесь является число 10. Но находится оно совсем не на первой позиции. Как же быть в таком случае?
Решение очевидно – нужно сохранять все результаты работы алгоритма в отдельный список. Сделать это несложно, достаточно к нашему привычному циклу добавить буквально две строчки: переменную res с пустым списком в начале и внутри цикла добавление значения R в res методом append.
res = []
for N in range(1, верхняя_граница):
# Основной цикл с условиями
# Добавляем результат в список
res.append(R)
Для вывода максимального или минимального значения R воспользуемся встроенными функциями max() и min(), которые применим к списку со всеми значениями R:
# Выводим максимальное значение
print(max(res))
# Выводим минимальное значение
print(min(res))
Это буквально все изменения в типовом алгоритме решения. Давайте скорее его опробуем на реальной задаче.
Пример 1
Начнём сегодня с такой формулировки:
Задание 500
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
- если число чётное, то к двоичной записи числа слева дописывается 10;
- если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 410 = 1002 результатом является число 2010 = 101002, а для исходного числа 510 = 1012 это число 5310 = 1101012.
Укажите максимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не больше 12. В ответе запишите это число в десятичной системе счисления.»
Сразу обратим внимание на условие «N не больше 12». Для его выполнения нам достаточно просто указать диапазон натуральных чисел от 1 до 12 (включительно): range(1, 13).
С правилами, по которым работает алгоритм, мы уже знакомились ранее. В них нет ничего необычного для нас: нужно определить чётность числа и, в зависимости от неё, дописывать значения к числу. Давайте приступим к написанию кода.
Сначала определим переменную для результатов работы алгоритма:
res = []
Далее создадим цикл с рассмотренным выше диапазоном:
for N in range(1, 13):
Построим двоичную запись для каждого числа:
N_bin = f'{N:b}'
Далее, если число чётное, то будем слева двоичной записи дописывать 10, а в противном случае слева 1 и справа 01. Распишем все это на языке Python:
# Если число чётное
if N % 2 == 0:
# Дописываем слева 10
N_bin = '10' + N_bin
# Иначе (если нечётное)
else:
# Слева 1 справа 01
N_bin = '1' + N_bin + '01'
Осталось лишь перевести результат работы алгоритма в десятичную систему счисления. Это и будет наше число R:
R = int(N_bin, 2)
Теперь проверим наш алгоритм на примерах из формулировки задания: подставим в качестве N числа 4 и 5 и выведем на экран результат:
res = []
# Сразу укажем, что N не больше 12
for N in range(1, 13):
# Строим двоичную запись
N_bin = f'{N:b}'
# Если число чётное
if N % 2 == 0:
# Дописываем слева 10
N_bin = '10' + N_bin
# Иначе (если нечётное)
else:
# Слева 1 справа 01
N_bin = '1' + N_bin + '01'
# Переводим в десятичную
R = int(N_bin, 2)
# Временная проверка алгоритма
if N == 4 or N == 5:
print(R)
В итоге видим числа 20 и 53, которые совпадают с теми, что даны в условии. Значит, программа написана верно, можем добавлять каждое значение R в список и выводить на экран максимальное число из этого списка. Итоговый код у нас выглядит так:
res = []
# Сразу укажем, что N не больше 12
for N in range(1, 13):
# Строим двоичную запись
N_bin = f'{N:b}'
# Если число чётное
if N % 2 == 0:
# Дописываем слева 10
N_bin = '10' + N_bin
# Иначе (если нечётное)
else:
# Слева 1 справа 01
N_bin = '1' + N_bin + '01'
# Переводим в десятичную
R = int(N_bin, 2)
# Добавляем результат в список
res.append(R)
# Выводим максимальное значение
print(max(res))
А в результате его работы получаем число 109, которое и будет ответом на это задание.
Пример 2
Теперь рассмотрим 5 задание с такой формулировкой:
Задание 501
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится троичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
- если число N делится на 3, то к этой записи дописываются две последние троичные цифры;
- если число N на 3 не делится, то вычисляется сумма цифр полученной троичной записи, эта сумма переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого
числа R.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1110 = 1023 результатом является число 102103 = 10210, а для исходного числа 1210 = 1103 это число 110103 = 11110.
Укажите минимальное чётное число R, большее 220, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления»
Нам предстоит работа с троичной системой счисления. Вспомним функцию для перевода чисел в троичную систему из прошлой статьи:
def to_ternary(num):
result = ''
while num:
result += str(num % 3)
num //= 3
return result[::-1]
Дальше решение будет типовым: создаём переменную для сохранения результатов, цикл натуральных чисел до 250 и строим троичную запись:
res = []
for N in range(1, 250):
N_tern = to_ternary(N)
Проверяем делимость на 3 и дописываем две последние цифры в случае истинности условия, либо дописываем сумму цифр в троичной системе в противоположном случае. Работу с суммой цифр мы подробно разобрали в предыдущей статье, останавливаться на этом не будем.
# Если число делится на 3
if N % 3 == 0:
# 2 последние цифры
N_tern += N_tern[-2:]
# Если не делится
else:
# Сумма цифр
sum_d = sum(map(int, N_tern))
# Сумму в 3-чную
sum_d = to_ternary(sum_d)
N_tern += sum_d
Далее обойдёмся без проверок значений из условия. Сразу переведём полученное после работы алгоритма число в десятичную систему и далее запишем условие для определения подходящего числа.
# Переводим в десятичную
R = int(N_tern, 3)
Это число должно быть, во-первых, чётным, во-вторых, большим 220. Отразим это в условии:
# Формируем ответ
if R % 2 ==0 and R > 220:
# Добавляем результат в список
res.append(R)
Осталось лишь вывести минимальное значение из списка на экран. Итоговый код для решения этого задания будет такой:
def to_ternary(num):
result = ''
while num:
result += str(num % 3)
num //= 3
return result[::-1]
res = []
for N in range(1, 250):
# Строим троичную запись
N_tern = to_ternary(N)
# Если число делится на 3
if N % 3 == 0:
# 2 последние цифры
N_tern += N_tern[-2:]
# Если не делится
else:
# Сумма цифр
sum_d = sum(map(int, N_tern))
# Сумму в 3-чную
sum_d = to_ternary(sum_d)
N_tern += sum_d
# Переводим в десятичную
R = int(N_tern, 3)
# Формируем ответ
if R % 2 ==0 and R > 220:
# Добавляем результат в список
res.append(R)
# Выводим минимальное значение
print(min(res))
Да, здесь можно было воспользоваться оператором break для остановки цикла и сразу вывести первое подходящее R. Но мы не будем отходить от типового решения. К тому же, в следующем примере вы сами убедитесь в том, что всегда лучше сохранять результаты в список!
В любом случае, после завершения работы программы, мы готовы дать ответ на это задание – число 222.
Пример 3
В заключении рассмотрим такую формулировку:
Задание 513
«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
a) если число N делится на 3, то к этой записи дописываются две последние троичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1110 = 1023 результатом является число 1021013 = 30710, а для исходного числа 1210 = 1103 это число 110103 = 11110.
Укажите минимальное число R, большее 150, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.»
Помните, что мы только что говорили про сохранения результатов в список? Из примера в условии мы уже можем увидеть, что алгоритм выдаёт значения не линейно: для числа 11 результатом является 307, а для 12 – 111. То есть итоговые значения идут не в строгом порядке возрастания!
В своём решении это задание похоже на второй пример из прошлой статьи. Так что подробно останавливаться на разборе кода в этот раз не будем. Запишем его следующим образом:
def to_ternary(num):
result = ''
while num:
result += str(num % 3)
num //= 3
return result[::-1]
res = []
for N in range(1, 100):
# Строим троичную запись
N_tern = to_ternary(N)
# Остаток от деления на 3
remainder = N % 3
if remainder == 0:
# Дописываем 2 последние цифры
N_tern += N_tern[-2:]
else:
# Остаток * 5 и переводится в 3-чную
N_tern += to_ternary(remainder * 5)
# Переводим в десятичную
R = int(N_tern, 3)
# Формируем ответ
if R > 150:
res.append(R)
# Выводим минимальное значение
print(min(res))
В результате работы программы на экран выведется минимальное число из списка – 162. Его мы и запишем в ответ на это задание.