Задание 4 ЕГЭ по информатике

1. 1. А=0 занимает всю левую ветвь от корня — значит любой код, начинающийся с 0, нарушит Фано (А будет его префиксом).
2. 2. Значит В должен начинаться с 1. Код «1» нельзя: он префикс для Б=10.
3. 3. Свободен путь 11 — это лист, никаких конфликтов. В=11.
4. 4. Длина 2 — минимально возможная.

Ответ: В = 11

1. 1. Шаг 1. Ищем свободные вершины, спускаясь от корня. Корень — пустая строка, у него два потомка: 0 и 1.
2. 2. Шаг 2. Вершина 1. Начинается ли какой-нибудь занятый код с единицы? Коды 000 и 010 начинаются с нуля — нет. Значит, вершина 1 свободна целиком, вместе со всем поддеревом под ней.
3. 3. Шаг 3. Вершина 0. Оба занятых кода начинаются с нуля, значит вершина занята «транзитом»: сама она кодом быть не может (иначе стала бы началом кодов В и Д), но её поддерево содержит свободные места. Спускаемся: потомки 00 и 01.
4. 4. Шаг 4. Вершина 00. Код 000 начинается с 00 → снова транзит. Потомки: 000 (это код В, занят) и 001 — свободна.
5. 5. Шаг 5. Вершина 01. Код 010 начинается с 01 → транзит. Потомки: 010 (код Д, занят) и 011 — свободна.
6. 6. Шаг 6. Итог обхода: свободные вершины — 1 (длина 1), 001 (длина 3), 011 (длина 3). Их ровно три, и букв тоже три — значит, каждой достаётся своя вершина.
7. 7. Шаг 7. Сумма длин: 1 + 3 + 3 = 7. Например, А = 1, Б = 001, Г = 011. Проверим условие Фано: ни одно из пяти слов (000, 010, 1, 001, 011) не является началом другого ✔
8. 8. Шаг 8. Проверим, нельзя ли дешевле. Единственный способ что-то сократить — взять слово короче трёх знаков, но все вершины длиной 1 и 2, кроме уже взятой единицы, либо заняты, либо ведут к занятым кодам. Значит, 7 — минимум.

Ответ: 7

1. 1.
   • • def svobodnye(izvestnye):
   • • """Корни свободных поддеревьев кодового дерева."""
   • • svob, ochered = [], ['']

       while ochered:
           w = ochered.pop(0)
           if w in izvestnye:
               continue                       # вершина занята кодом
           if any(k.startswith(w) for k in izvestnye):
               ochered += [w + '0', w + '1']  # транзит: идём глубже
           elif w:
               svob.append(w)                 # свободный корень
           else:
               ochered += ['0', '1']          # корень дерева
       return svob

   def reshit(izvestnye, nuzhno):
       slova = sorted(svobodnye(izvestnye), key=len)
       while len(slova) < nuzhno:             # вершин мало — дробим короткую
           w = slova.pop(0)
           slova += [w + '0', w + '1']
           slova.sort(key=len)
       while True:                            # обмен: длинное на два коротких
           slova.sort(key=len)
           vybor = slova[:nuzhno]
           if len(vybor[0]) + 2 < len(vybor[-1]):
               k = vybor[0]
               slova.remove(k)
               slova.remove(vybor[-1])
               slova += [k + '0', k + '1']
           else:
               return vybor, sum(len(w) for w in vybor)

   print(reshit({'000', '010'}, 3))
   print(reshit({'101', '11'}, 4))
   print(reshit({'1111', '1001', '110'}, 4))

2. 2. Шаг 1. Как работает svobodnye. Обход идёт очередью, то есть в ширину — по возрастанию длины слов. Для каждой вершины три случая: она сама занята кодом (пропускаем всё поддерево), какой-то код начинается с неё (значит, это транзитная вершина — спускаемся к потомкам), или ни то ни другое (вершина свободна вместе со всем поддеревом).
3. 3. Шаг 2. Отдельная ветка для корня нужна потому, что пустая строка формально «является началом» любого кода, но кодом быть не может: она означала бы символ нулевой длины.
4. 4. Шаг 3. Первый цикл reshit добирает вершины дроблением, если их меньше, чем букв. Дробится всегда самая короткая — так прирост суммы наименьший.
5. 5. Шаг 4. Второй цикл делает обмен, разобранный выше: пока самое короткое из выбранных плюс два меньше самого длинного, дробим короткое и выбрасываем длинное. Условие строгое: при равенстве обмен ничего не даёт, а цикл зациклился бы.
6. 6. Шаг 5. Что печатает программа. Для {000, 010} и трёх букв: (['1', '001', '011'], 7). Для {101, 11} и четырёх букв: (['01', '100', '000', '001'], 11). Для {1111, 1001, 110} и четырёх букв: (['00', '01', '101', '1000'], 11) — тот самый случай, где наивный подсчёт давал 12.
7. 7. Шаг 6. Программа проверена на всех пятидесяти заданиях линии 4 из банка ФИПИ и на каждом даёт ответ, совпадающий с эталонным. Это не значит, что на экзамене надо её набирать: задача решается на бумаге за три минуты. Но она даёт то, чего бумага не даёт, — уверенность в правиле обмена, которое иначе выглядит как произвольная хитрость.

Ответ: 7; 11; 11

1. 1. Шаг 1. В этой формулировке спрашивают не сумму длин, а одно конкретное слово. Метод тот же: обойти дерево и найти свободные вершины.
2. 2. Шаг 2. Вершина 0. Коды 00 и 01 начинаются с нуля — значит, сама вершина занята транзитом, спускаемся. Потомки 00 и 01 — оба заняты кодами А и Б. Вся левая половина дерева закрыта.
3. 3. Шаг 3. Вершина 1. Коды 100, 1010 и 1011 начинаются с единицы — транзит, спускаемся к 10 и 11.
4. 4. Шаг 4. Вершина 11. Начинается ли с неё какой-нибудь занятый код? Нет: занятые начинаются с 00, 01, 100, 1010, 1011. Значит, 11 свободна вместе со всем поддеревом.
5. 5. Шаг 5. Вершина 10. Транзит (под ней 100, 1010, 1011). Потомки: 100 — занят кодом В; 101 — транзит, под ним 1010 и 1011, оба заняты. Здесь свободного места нет.
6. 6. Шаг 6. Итог обхода: единственная свободная вершина — 11, длина 2. Это и есть кратчайшее возможное кодовое слово для Е.
7. 7. Шаг 7. Проверяем условие Фано для всего набора: 00, 01, 100, 1010, 1011, 11. Ни одно слово не является началом другого — двойка начинается с «11», а таких среди занятых нет, и сама она ни с чего не начинается ✔
8. 8.

   Шаг 8. Проверка программой (та же функция, что и в разборе выше):

   print(svobodnye({'00', '01', '100', '1010', '1011'}))

9. 9. Шаг 9. Печатается список из одной вершины: ['11'] ✔ Если бы свободных вершин оказалось несколько, кратчайшим был бы ответ с наименьшей длиной, а при равной длине годился бы любой — в ответ идёт одно слово, и проверяется оно по условию Фано, а не по совпадению с эталоном.
10. 10. Шаг 10. Частая ошибка этой формулировки — предложить слово 110 или 111. Оба свободны (они лежат внутри поддерева вершины 11), оба не нарушают условие Фано, но они длиннее, а спрашивают кратчайшее. Берите корень свободного поддерева, а не его потомка.

Ответ: 11