Задание 4 ЕГЭ: условие Фано

11 класс, углублённый уровень. Практикум: неравномерный двоичный код, свободные ветви дерева и самый короткий код. Решаем деревом.

Что нужно сделать
Семь задач — по одной на каждый тип, все на экране сразу, решай в любом порядке. Первые три типа — про то, как устроено дерево кода; четыре следующих — задание 4 в том виде, как на ЕГЭ.
Баллы
Балл даёт каждый верно решённый тип. Семь — «5», шесть — «4», пять — «3».
Ошибся — не страшно
Разбор с деревом появится сразу. Кнопка «Новые числа» даст задачу того же типа с другими данными: балл можно доработать. Отдельно видно, сколько сделано с первой попытки.
Ответ
Число — целое, без пояснений: 17. Кодовое слово — нулями и единицами подряд: 1100. Буквы — подряд, без пробелов. Сверка знак в знак, как на КЕГЭ.

Задачи

освоено типов 0 из 7, это—

Подсказка: как решать задание 4 деревом

Условие Фано и дерево

Никакое кодовое слово не является началом другого — тогда расшифровка однозначна. На дереве (корень наверху, 0 — влево, 1 — вправо) это значит: каждая буква — лист, ни одна не сидит на пути к другой.

0010111010Б00Н010Л111·10·011·110

Демо 2027: Б – 00, Н – 010, Л – 111. Пунктир — свободные ветви 011, 10, 110.

Свободные ветви

Узел, куда не легло слово и через который не идёт путь к слову. Новые буквы садятся только туда. Ветка длины d делится: 2 слова длины d+1, 4 — длины d+2…

Наименьшая длина — четыре шага

  1. Дерево известных слов, свободные ветви.
  2. Сколько раз каждая неизвестная буква встречается в слове.
  3. Букв больше, чем ветвей, — делим короткие ветки. Короткие слова — частым буквам. Сравни два-три разбиения.
  4. Сумма «сколько раз × длина» по всем буквам слова, известным тоже.

Кратчайшее слово с наименьшим значением

Самый высокий свободный узел; если их несколько на одной глубине — левый (0 левее 1).

Три ловушки

Откуда эти задачи

Задачи авторские, составлены в форме задания 4 ЕГЭ по информатике. Форма задания и способ решения — как на экзамене, а условия написаны своими словами. Коды и слова каждый раз новые.

Материалы подготовлены с использованием технологий искусственного интеллекта.