Автор статьи: Андрей Рогов
Введение
По правилам экзамена задание № 14 можно решать без компьютера — просто ручкой на бумаге. Предполагается, что решение должно быть аналитическим. Но на практике почти никто так не делает: вычисления довольно сложные, и программа справляется с этим намного быстрее и удобнее.
Большинство необходимых функций уже были рассмотрены в материалах по заданиям 5 и 8. Поэтому здесь сразу будут разобраны примеры решений с использованием Python.
Задача 1. Длинная арифметика
Это задание — одно из самых старых, ещё с тех времён, когда ЕГЭ сдавали без компьютеров, поэтому его действительно можно решить вручную. Тем не менее здесь будет рассматриваться только программный подход. Задача сводится к тому, чтобы перевести число в семеричную систему счисления и посчитать, сколько раз в записи встречается цифра 6.
Есть два похожих способа решения: получить семеричную запись числа и посчитать в ней количество шестерок. Удобнее всего хранить такую запись в виде списка, ведь иногда встречаются системы счисления с основаниями больше десяти — в этом случае обычные строки могут давать некорректный результат.
x = 7 * 49**120 - 6 * 343**65 - 5 * 7**40
s = [] # список для хранения цифр числа
while x > 0:
s = [x % 7] + s # добавляем новый остаток в начало записи
x //= 7
print(s.count(6)) # выводим количество шестерок
В примере реализован алгоритм перевода числа в семеричную систему счисления. Метод count у списков позволяет посчитать, сколько раз в списке встречается нужный элемент. На самом деле хранить всю запись числа необязательно — можно в каждом шаге цикла просто проверять остаток от деления. Такой вариант также отлично работает. Всё это будет показано на примере следующей задачи.
Задача 2. Длинная арифметика с несколькими подходящими цифрами
Остатки, которые больше 9, уже не считаются десятичными цифрами. Чтобы это учесть, можно немного изменить предыдущий алгоритм: добавить сравнение прямо в цикл и убрать использование списка.
x = 2**2048 + 32**102 - 8 * 4**128
k = 0 # счетчик подходящих цифр
while x > 0:
if x % 32 > 9: # если цифра не десятичная
k += 1 # увеличиваем счетчик
x //= 32
print(k) # выводим количество цифр
Такая программа будет использовать меньше памяти, потому что не хранит все цифры числа в списке, но на современных компьютерах это почти не играет роли.
Задача 3. Длинная арифметика с неизвестным числом
В предыдущих заданиях нужно было узнать количество определённых цифр, а здесь это значение уже дано. Зато неизвестна часть выражения. Просто перевести число в другую систему счисления недостаточно — тут нужно выяснить, как значение x влияет на количество нулей в семеричной записи.
И хотя задачу можно решить аналитически, проще воспользоваться компьютером: перебрать все возможные значения x и найти нужный вариант. Для удобства и понятности кода отдельно оформим функцию, которая считает количество нулей.
def count0(x):
k = 0 # счетчик подходящих цифр
while x > 0:
if x % 7 == 0:
k += 1 # увеличиваем счетчик
x //= 7
return k
for x in range(2300, 0, -1): # по убыванию, поскольку ищем максимальное значение
a = 7**350 + 7**150 - x
if count0(a) == 200:
print(x)
break
Выносить часть кода в отдельную функцию необязательно, но это помогает лучше разделять различные части программы. По сути, эта задача — усложнённая версия первых двух: здесь нужно не только посчитать цифры, но и перебрать возможные значения переменной.
Задача 4. Выражение с неизвестными цифрами
В этой задаче тип перевода совсем другой — теперь нужно переводить числа не из десятичной системы, а наоборот, в неё. С этим отлично справляется функция int, если основание системы счисления не больше 36. Если же основание больше, придётся использовать арифметические методы.
Рассмотрим несколько вариантов решения. В первом из них перебираются все возможные цифры 29-ричной системы счисления. Это десять обычных цифр и ещё девятнадцать латинских букв. Чтобы записать буквы, нужно либо помнить их порядок в алфавите, либо найти другой способ получить нужные символы. Один из удобных вариантов — импортировать из модуля string переменную ascii_letters, в которой содержатся буквы латинского алфавита сразу в обоих регистрах.
from string import ascii_letters
print(ascii_letters)
>>> 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
Есть и другой вариант — можно просто отсортировать все буквы, которые вводят с клавиатуры.
print(''.join(sorted('qwertyuiopasdfghjklzxcvbnm')))
>>> 'abcdefghijklmnopqrstuvwxyz'
Есть и более необычный способ — создать в текстовом редакторе нумерованный список, выбрав для нумерации буквы вместо цифр.
Девятнадцать букв заканчиваются на букве S. Чтобы убедиться, что весь нужный алфавит выбран правильно, можно просто проверить длину получившейся строки.
len('0123456789abcdefghijklmnopqrs')
>>> 29
Теперь подставим все значения x в выражение. Это удобно делать либо через простое склеивание строк, либо с помощью f-строк. После этого выражение переводится в десятичную систему счисления, и производится вычисление. Если результат делится на 28 без остатка, можно вывести и подходящую цифру, и само частное.
for x in '0123456789abcdefghijklmnopqrs':
a = int('923' + x + '874', 29) + int('524' + x + '6152', 29)
# a = int(f'923{x}874', 29) + int('524{x}6152', 29)
if a % 28 == 0:
print(x, a // 28)
В результате видим две строки.
d 3318831885
r 3319197720
В итоге условию подходят две цифры. Наибольшей из них будет вторая, поэтому в ответ впишется частное 3319197720.
Теперь программа будет работать и с системами счисления, где основание больше 36. Стоит помнить, что для цифр с числовым значением выше 36 не существует общепринятых обозначений, так что все символы числа всё равно будут в рамках 36-ричной системы.
Добавим функцию для перевода такого числа в десятичную систему. Внутри неё у каждого разряда будет свой «вес», который хранится в переменной k. При переходе к следующему разряду этот вес просто умножается на основание системы.
def to10(x, b):
k = 1
a = 0
for c in x[::-1]:
a += int(c, 36) * k
k *= b
return a
for x in '0123456789abcdefghijklmnopqrs':
a = to10('923' + x + '874', 29) + to10('524' + x + '6152', 29)
# a = to10(f'923{x}874', 29) + to10('524{x}6152', 29)
if a % 28 == 0:
print(x, a // 28)
Вес каждого разряда можно вычислять и вручную. Для этого каждый раз нужно брать цифру и умножать её на основание системы счисления в нужной степени.
for x in '0123456789abcdefghijklmnopqrs':
a1 = 9*29**6 + 2*29**5 + 3*29**4 + int(x, 29)*29**3 + 8*29**2 + 7*29**1 + 4*29**0
a2 = 5*29**7 + 2*29**6 + 4*29**5 + int(x, 29)*29**4 + 6*29**3 + 1*29**2 + 5*29**1 + 2*29**0
a = a1 + a2
if a % 28 == 0:
print(x, a // 28)
Вот несколько частых ошибок, которые встречаются в этом задании:
- Опечатки в числах. Важно аккуратно переписывать числа из условия, чтобы избежать лишних проблем.
- Неправильный алгоритм перевода числа в нужную систему.
- Использование строк для хранения чисел после перевода — это иногда приводит к неверным результатам.
Заключение
Программный подход заметно облегчает решение задач, связанных с системами счисления. В Python есть все нужные инструменты для работы с числами в разных системах. Использование функций делает код более понятным и удобным для проверки.
Умение решать задачи на системы счисления с помощью программ — важный навык для успешной сдачи ЕГЭ по информатике. Методы, рассмотренные в этой статье, позволяют легко решать задачи на перевод чисел, подсчёт цифр и поиск неизвестных значений.
Регулярная тренировка и разбор типовых заданий помогут быстро освоиться с задачей № 14. При подготовке стоит попробовать разные способы решения и обязательно порешать подборки практических заданий: