Задание 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. Сложим все полученные произведения:
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() и добавить в качестве второго аргумента номер системы, из который мы переводим число.
При решении задачи 5 нам может пригодиться способ нахождения разрядов у числа.
Удобнее всего переводить число в строку функцией 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:
2. Строим алгоритм из задачи:
Пояснение по некоторым частям алгоритма:
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:
2. Строим алгоритм из задачи
N % 2 == 0 – стандартная проверка на четность.
3. Находим число, которое подходит по условию.
Если полученное число 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. К этой записи дописываются справа и слева ещё по одному или два разряда по следующему правилу:
Например, для числа 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 для решения задачи и проверки.
Удачи на экзамене!
В варианте ЕГЭ-2025 две задачи по теории вероятностей — это №4 и №5. По заданию 5 в Интернете почти нет доступных материалов. Но в нашем бесплатном мини-курсе все это есть.
