Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого, автомат выдаст число 1311.
Решение.
Поскольку числа записаны в порядке убывания, одна сумма цифр двух разрядов равна 13, другая — 11. Чтобы число было наименьшим, необходимо, чтобы в старших разрядах находилась как можно меньшая цифра, следовательно, сумма старших разрядов должна быть меньшей. При разложении 11 на слагаемые необходимо, чтобы одно из них было минимально возможным, поэтому представим 11 как сумму 2 и 9, это — первые две цифры искомого числа. Вторые две цифры получатся разложением числа 13 на слагаемые: 4 и 9. Следовательно, ответ 2949.
Ответ: 2949.
Приведём другое решение на языке Python.
for i in range(1000, 10000):
s = str(i)
k1 = int(s[0]) + int(s[1])
k2 = int(s[2]) + int(s[3])
first = str(max(k1, k2))
second = str((min(k1, k2)))
s1 = first + second
if s1 == ‘1311’:
print(i)
break
Источник: Демонстрационная версия ЕГЭ—2015 по информатике.
В начало страницы
Учитываемые варианты
Различие заданий
(Подсказка: для перехода к заданию нажмите на его название
или на его линию.)
Максимальное допустимое различие в подтеме:
0.35.
Выбрать другое:
0.5, 0.65.
Подтема 1
Задание
1.1
(ДОСР-2016, №11107) У исполнителя Аккорд-4 две команды, которым присвоены номера: 1. вычти 1 2. умножь на 4 Выполняя первую из них, Аккорд-4 вычитает из числа на экране 1, а выполняя вторую, умножает это число на 4. Запишите порядок команд в программе, которая содержит не более пяти команд и преобразует число 5 в число 62. Если таких программ более одной, то запишите любую из них. В ответе указывайте лишь номера команд. Так, для программы умножь на 4 вычти 1 вычти 1 нужно написать: 211. Эта программа преобразует, например, число 7 в число 26.
Варианты
Текст задания
Подтема 2
Задание
2.1
(ДОСР-2017, №13352) У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2, 2. умножь на 5. Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5. Например, программа 2121 – это программа умножь на 5, прибавь 2, умножь на 5, прибавь 2, которая преобразует число 2 в число 62. Запишите порядок команд в программе, которая преобразует число 1 в число 45 и содержит не более четырёх команд. Указывайте лишь номера команд. Если таких программ более одной, то запишите любую из них.
Варианты
Текст задания
(
с выделением различий)
Подтема 3
Задание
3.1
(ДЕМО-2016, №9357) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 125. В ответе это число запишите в десятичной системе счисления. ИЛИ У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2, 2. умножь на 5. Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5. Например, программа 2121 — это программа умножь на 5, прибавь 2, умножь на 5, прибавь 2, которая преобразует число 1 в число 37. Запишите порядок команд в программе, которая преобразует число 2 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.
Варианты
Текст задания
(
с выделением различий)
Задание
3.2
(ОСН-2019, №18708) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 85. В ответе запишите это число в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.3
(ДОСР-2015, №8094) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Варианты
Текст задания
(
с выделением различий)
Задание
3.4
(ДОСР-2019, №18434) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 55 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.5
(ДЕМО-2020, №19055) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 97 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.6
(ДОСР-2021, №36018) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 396 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.7
(ДЕМО-2018, №13733) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.8
(ДЕМО-2021, №27402) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.9
(ДОСР-2019, №18075) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: а) находится остаток от деления на 2 суммы двоичных разрядов N, полученный результат дописывается в конец двоичной последовательности N. б) пункт а повторяется для вновь полученной последовательности. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 123 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Варианты
Текст задания
(
с выделением различий)
Задание
3.10
(ДОСР-2018, №15622) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи, если а) сумма нечетная к числу дописывается 11, б) сумма четная, дописывается 00. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 114 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.11
(ДЕМО-2019, №16033) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: а) если N чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. б)если N нечётное, справа дописывается сначала единица, а затем ноль. Например, двоичная запись 100 числа 4 будет преобразована в 10001, а двоичная запись 111 числа 7 будет преобразована в 11110. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R — результата работы данного алгоритма. Укажите минимальное число R, которое больше 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.12
(ОСН-2018, №15974) Автомат обрабатывает натуральное число N по следующему алгоритму: 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается 10, в противном случае справа дописывается 01. Например, двоичная запись 1001 числа 9 будет преобразована в 100101. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма. Укажите максимальное число R, которое не превышает 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.13
(ДОСР-2020, №25836) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма. Укажите максимальное число N, для которого результат работы алгоритма будет меньше 134. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.14
(ДОСР-2020, №23904) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма. Укажите минимальное число N, для которого результат работы алгоритма будет больше 134. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Задание
3.15
(ДОСР-2018, №15846) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа – результата работы данного алгоритма. Укажите минимальное число N, для которого результат работы алгоритма будет больше 115. В ответе это число запишите в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Подтема 4
Задание
4.1
(ОСН-2019, №18812) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно; б) к этой записи справа дописывается 1, если остаток от деления количества единиц на 2 равен 0, и 0, если остаток от деления количества единиц на 2 равен 1. Полученная таким образом запись является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 54 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Варианты
Текст задания
(
с выделением различий)
Подтема 5
Задание
5.1
(ОСН-2020, №26978) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются разряды по следующему правилу: а) если число четное, то к двоичной записи числа в конце дописываются 1 и 0; б) если число нечетное, то к двоичной записи числа в конце дописывается 01. Полученная таким образом запись является двоичной записью искомого числа R. Укажите наибольшее число R меньшее 109, которое может получиться после обработки этого алгоритма. В ответе это число запишите в десятичной системе.
Варианты
Текст задания
(
с выделением различий)
Задание
5.2
(ОСН-2019, №18785) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. Далее эта запись обрабатывается по следующему правилу: а) если число чётное, то к двоичной записи числа слева дописывается 1, а справа 0. Например, если для исходного числа 100 результатом будет являться число 11000; б) если число нечётное, то к двоичной записи числа слева дописывается 11 и справа дописывается 11. Полученная таким образом запись является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 52. В ответе запишите это число в десятичной системе счисления.
Варианты
Текст задания
(
с выделением различий)
Подтема 6
Задание
6.1
(ОСН-2020, №26949) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописывается справа два нуля, если число четное, или две единицы в противном случае Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число менее 94. В ответе это число запишите в десятичной системе.
Варианты
Текст задания
(
с выделением различий)
Подтема 7
Задание
7.1
(ОСН-2021, №37140) Автомат обрабатывает натуральное число N по следующему алгоритму. 1. Строится двоичная запись числа N. 2. Если N четное, то в конец полученной записи (справа) дописывается 0, в начало — 1; если N — нечётное в конец и начало дописывается по две единицы. 3. Результат переводится в десятичную систему и выводится на экран. Пример. Дано число N = 13. Алгоритм работает следующим образом: 1. Двоичная запись числа N: 1101. 2. Число нечетное, следовательно по две единицы по краям — 11110111. 3. На экран выводится число 247. Укажите наименьшее число, большее 52, которое может является результатом работы автомата.
Варианты
Текст задания
(
с выделением различий)
Подтема 8
Задание
8.1
(ДЕМО-2015, №7454) Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам. 1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа. 2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей). Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114. Укажите наименьшее число, в результате обработки которого, автомат выдаст число 1311.
Варианты
Текст задания
(
с выделением различий)
Задание
8.2
(ДЕМО-2017, №11342) Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам. 1. Складываются первая и вторая, а также вторая и третья цифры исходного числа. 2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей). Пример. Исходное число: 348. Суммы: 3 + 4 = 7; 4 + 8 = 12. Результат: 127. Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711.
Варианты
Текст задания
(
с выделением различий)
ЕГЭ по математике | профиль — Задание 1 (Задачи на параллелограмм)
Привет! Сегодня повторим геометрическую фигуру параллелограмм и пореша…
Категория: ЕГЭ Подкатегория: Математика
Дата: 08-03-2023 в 11:27:39
0
ЕГЭ по информатике — Задание 27 (Количество цепочек чисел)
Привет! Сегодня поговорим, как искать количество подпоследовательносте…
Категория: ЕГЭ Подкатегория: Информатика
Дата: 06-03-2023 в 17:30:07
0
ЕГЭ по математике | профиль — Задание 1 (Задачи на площадь треугольника)
Привет! Это первая статья посвящённая ЕГЭ по математике профильному ур…
Категория: ЕГЭ Подкатегория: Математика
Дата: 02-03-2023 в 16:24:25
0
ЕГЭ по информатике — Задание 27 (Цепочки чисел)
Привет! Продолжаем готовится к ЕГЭ по информатике. Сегодня решим неско…
Категория: ЕГЭ Подкатегория: Информатика
Дата: 27-02-2023 в 16:00:04
2
ЕГЭ по информатике — Задание 27 (Набираем форму)
Сегодня рассмотрим некоторые тренировочные задачи из 27 задания ЕГЭ по…
Категория: ЕГЭ Подкатегория: Информатика
Дата: 20-02-2023 в 17:20:47
0
ЕГЭ по информатике — Задание 27 (Делимость чисел)
Эта статья посвящена 27 заданию из ЕГЭ по информатике 2023…
Категория: ЕГЭ Подкатегория: Информатика
Дата: 13-02-2023 в 11:00:57
0
ЕГЭ по информатике — Задание 15 (Отрезки на Python)
Привет! Сегодня посмотрим задачи на отрезки из 15 задания ЕГЭ по инфор…
Категория: ЕГЭ Подкатегория: Информатика
Дата: 31-01-2023 в 14:30:51
0
ЕГЭ по информатике 2023 — Задание 26 (Сортировка)
Привет! В этой статье посмотрим некоторые задачи из 26 задания ЕГЭ по …
Категория: ЕГЭ Подкатегория: Информатика
Дата: 16-01-2023 в 14:00:23
4
ЕГЭ по информатике 2023 — Задание 22 (Параллельные процессы)
Сегодня посмотрим новое 22 задание из ЕГЭ по информатике 2023….
Категория: ЕГЭ Подкатегория: Информатика
Дата: 31-12-2022 в 13:00:03
0
ЕГЭ по информатике 2023 — Задание 6 (Задачи с Черепахой)
Привет! Сегодня разберём новый тип 6 задания из ЕГЭ по информатике 202…
Категория: ЕГЭ Подкатегория: Информатика
Дата: 17-11-2022 в 13:26:27
4
Задание 7682
Внимательно прочитайте текст задания и выберите верный ответ из списка
Решение
→
Задание 7759
Введите ответ в поле ввода
Решение
→
Задание 7751
Введите ответ в поле ввода
Решение
→
Задание 8228
Введите ответ в поле ввода
Решение
→
Задание 7646
Внимательно прочитайте текст задания и выберите верный ответ из списка
Решение
→
Задание 8611
Введите ответ в поле ввода
Решение
→
Задание 8183
Введите ответ в поле ввода
Решение
→
Задание 8219
Введите ответ в поле ввода
Решение
→
Задание 8634
Введите ответ в поле ввода
Решение
→
Задание 7359
Внимательно прочитайте текст задания и выберите верный ответ из списка
Решение
→
Задание 7394
Внимательно прочитайте текст задания и выберите верный ответ из списка
Решение
→
Задание 7484
Внимательно прочитайте текст задания и выберите верный ответ из списка
Решение
→
Задание 7556
Внимательно прочитайте текст задания и выберите верный ответ из списка
Решение
→
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами — ЛЕГКО!
0. Практика Программирования
1. Графы через матрицу смежности
3. Базы данных. Поиск файла по маске.
4. Кодирование и декодирование
5. Простейшие исполнители и алгоритмы
6. Анализ простейших программ
7. Передача данных. Размеры файлов.
8. Количество информации и комбинаторика
9. Обработка числовой информации в электронных таблицах
10. Информационный поиск средствами операционной системы или текстового редактора
11. Количество информации и комбинаторика
12. Сложные исполнители и алгоритмы
15. Преобразование логических выражений
17. Программа для обработки целочисленной информации
18. Обработка вещественных выражений в электронных таблицах
22. Программирование – циклы, условия
23. Линейные программы и ветвление
24. Программирование — Обработка символьной информации
25. Программирование — Обработка целочисленной информации
26. Программирование — Обработка целочисленной информации с использованием сортировки
27. Программирование – оптимизация по времени и по памяти
Public user contributions licensed under
cc-wiki license with attribution required
Урок посвящен тому, как решать 4 задание ЕГЭ по информатике
Содержание:
- Кодирование информации
- Кодирование и расшифровка сообщений
- Решение 4 заданий ЕГЭ
Кодирование информации
4-е задание: «Кодирование и декодирование информации»
Уровень сложности
— базовый,
Требуется использование специализированного программного обеспечения
— нет,
Максимальный балл
— 1,
Примерное время выполнения
— 2 минуты.
Проверяемые элементы содержания: Умение кодировать и декодировать информацию
До ЕГЭ 2021 года — это было задание № 5 ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:
«Из-за невнимательного чтения условия задания экзаменуемые иногда не замечают, что требуется найти кодовое слово минимальной длины с максимальным (минимальным) числовым значением.
Кроме того, если в задании указано, что несколько букв остались без кодовых слов (как, например, в задании демоварианта), то кодовое слово для указанной буквы должно быть подобрано таким образом, чтобы осталась возможность найти кодовые слова, удовлетворяющие условию Фано, и для других букв. Так, например, если мы букву А закодируем нулём, а букву Б единицей, то букву В мы уже никак не сможем закодировать с соблюдением условия Фано, поэтому длину кодового слова для А или Б следует увеличить»
ФГБНУ «Федеральный институт педагогических измерений»
- Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
- Кодирование бывает равномерным и неравномерным:
- при равномерном кодировании всем символам соответствуют коды одинаковой длины;
- при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.
Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).
Кодирование и расшифровка сообщений
Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.
Для решения задач с декодированием, необходимо знать условие Фано:
Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)
Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.
- если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:
- условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова
Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с концом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.
Однозначное декодирование обеспечивается:
Однозначное декодирование
Декодирование
Егифка ©:
Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube: 
ЕГЭ 4.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
✍ Решение:
- Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
О -> 0 -> 00 В -> 1 -> 01 Д -> 2 -> 10 П -> 3 -> 11 А -> 4 -> 100
ВОДОПАД:010010001110010
010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2
Результат: 22162
Теоретическое решение ЕГЭ данного задания по информатике, видео:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Рассмотрим еще разбор 4 задания ЕГЭ:
ЕГЭ 4.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
| a | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
Какой набор букв закодирован двоичной строкой 1100000100110?
✍ Решение:
- Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
- Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
✎ 1 вариант решения:
110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ b a c d e
Результат: b a c d e.
✎ 2 вариант решения:
-
Этот вариант решения 4 задания ЕГЭ более сложен, но тоже верен.
- Сделаем дерево, согласно кодам в таблице:
- Сопоставим закодированное сообщение с кодами в дереве:
110 000 01 001 10
Результат: b a c d e.
Кроме того, вы можете посмотреть видеорешение этого задания ЕГЭ по информатике (теоретическое решение):
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Решим следующее 4 задание:
ЕГЭ 4.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).
Определите, какое число передавалось по каналу в виде 01100010100100100110.
✍ Решение:
- Рассмотрим пример из условия задачи:
Было2310 Стало00101001102
0010100110 (0010 - 2, 0011 - 3)
01100 01010 01001 00110
0110 0101 0100 0011
0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3
Ответ: 6 5 4 3
Вы можете посмотреть видеорешение этого задания ЕГЭ по информатике, теоретическое решение:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
ЕГЭ 4.4:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Подобные задания для тренировки
✍ Решение:
✎
1 вариант решения
основан на логических умозаключениях:
- Найдём самые короткие возможные кодовые слова для всех букв.
- Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
- Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
- Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
- Суммарная длина всех четырёх кодовых слов равна:
(Н)1 + (К)2 + (Л)3 + (М)3 = 9
✎ 2 вариант решения:
- Будем использовать дерево. Влево откладываем 0, вправо — 1:
- Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
(Н) -> 0 -> 1 символ (К) -> 10 -> 2 символа (Л) -> 110 -> 3 символа (М) -> 111 -> 3 символа
(Н)1 + (К)2 + (Л)3 + (М)3 = 9
Ответ: 9
4.5:
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:
А: 101010, Б: 011011, В: 01000
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Подобные задания для тренировки
✍ Решение:
- Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
- Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.
Результат: 00
4.6:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:
А - 01 Б - 00 В - 11 Г - 100
Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
- Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:
- Перепишем сверху вниз получившееся кодовое слово для Д: 101
Результат: 101
Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
4.7: Демоверсия ЕГЭ 2018 информатика (ФИПИ):
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Подобные задания для тренировки
✍ Решение:
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
- При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:
Результат: 1100
Подробное теоретическое решение данного 4 (раньше №5) задания из демоверсии ЕГЭ 2018 года смотрите на видео:
📹 Видеорешение на RuTube здесь
4.8:
По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:
А: 00011 Б: 111 В: 1010
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
✍ Решение:
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
- Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
- Получившееся числовое значение кодового слова для буквы Г — 01.
- Получившееся числовое значение кодового слова для буквы Г — 00.
- После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.
Дерево по условию Фано (однозначно декодируется с начала):
Дерево по обратному условию Фано (однозначно декодируется с конца):
Результат: 00
4.9:
По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:
Е – 000 Д – 10 К – 111
Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.
Подобные задания для тренировки
✍ Решение:
- С помощью дерева отобразим известные коды для букв:
- В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:
- Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
Д Е Д М А К А Р 10 000 10 001 01 111 01 110
Результат: 20
Смотрите виде решения задания:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь