Задание 5. Формальное исполнение алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд: все задания

Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).

Версия для печати

1. Задание#T30241

По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: A – 101, B – 010, С – 00, D – 1001, E – 111, F – 0110.

Укажите кратчайшее возможное кодовое слово для буквы N. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 17 тыс. раз. С ним справились 62% пользователей.

2. Задание#T30158

По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: A – 111, B – 000, С – 01, D – 1101, E – 100, F – 0010.

Укажите кратчайшее возможное кодовое слово для буквы L. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 10 тыс. раз. С ним справились 68% пользователей.

3. Задание#T29776

По каналу связи передаются сообщения, содержащие только восемь букв: К, Л, М, Н, О, П, Р, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К – 001, Н – 100, Р – 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МОЛОКОСОС?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Построим дерево кодирования для заданных букв.

Видно, что в дереве есть четыре свободных узла: 000 (длина кода 3), 01 (длина кода 2), 101 (длина кода 3), 110 (длина кода 3). Нужно закодировать ещё пять букв (Л, М, О, П, С), четыре из которых входят в слово МОЛОКОСОС.

Один из свободных узлов нужно использовать для расширения дерева. Если расширить узел длины 2, то все буквы будут кодироваться тремя двоичными символами и длина кода для слова МОЛОКОСОС составит 9 ⋅ 3 = 27 бит.

Если расширить узел длины 3, то получится один узел длины 2, два узла длины 3 и два узла длины 4. Чтобы количество знаков для кодирования слова МОЛОКОСОС было минимальным, нужно брать для букв Л, М, О, С как можно более короткие коды, при этом самый короткий код надо использовать для буквы О, которая встречается в заданном слове четыре раза; для буквы С, которая встречается два раза, можно взять код более длинный, а для букв Л и М (по одному разу) – самый длинный. С учётом уже заданного кода для К получаем 4 ⋅ 2 + 2 ⋅ 3 + 3 + 4 + 3 = 24 бита.

Ответ: 24

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 8 тыс. раз. С ним справились 40% пользователей.

4. Задание#T29749

По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 101, В – 010, И – 0.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Построим дерево кодирования для заданных букв.

Видно, что в дереве есть три свободных узла: 011 (длина кода 3), 100 (длина кода 3), 11 (длина кода 2). Нужно закодировать ещё пять букв (Е, З, Н,О, Р), три из которых входят в слово НЕВЕЗЕНИЕ. Чтобы количество знаков для кодирования этого слова было минимальным, нужно брать для букв Е, З, Н как можно более короткие коды, при этом самый короткий код надо использовать для буквы Е, которая встречается в заданном слове четыре раза; для буквы Н, которая встречается два раза, можно взять код более длинный, а для буквы З (один раз) – самый длинный.

Используем один из свободных узлов для расширения дерева. После этого получится четыре свободных узла. Три из них можно использовать для букв Е, З, Н, а четвёртый – для дальнейшего расширения дерева и кодирования букв О и Р, которые не входят в заданное слово.

Если расширить узел длины 2, то все коды букв Е, З, Н будут содержать по три бита, общая длина добавленных кодов для слова НЕВЕЗЕНИЕ составит

7 · 3 = 21.

Если расширить узел длины 3, то получится один свободный узел длины 2, один длины 3 и два длины 4. Если использовать код длины 2 для буквы Е, код длины 3 для Н и код длины 4 для З, то общая длина добавленных кодов составит

4 · 2 + 2 · 3 + 4 = 18.

Видно, что этот вариант выгоднее. Коды букв В и И заданы в условии, их общая длина – 5, итого получается 23 бита.

Ответ: 23

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 7 тыс. раз. С ним справились 38% пользователей.

5. Задание#T9786

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова

, Для двух оставшихся букв – П и Р – длины кодовых слов неизвестны.

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

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

Показать ответ

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 11 тыс. раз. С ним справились 66% пользователей.

6. Задание#T9286

По каналу связи передаются сообщения, содержащие только восемь букв: А, Е, И, О, П, Р, С, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 00, И – 1100, Р – 1110.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова РЕПЕТИТОР?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 10 тыс. раз. С ним справились 45% пользователей.

7. Задание#T8636

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, К решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово ; для буквы Б – кодовое слово .

Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е, К?

Показать ответ

Это задание решали 6 тыс. раз. С ним справились 62% пользователей.

8. Задание#T4897

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А –

, Б – , И –

Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Указание:

Постройте дерево кодирования.

Решение:

Построим дерево кодирования.

Нужно закодировать ещё четыре буквы (В, Д, Е, Н), а в дереве есть три свободных узла. Каждое продолжение дерева из свободного узла создаёт два узла вместо одного, то есть количество узлов увеличивается на . Значит, нужно продолжить дерево в одном месте. С точки зрения длины кодов это можно сделать двумя способами:

из узла (длина кода ) получить два узла с длиной кода ;
из узла или (длина кода ) получить два узла с длиной кода .

В первом случае мы получим новые коды длиной , , , , во втором – , , , .

Подсчитаем количество знаков для кодирования слова ВВЕДЕНИЕ в каждом их этих случаев. В первом случае длина всех добавленных кодов (буквы В, Д, Е, Н) одинакова – бита. Длина кода буквы И задана – тоже бита. Всего получается

бита.

Во втором случае длина добавленных кодов разная. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы Е (она встречается чаще всех), следующим – код буквы В. Тогда длина кода для Е – бита, для В – , для Д и Н – по . Всего потребуется

бита.

Ответ: 23

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 12 тыс. раз. С ним справились 43% пользователей.

9. Задание#T4870

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – , К –

, Л –

Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Указание:

Постройте дерево кодирования.

Решение:

Построим дерево кодирования.

Нужно закодировать ещё четыре буквы (А, И, С, Ц), а в дереве есть три свободных узла. Каждое продолжение дерева из свободного узла создаёт два узла вместо одного, то есть количество узлов увеличивается на . Значит, нужно продолжить дерево в одном месте. С точки зрения длины кодов это можно сделать двумя способами:

из узла (длина кода ) получить два узла с длиной кода ;
из узла или (длина кода ) получить два узла с длиной кода .

В первом случае мы получим новые коды длиной , , , , во втором – , , , .

Подсчитаем количество знаков для кодирования слова АБСЦИССА в каждом их этих случаев. В первом случае длина всех добавленных кодов (буквы А, С, Ц, И) одинакова – бит. Длина кода буквы Б задана – бит. Всего получается

бит.

Во втором случае длина добавленных кодов разная. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы А (она встречается чаще всех), следующим – код буквы С. Тогда длина кода для А – бит, для С – , для Ц и И – по . Всего потребуется

бит.

Ответ: 22

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 9 тыс. раз. С ним справились 45% пользователей.

10. Задание#T4843

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г –

, И – , Т – .

Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Указание:

Постройте дерево кодирования.

Решение:

Построим дерево кодирования.

Нужно закодировать ещё четыре буквы (А, Б, Н, Р), а в дереве есть два свободных узла. Каждое продолжение дерева из свободного узла создаёт два узла вместо одного, то есть количество узлов увеличивается на . Значит, нужно продолжить дерево в двух местах. С точки зрения длины кодов это можно сделать двумя способами:

из узла (длина кода ) получить два узла с длиной кода , затем продолжить дерево из любого из трёх свободных узлов длины ;
из узла (длина кода ) получить два узла с длиной кода , а затем из одного из них - два узла с длиной кода .

В первом случае мы получим новые коды длиной , , , , во втором – , , , .

Подсчитаем количество знаков для кодирования слова БАРАБАН в каждом из этих случаев. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы А (она встречается чаще всех), следующим – код буквы Б.

В первом случае длина кода букв А и Б – бит, букв Н и Р – бит, для кодирования слова БАРАБАН потребуется

бит.

Во втором случае длина кода А – бит, Б – , Н и Р – и . Всего потребуется

бит.

В любом случае для кодирования слова БАРАБАН потребуется минимум двоичных знака.

Ответ: 23

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 8 тыс. раз. С ним справились 56% пользователей.

11. Задание#T4816

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, О, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А –

, И – , С – .

Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОБОК?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Указание:

Постройте дерево кодирования.

Решение:

Построим дерево кодирования.

Нужно закодировать ещё четыре буквы (Б, К, Л, О), а в дереве есть два свободных узла. Каждое продолжение дерева из свободного узла создаёт два узла вместо одного, то есть количество узлов увеличивается на . Значит, нужно продолжить дерево в двух местах. С точки зрения длины кодов это можно сделать двумя способами:

Из узла (длина кода ) получить два узла с длиной кода , затем продолжить дерево из любого из трёх свободных узлов длины ;
Из узла (длина кода ) получить два узла с длиной кода , а затем из одного из них – два узла с длиной кода .

В первом случае мы получим новые коды длиной , , , , во втором – , , , .

Подсчитаем количество знаков для кодирования слова КОЛОБОК в каждом из этих случаев. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы О (она встречается чаще всех), следующим – код буквы К.

В первом случае длина кода букв О и К – бит, букв Л и Б – бит, для кодирования слова КОЛОБОК потребуется

бит.

В любом случае для кодирования слова КОЛОБОК потребуется минимум двоичных знака.

Ответ: 23

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 10 тыс. раз. С ним справились 48% пользователей.

12. Задание#T2320

Для передачи сообщений используются буквы A, B, C, D, E, F, G, H, I, J. Кодовые слова для некоторых букв приведены в таблице.

Буква	Кодовое слово	Буква	Кодовое слово	Буква	Кодовое слово
A		E		I
B		F		J
C		G
D		H

Каким должно быть кодовое слово минимальной длины для буквы G, чтобы код допускал однозначное декодирование?

Если имеется несколько подходящих кодовых слов, укажите кодовое слово, имеющее наименьшее числовое значение.

Показать ответ

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 8 тыс. раз. С ним справились 43% пользователей.

13. Задание#T784

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово , для буквы Б – кодовое слово . Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?

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

Показать ответ

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 16 тыс. раз. С ним справились 54% пользователей.

0 баллов сегодня

дней без пропуска

сб

вс

пн

вт

ср

чт

пт