zad5

О задании

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

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

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

Важную роль в выполнении задания 5 занимает перевод чисел из десятичной системы счисления в другие. При этом, если для перевода в стандартные системы счисления вроде двоичной, восьмеричной и шестнадцатеричной существует уже реализованный в Python функционал, то для перевода в системы счисления с иными основания придётся создавать собственные алгоритмы.

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

Системы счисления

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

История возникновения систем счисления

Простейшие системы счисления существовали ещё в древности. Первоначально люди использовали системы счисления, основанные на количестве пальцев, таких как десятичная система, в которой числа представляются с помощью 10 символов — от 0 до 9.

В Древнем Египте и Месопотамии уже использовались различные системы счисления для ведения учёта и проведения торговых операций.

Древние египтяне использовали систему счисления, которая также не была позиционной. Они использовали различные символы для представления разных степеней числа 10. Например, для числа 10 использовался символ, похожий на палочку, для 100 — символ, похожий на моток ниток и т. д. Эта система позволяла эффективно работать с большими числами, однако её ограниченность заключалась в трудности выполнения арифметических операций.

Одна из самых интересных и необычных систем счисления — это система с основанием 60, использовавшаяся в Древнем Вавилоне.

Шестидесятеричная система оставила значительное наследие в нашей культуре, например, её основу мы видим в измерении времени (60 секунд в минуте, 60 минут в часе) и в круге (360 градусов). Эта система, вероятно, была удобна для астрономических наблюдений и расчётов, так как 60 имеет много делителей, что облегчало деление и вычисления.

В Древнем Риме была разработана уникальная система счисления, основанная на символах, которые были комбинированы для представления чисел. В отличие от позиционных систем, где значение цифры зависит от её места в числе, римские числа были аддитивными (например, VIII = 5 + 3).

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

Однако с развитием математики и науки, необходимость в более сложных системах счисления продолжала возрастать. Так, в Средневековье была разработана двоичная (основанная на двух символах — 0 и 1) система счисления, которая оказалась крайне полезной для вычислений с использованием механических устройств, таких как абаки и счётные машины.

С развитием компьютеров в 20 веке системы счисления, особенно двоичная система, стали основой для работы цифровых вычислительных машин. Именно двоичная система, которая использует только два символа — 0 и 1, — идеально подходит для представления информации в электронных устройствах, где каждый элемент может быть в одном из двух состояний: включён или выключен.

Для чего создавались системы счисления

Основной целью создания систем счисления было упрощение записи и вычислений. Ранее люди использовали различные методы подсчёта — например, палочки, камни или специальные знаки. Но с развитием науки, а особенно с развитием вычислительных машин, возникла потребность в стандартизации систем счисления для более точных и быстрых вычислений.

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

Системы счисления также стали важными для развития различных технологий. Шестнадцатеричная система (основание 16) используется для удобства представления данных в программировании. Например, она часто применяется для представления адресов в памяти компьютера, поскольку её основа (16) подходит для краткой записи больших чисел, что облегчает работу программистов.

Современные системы счисления

Десятичная система (основание 10)

Эта система стала естественной для человечества благодаря тому, что у нас десять пальцев на руках. В ней используются цифры от 0 до 9, а каждый следующий разряд увеличивает значение в десять раз. Она остаётся основной в повседневной жизни, торговле, науке и большинстве расчётов.

Двоичная система (основание 2)

Фундамент современной вычислительной техники. Использует только две цифры — 0 и 1, что идеально соответствует природе электронных схем, где сигнал может быть либо включен, либо выключен. Именно эта система лежит в основе работы всех компьютеров и цифровых устройств.

Восьмеричная система (основание 8)

Исторически использовалась программистами как более компактная альтернатива двоичной системе. Каждая восьмеричная цифра представляет ровно три двоичных разряда, что делает её удобной для работы с машинным кодом. Хотя сегодня она используется реже, её всё ещё можно встретить в некоторых Unix-системах при работе с правами доступа к файлам.

Шестнадцатеричная система (основание 16)

Самая популярная система для программистов после двоичной. Использует цифры от 0 до 9 и буквы A-F. Каждый шестнадцатеричный символ представляет ровно четыре двоичных разряда, что делает её особенно удобной при работе с компьютерной памятью, отладке программ и написании низкоуровневого кода.

Цвета в HTML, CSS также обозначаются шестнадцатеричными значениями, например, #FF5733 для указания RGB-цветов. А в языках программирования и отладчиках адреса в памяти отображаются в шестнадцатеричном формате, например, 0x7FFE23A8.

Перевод чисел в различные системамы счисления

Ручной метод

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

Например, чтобы перевести число 42 в двоичную систему:

42 ÷ 2 = 21 (остаток 0)

21 ÷ 2 = 10 (остаток 1)

10 ÷ 2 = 5 (остаток 0)

5 ÷ 2 = 2 (остаток 1)

2 ÷ 2 = 1 (остаток 0)

1 ÷ 2 = 0 (остаток 1)

Читая остатки снизу вверх, получаем число 101010.

Аналогично работает и алгоритм перевода числа из десятичной системы счисления в любую другую с основанием от 2 до 36.

Алгоритм перевода

  1. Определить основание новой системы счисления
    Выберите основание N, в которое нужно перевести число. N должно находиться в диапазоне от 2 до 36.
  2. Разделить десятичное число на основание N
    Повторяйте деление числа на N, записывая остаток от каждого деления.
  3. Записать остатки в обратном порядке
    Остатки, полученные при делении, записываются снизу вверх (или в обратном порядке), начиная с последнего остатка.
  4. Для оснований больше 10 использовать символы
    Если основание N>10, остатки, превышающие 9, заменяются на буквы латинского алфавита:

    • 10→A
    • 11→B1
    • 12→C, и так далее, до 35→Z
  5. Результат
    Запишите все остатки в последовательности, начиная с последнего полученного при делении. Это и будет число в новой системе счисления.

Для примера, переведём число 78 в систему счисления с основанием 8 (восьмеричная система)

  1. Делим 78 на 8:
    78÷8=9, остаток 6
    9÷8=1, остаток 1
    1÷8=0, остаток 1
  2. Записываем остатки в обратном порядке: 116.

Перевод в различные системы счисления в языке Python

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

Например, для перевода числа, представленного в виде строки, из любой системы счисления с основанием от 2 до 36 в десятичную используется функция int().

Функция int() имеет следующий синтаксис:

int(number_string, base)

  • number_string — строка, представляющая число в исходной системе счисления
  • base — основание исходной системы счисления (целое число от 2 до 36)

Например, переведём число «ff» из шестнадцатеричной системы счисления в десятичную:

x = 'ff'
print(int(x, 16))
>>>255

С переводом из десятичной в другие системы все несколько сложнее. В Python есть три встроенные функции для перевода в базовые системы счисления: двоичную (bin()), восьмеричную (oct()) и шестнадцатеричную (hex()). Для перевода в любые другие системы придётся самостоятельно реализовывать рассмотренный выше алгоритм перевода.

Все три перечисленный функции — bin(), oct() и hex() — принимают целое число и преобразуют его в нужную систему счисления, возвращая результат в виде строки с префиксом 0b, 0o, 0x, соответственно.

Ниже приведён пример перевода числа 42 в двоичную, восьмеричную и шестнадцатеричную системы:

x = 42
print(bin(x))
print(oct(x))
print(hex(x))
>>> 0b101010
>>> 0o52
>>> 0x2a

Избавиться от префикса можно используя операцию среза [2:].

x = 42
print(bin(x)[2:])
print(oct(x)[2:])
print(hex(x)[2:])
>>> 101010
>>> 52
>>> 2a

В эти же системы счисления можно осуществить перевод использую функцию format() или f-строки.

Функция format() используется для форматирования строк. Она предоставляет удобный способ представления данных в различных форматах, включая перевод чисел в разные системы счисления. При использовании данной функции, получаемые строки не содержат префикса.

Её синтаксис следующий:

format(value, format_spec)

  • value — значение, которое нужно отформатировать (например, число)
  • format_spec — формат спецификатора — строка, задающая способ

Форматы спецификатора могут быть следующими:

  1. 'b' — Двоичное представление
  2. 'o' — Восьмеричное представление
  3. 'x' — Шестнадцатеричное (строчные)
  4. 'X' — Шестнадцатеричное (заглавные)
  5. 'd' — Десятичное представление (по умолчанию)

Переведём число 42 с помощью функции format() в восьмеричную систему счисления:

x = 42
x_oct = format(x, 'o')
print(x_oct)
>>>52

Более современным и удобным способом форматирования в Python является использование f-строк. f-строки или же форматированные строковые литералы позволяют вставлять выражения Python внутри строковых литералов, используя фигурные скобки { }. В этом методе, перед форматируемой строкой ставится символ f, а внутри фигурных скобок пишутся имена переменных и спецификаторы формата.

f-строки имеют следующий синтаксис:

f"{value:format_spec}"

  • value — значение, которое нужно вставить в строку
  • format_spec — формат спецификатора — строка, задающая способ отображения значения

Спецификаторы формата для систем счисления следующие:

  • b — двоичная система
  • o — восьмеричная система
  • x или X — шестнадцатеричная система

Используются после двоеточия: f"{число:b}". В примере ниже переведём число 42 в различные системы счисления:

x = 42
print(f'{x:b}')
print(f'{x:o}')
print(f'{x:x}')
print(f'{x:X}')
>>>101010
>>>52
>>>2a
>>>2A

Теперь давайте напишем собственную функцию, которая позволит переводить числа в любую систему счисления с основанием от 2 до 36.

Вспомним, что алфавит систем с основанием выше 10 содержит буквы латинского алфавита. Следовательно, нам необходимо создать алфавит, который содержит в себе цифры от 0 до 9 и все буквы латинского алфавита.

Можно перечислить все символы вручную, но надёжнее будет воспользоваться константами digits и ascii_uppercase из модуля string.

Импортируем константы из модуля:

from string import digits, ascii_uppercase

Сформируем алфавит для любой системы счисления:

alph = digits + ascii_uppercase

Теперь реализуем алгоритм перевода:

while num:
    result += alph[num % base]
    num //= base

Этот цикл реализует метод последовательного деления:

  • num % base даёт остаток от деления (индекс для выбора символа из алфавита alph)
  • num //= base выполняет целочисленное деление на основание
  • Процесс продолжается, пока число не станет равным нулю

Теперь оборачиваем цикл в функцию и выводим результат в обратном порядке. В итоге наша функция для перевода числа в любую систему счисления с основанием от 2 до 36 будет выглядеть так:

from string import digits, ascii_uppercase


def convert(num, base):
    alph = digits + ascii_uppercase
    result = ''
    while num:
        result += alph[num % base]
        num //= base
    return result[::-1]

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

def to_ternary(num):
    result = ''
    while num:
        result += str(num % 3)
        num //= 3
    return result[::-1]

Алгоритм решения задания 5

Обычно, алгоритм решения задания 5 заключается в том, что сначала определяем систему счисления, с которой будем работать. Если для перевода в эту систему нет встроенной функции Python, то пишем свою.

Далее в цикле поочерёдно перебираем числовые значения N и пишем условия, которые сформулированы в задании. Так, при наличии условия «если число делится на 3, то…» будем проверять остаток от деления переменной-счётчика цикла N на 3. Если он равен нулю, то выполняем операции, написанные после «то». И так продолжаем до тех пор, пока не будет реализован весь алгоритм.

Последним шагом нашей программы будет реализация условия для формирования ответа на задание. Например, решение при наличии такой формулировки: «Укажите минимальное чётное число R, большее 220, которое может быть получено с помощью описанного алгоритма».

В таком случае, сначала сформируем такое условие:

if R % 2 == 0 and R > 220

И внутри этой условной конструкции будем выводить значение для ответа.

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

Пример 1

Задание 500

«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число чётное, то к двоичной записи числа слева дописывается 10;
б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 410 = 1002 результатом является число 2010 = 101002, а для исходного числа 510 = 1012 это число 5310 = 1101012.
Укажите максимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не больше 12. В ответе запишите это число в десятичной системе счисления»

Для начала давайте составим алгоритм из условия задания и проверим его с числами 4 и 5.

for N in range(1, 13):
    # Строим двоичную запись
    R = f'{N:b}'
    # Если число чётное
    if N % 2 == 0:
        # Дописываем слева 10
        R = '10' + R
    # Иначе (если нечётное)
    else:
        # Слева 1 справа 01
        R = '1' + R + '01'
    # Переводим в десятичную
    R = int(R, 2)
    # Проверим алгоритм
    if N == 4 or N == 5:
        print(N, R)
>>>4 20
>>>5 53

Видим, что для числа 4 результатом является 20, а для 5 — 53, как и было указано в условии. Следовательно, дописываем нашу программу для получения ответа.

res = []
# Сразу укажем, что N не больше 12
for N in range(1, 13):
    # Строим двоичную запись
    R = f'{N:b}'
    # Если число чётное
    if N % 2 == 0:
        # Дописываем слева 10
        R = '10' + R
    # Иначе (если нечётное)
    else:
        # Слева 1 справа 01
        R = '1' + R + '01'
    # Переводим в десятичную
    R = int(R, 2)
    # Формируем ответ
    res.append(R)

print(max(res))

Здесь мы все возможные R помещаем в список res. А условие «N не больше 12» у нас учитывается в функции range(), которая формирует последовательность от 1 до 12 включительно. В конце выводится максимальное значение из списка res — 109. Это и будет ответ на данное задание.

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

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

# Генератор двоичных чисел
def bin_digits():
    n = 1
    while True:
        yield f'{n:b}'
        n += 1


res = []
# Объект генератора
gen = bin_digits()

for N, R in enumerate(gen, start=1):
    # Если число чётное
    if N % 2 == 0:
        # Дописываем слева 10
        R = '10' + R
    # Иначе (если нечётное)
    else:
        # Слева 1 справа 01
        R = '1' + R + '01'
    # Переводим в десятичную
    R = int(R, 2)
    # Формируем ответ
    # Значения N не больше 12
    if N <= 12:
        res.append(R)
    else:
        break

print(max(res))

Пример 2

Задание 501

«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1.    Строится троичная запись числа N.
2.    Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются две последние троичные цифры;
б) если число N на 3 не делится, то вычисляется сумма цифр полученной троичной записи, эта сумма переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
3.    Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1110 = 1023 результатом является число 102103 = 10210, а для исходного числа 1210 = 1103 это число 110103 = 11110.
Укажите минимальное чётное число R, большее 220, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления»

Сначала напишем функцию для перевода числа в троичную систему счисления. Мы её уже разбирали ранее, так что подробно останавливаться на ней не будем.

В этом задании сталкиваемся с формулировкой «сумма цифр полученной записи». Найти сумму цифр строки можно следующим образом:

sum_d = sum(map(int, R))

Здесь мы с помощью функции map() приводим к целому десятичному числу каждый символ строки R, получая тем самым цифры троичной записи. Затем суммируем эти цифры с помощью функции sum().

Давайте составим программу и проверим её на числах из условия.

def to_ternary(num):
    result = ''
    while num:
        result += str(num % 3)
        num //= 3
    return result[::-1]


for N in range(1, 10_000):
    # Строим троичную запись
    R = to_ternary(N)
    # Если число делится на 3
    if N % 3 == 0:
        # 2 последние цифры
        R += R[-2:]
    # Если не делится
    else:
        # Сумма цифр
        sum_d = sum(map(int, R))
        # Сумму в троичную СС
        sum_d = to_ternary(sum_d)
        R += sum_d
    # Переводим в десятичную
    R = int(R, 3)
    # Проверка
    if N == 11 or N == 12:
        print(N, R)
>>>11 102
>>>12 111

Проверка завершилась успешно, теперь дописываем программу и выводим ответ.

def to_ternary(num):
    result = ''
    while num:
        result += str(num % 3)
        num //= 3
    return result[::-1]


res = []

for N in range(1, 10_000):
    # Строим троичную запись
    R = to_ternary(N)
    # Если число делится на 3
    if N % 3 == 0:
        # 2 последние цифры
        R += R[-2:]
    # Если не делится
    else:
        # Сумма цифр
        sum_d = sum(map(int, R))
        # Сумму в троичную СС
        sum_d = to_ternary(sum_d)
        R += sum_d
    # Переводим в десятичную
    R = int(R, 3)
    # Формируем ответ
    if R % 2 == 0 and R > 220:
        res.append(R)
        
print(min(res))

В результате получаем число 222.

Пример 3

Задание 502

«На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится восьмеричная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если количество чётных цифр в записи числа нечётно, то к трём последним разрядам восьмеричной записи справа дописывается 46;
б) если количество чётных цифр в записи числа чётно, то остаток от деления числа на 8 умножается на 5, переводится в восьмеричную запись и дописывается слева.
Полученная таким образом запись является восьмеричной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 12 = 148 результатом является число 14468 = 806, а для исходного числа 777 = 14118 это число 411468 = 16998.
Укажите минимальное число R, которое может быть получено с помощью описанного алгоритма при N не меньшем 80. В ответ запишите это число в десятичной системе счисления»

Здесь мы не будем писать собственную функцию для перевода числа, поскольку в Python уже есть функция oct(). Однако, стоит отметить здесь фразу «количество чётных чисел». Давайте напишем функцию, для вычисления количество чётных чисел в строке.

# Функция для подсчета чётных цифр
def count_evens(num):
    evens = sum([1 for i in num
                 if int(i, 8) % 2 == 0])
    return evens

Здесь мы используем списочное выражение [1 for i in num if int(i, 8) % 2 == 0], которое формирует список из единиц, количество которых равно количеству чётных цифр в строке num.

Давайте подробнее разберем это выражение:

  • for i in num: Проходим по каждой цифре строки num. Например, для num = '36147' это цифры '3', '6', '1', '4', '7'.
  • int(i, 8): Преобразуем каждую восьмеричную цифру i обратно в десятичное число. Например, int('6', 8) вернёт 6, а int('4', 8) вернёт 4.
  • int(i, 8) % 2 == 0: Проверяем, является ли преобразованная цифра чётной.
  • [1 for i in r if ...]: Если условие чётности выполняется, добавляем 1 в список.

В итоге суммируем все единицы из списка с помощью функции sum() и возвращаем оператором return.

Составляем программу и убеждаемся в её правильности, подставляя значения из условия:

# Функция для подсчета чётных цифр
def count_evens(num):
    evens = sum([1 for i in num
                 if int(i, 8) % 2 == 0])
    return evens


for N in range(1, 10_000):
    # Строим 8-ричную запись
    R = f'{N:o}'
    # Если кол-во нечётно
    if count_evens(R) % 2:
        R = R[-3:] + '46'
    # Если кол-во чётно
    else:
        R = f'{(N % 8 * 5):o}' + R
    # Переводим в десятичную
    R = int(R, 8)
    # Проверка
    if N == 12 or N == 777:
        print(N, R)
>>>12 806
>>>777 16998

Программа работает корректно, следовательно, приступаем к формированию ответа. В конструкции if необходимо учесть только одно условие: число R должно быть равно N. Поскольку нам необходимо минимальное N, то, как только условие выполнится, выводим это число и завершаем цикл оператором break.

# Функция для подсчета чётных цифр
def count_evens(num):
    evens = sum([1 for i in num
                 if int(i, 8) % 2 == 0])
    return evens


res = []
for N in range(10000):
    # Строим 8-ричную запись
    R = f'{N:o}'
    # Если кол-во нечётно
    if count_evens(R) % 2:
        R = R[-3:] + '46'
    # Если кол-во чётно
    else:
        R = f'{(N % 8 * 5):o}' + R
    # Переводим в десятичную
    R = int(R, 8)
    # Формируем ответ
    if R == N:
        print(N)
        break

В итоге на экране видим ответ на данное задание — число 16.