Задание 5. Анализ и построение алгоритмов для исполнителей. 

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

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

Эту задачу можно решать двумя способами, аналитически и программированием. Решая через Python, сложнее допустить ошибку, однако некоторые виды задач можно решить только аналитическим способом. 

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

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

Системы счисления — это способы представления чисел с помощью символов. Существует множество систем счисления, но наиболее распространены десятичная, двоичная, восьмеричная и шестнадцатеричная.

Десятичная

Самая популярная система счисления – десятичная. Ее основание – 10 и состоит она из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Так, когда мы прибавляем к 9 – наибольшей цифре - единицу, мы пишем на ее месте 0, добавляем следующий разряд (в данном случае второй) и получаем 10. Это очевидно, но подробное понимание этого факта облегчит нам изучение других систем счисления.

Двоичная

Имеет основание 2 и состоит из цифр 0 и 1. Возьмем 1 и прибавим к ней 1, так как 1 — это наибольшая цифра, мы перейдем на следующий разряд и получим 10. Для примера соотнесем числа из десятичной с числами из двоичной:

1 = 1     2 = 10    3 = 11     4 = 100     5 = 101     6 = 110    7 = 111    8 = 1000   

Восьмеричная

Имеет основание 8 и состоит из цифр 0, 1, 2, 3, 4, 5, 6, 7. Приведем несколько примеров, где первое число – десятичная система, второе – восьмеричная:

5 = 5     6 = 6     7 = 7     8 = 10     9 = 11     10 = 12     11 = 13     12 = 14

Шестнадцатеричная

 Имеет основание 16 и состоит из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Да, символы A, B, C и т.д. тоже являются цифрами. Они используются, так как мы не можем отобразить, например, число 11 одной цифрой. Приведем несколько примеров, где первое число – десятичная система, второе – шестнадцатеричная:

8 = 8     9 = 9     10 = A     11 = B     12 = C     13 = D     14 = E     15 = F     16 = 10

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

• Перевод чисел из десятичной системы счисления в другие.

Перевод чисел из десятичной в другие осуществляется с помощью последовательного деления исходного числа на основание новой системы счисления и записывания остатков. Напомним, что у двоичной системы счисления основание – 2, у восьмеричной – 8 и т. д.

Алгоритм таков:

1. Делим число на основание новой системы счисления.

2. Записываем остаток от деления.

3. Продолжаем деление частного от предыдущего деления на основание, пока частное не станет равным 0.

4. Записываем остатки в обратном порядке.

Разберем на примере:

Переведем 25 из десятичной системы в двоичную.

1. 25 ÷ 2 = 12 (остаток 1), записано 1

2. 12 ÷ 2 = 6 (остаток 0), записано 10

3. 6 ÷ 2 = 3 (остаток 0), записано 100

4. 3 ÷ 2 = 1 (остаток 1), записано 1001

5. 1 ÷ 2 = 0 (остаток 1), записано 10011

Частное равно 0, значит пора переворачивать наше записанное число. Получаем 11001 – это и есть 25 в двоичной системе.

Переведем 123 из десятичной системы в восьмеричную.

1. 123 ÷ 8 = 15 (остаток 3), записано 3

2. 15 ÷ 8 = 1 (остаток 7), записано 37

3. 1 ÷ 8 = 0 (остаток 1), записано 371

Переворачиваем и получаем наш ответ – 173.

Переведем число 241 из десятичной системы в шестнадцатеричную.

1. 241 ÷ 16 = 15 (остаток 1), записано 1

2. 15 ÷ 16 = 0 (остаток 15, что соответствует F в шестнадцатеричной системе), записано 1F

Переворачиваем и получаем F1.

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

Каждый разряд числа в любой системе счисления представляет собой определенную степень основания этой системы. Чтобы перевести число в десятичную систему, нужно умножить каждую цифру числа на основание системы в степени, соответствующей разряду этой цифры, и затем сложить все полученные произведения.

Общий алгоритм:

1. Запишем число и под каждой цифрой укажем ее разряд (степень основания системы счисления).

2. Умножим каждую цифру на основание системы в степени, соответствующей ее разряду.

3. Сложим все полученные произведения.

Разберемся на примерах:

Переведем число 1101 из двоичной системы в десятичную.

1. Запишем число и под каждой цифрой укажем ее разряд (степень двойки): 

1 1 0 1 

3 2 1 0

2. Умножим каждую цифру 1101 на 2 в степени, соответствующей ее разряду:

1 * 23 = 1 * 8 = 8

1 * 22 = 1 * 4 = 4

0 * 21 = 0 * 2 = 0

1 * 20 = 1 * 1 = 1

3. Сложим все полученные произведения:

8 + 4 + 0 + 1 = 13

Получим, что 1101 в двоичной системе = 13 в десятичной.

Переведем число 372 из восьмеричной системы в десятичную.

1. Запишем число и под каждой цифрой укажем ее разряд (степень восьмерки): 

3 7 2

2 1 0

2. Умножим каждую цифру на 8 в степени, соответствующей ее разряду:

3 * 82 = 3 * 64 = 192

7 * 81 = 7 * 8 = 56

2 * 80 = 2 * 1 = 2

3. Сложим все полученные произведения:

192 + 56 + 2 = 250

Получим, что 372 в восьмеричной системе = 250 в десятичной.

Переведем число A3F из шестнадцатеричной системы в десятичную.

1. Запишем число и под каждой цифрой укажем ее разряд (степень шестнадцати):

A 3 F

2 1 0

2. Умножим каждую цифру на 16 в степени, соответствующей ее разряду:

A (10) * 162 = 10 * 256 = 2560

3 * 161 = 3 * 16 = 48

F (15) * 160 = 15 * 1 = 15

3. Сложим все полученные произведения:

• 2560 + 48 + 15 = 2623 

A3F в шестнадцатеричной = 2623 в десятичной.

Умение переводить числа из различных систем счисления достаточно для решения 5 задания аналитически. Теперь давайте разберемся как решать его через Python.

Чтобы перевести число из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную используются функции bin(), oct() и hex() соответственно.

Функции bin, oct и hex возвращают строки, первые два символа в которых указывают на систему счисления. Они нам не понадобятся. Чтобы их убрать, используются срезы. Пишем [ : ] после функции и перед двоеточием в квадратных скобках пишем 2 – номер символа, с которого начнется наша срезанная строка (помним, что в программировании счет начинается с 0).

num – исходное число в десятичной системе;

base – основание системы, в которую хотим перевести.

Пока наш num > 0, мы добавляем в переменную result остаток от деления числа на основание и делим число нацело на основание. В конце мы пишем [ : :-1], чтобы перевернуть нашу строку result.

Если нас попросят перевести число в систему с основанием больше 10, то такой алгоритм не сработает, давайте исправим его.

Мы добавили строку digits со всеми возможными символами. Теперь мы добавляем в переменную result не остаток, а элемент из строки digits под индексом остатка. Так, если остаток будет равен 11, мы добавим не ‘11’, а элемент под индексом 11 из строки digits – ‘B’.

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

Удобнее всего переводить число в строку функцией str() и находить цифры по индексу. Если указать - , то счет пойдет с конца, но самый последний элемент строки будет иметь индекс -1, а не -0. Помним, что таким способом мы получим цифры в строковом типе. Чтобы перевести их в числа, воспользуемся функцией int().

Мы изучили всю нужную теорию для задания 5. Давайте разберем основной алгоритм решения задачи.

1. Перебираем все числа в указанном диапазоне.

2. Строим алгоритм, который описывается в условии задачи.

3. Находим число, которое подходит по условию.

Перейдем к решению пятых задач.

1. Демоверсия ЕГЭ 2025

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

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

а) если число чётное, то к двоичной записи числа слева дописывается 10;

б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.

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

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 410 = 1002 результатом является число 2010 = 101002, а для исходного числа 510 = 1012 это число 5310 = 1101012.

Укажите максимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не больше 12. В ответе запишите это число в десятичной системе счисления.

Решим аналитическим способом.

Нам нужно найти такое число N <= 12, что число R, построенное по алгоритму, будет максимальным.

1. Чтобы получить максимальное число, начнем перебирать все числа N с конца (12, 11, 10...).

2. Строим двоичную запись числа N, проверяем ее на четность.

Важно отметить, что четность у числа в десятичном виде и в двоичном одинаковая. Чтобы определить четность у числа в двоичном виде, можно посмотреть на последнюю цифру – если она 1, то число нечетное, 0 – четное.

а) если число чётное, то к двоичной записи числа слева дописывается 10;

б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.

В случае б) мы добавим к нашему числу 3 цифры, а значит и три разряда, а в случае а) только два, следовательно, случай б) вернет заведомо большее число. Значит нам нужно, чтобы N было нечетным.

3. Возьмем наибольшее нечетное число – 11. Переведем его в двоичную запись:

11 ÷ 2 = 5 (остаток 1), записано 1

5 ÷ 2 = 2 (остаток 1), записано 11

2 ÷ 2 = 1 (остаток 0), записано 110

1 ÷ 2 = 0 (остаток 1), записано 1101

Переворачиваем и получаем 1011

Дописываем слева 1 и справа 01, получаем 1101101

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

1 1 0 1 1 0 1

6 5 4 3 2 1 0

1 * 26 = 1 * 64 = 64

1 * 25 = 1 * 32 = 32

0 * 24 = 0 * 16 = 0

1 * 23 = 1 * 8 = 8

1 * 22 = 1 * 4 = 4

0 * 21 = 0 * 2 = 0

1 * 20 = 1 * 1 = 1

64 + 32 + 0 + 8 + 4 + 0 + 1 = 109

Получаем ответ - 109

2. Демоверсия ЕГЭ 2024

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

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

а) если число N делится на 3, то к этой записи дописываются три последние двоичные цифры;

б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.

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

3. Результат переводится в десятичную систему и выводится на экран.

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

Решим программированием 

1. Перебираем все числа. Так как диапазон N не указан, напишем от 1 до 100:

Пояснение по некоторым частям алгоритма:

N % 3 найдет остаток от деления N на 3. Если он равен 0, то число N делится на 3

R[ -3 : ] – срез, который начинается на третьем элементе с конца и заканчивается последним элементом строки.

3. Находим число, которое подходит по условию

Добавляем в самое начало массив ans. int(R, 2) переведет число из двоичной в десятичную систему. Если наше R больше 151, мы добавляем его в массив ans. После выхода из цикла, мы пишем наименьшее число из массива ans.

Ответ: 163

3. Досрочная волна 2024

Here's the text from the image:

________________________________________

Задание 5 (№15317). (М. Ишимов)

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

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

а) если число N чётно, то справа приписывается «01»;

б) если число N нечётно, то к этой записи слева и справа приписывается единица.

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

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 12 = 1100₂ результатом является число 110001₂ = 49, а для исходного числа 5 = 101₂ результатом является число 110111₂ = 27.

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

1. Перебираем все числа. Так как диапазон N не указан, напишем от 1 до 100:

Если полученное число R > 156, то мы печатаем исходное число N и пишем break – останова цикла for.

Получаем ответ 33.

4. Основная волна (центр) 2024

Задание 5 (№17624).

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

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

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

б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.

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

3. Результат переводится в десятичную систему и выводится на экран.

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

5. Пробник 01.2023 

Задание 5 (№1804).

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

1. Строится двоичная запись числа 2N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

a) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 1000001;

b) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 249. В ответе это число запишите в десятичной системе счисления.

 6. OpenFIPI #1 2023

Задание 5 (№6884).

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

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа и слева ещё по одному или два разряда по следующему правилу:

• если N чётное, то в конец числа (справа) дописывается нуль, а в начало числа (слева) дописывается единица;

• если N нечётное, то в конец числа (справа) и в начало числа (слева) дописываются по две единицы.

Например, для числа 13 двоичная запись 1101 преобразуется в запись 11101111.

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

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

 7. Досрочная волна I 2023

Задание 5 (№7584).

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

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

a) если число кратно 3, тогда в конец дописывается три младших разряда полученной двоичной записи,

b) если число не кратно 3, тогда в конец дописывается двоичная последовательность, являющаяся результатом умножения 3 на остаток от деления числа N на 3.

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

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

 8. Основная волна 2022 I

Задание 5 (№4585).

На вход алгоритма подаётся натуральное число N.

Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

a) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

b) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

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

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

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