8 Шпаргалка по заданию 4
Шпаргалка по заданию 4
Условие Фано
Ни один код не является началом (префиксом) другого.
На дереве: все коды сидят в ЛИСТЬЯХ, ни один не стоит по пути к другому.Дерево кода
влево = 0 вправо = 1
код = путь от корня до листа
занятый лист закрывает всю ветку под собойПорядок решения (типы 1 и 2)
1. Нарисовать дерево, отметить известные коды (занятые листья).
2. Найти свободные ветки (куда ещё можно поставить код).
3. Тип 1: посадить буквы в самые короткие ветки, дробя при нехватке; сложить длины.
Тип 2: взять кратчайшую свободную ветку; при нескольких вариантах —
нужное числовое значение (наименьшее или наибольшее).Python (жадная упаковка для типа 1)
import heapq
def free_branches(occ):
occ=set(occ); free=[]; stack=['']
while stack:
c=stack.pop()
if c in occ: continue
if any(o.startswith(c) and o!=c for o in occ): stack+=[c+'0', c+'1']
else: free.append(c)
return free
free=[len(b) for b in free_branches(fixed)]; heapq.heapify(free)
while len(free)<k: # k = сколько букв разместить
d=heapq.heappop(free); heapq.heappush(free,d+1); heapq.heappush(free,d+1)
print(sum(len(x) for x in fixed)+sum(sorted(free)[:k]))⚠️ Типичные ошибки 1. Забыл про условие Фано и повесил код на уже занятую ветку. Проверь: все коды — в листьях, ни один не стоит по пути к другому. 2. Посадил две буквы в одну ветку без деления. В ветку длины 3. В типе 1 взял не самые короткие свободные ветки — сумма получилась больше минимальной. Всегда начинай с самых высоких веток. 4. В типе 2 нашёл кратчайший код, но не оставил место для второй неизвестной буквы. Если букв две — короткую ветку придётся разделить. 5. Перепутал, что просят: наименьшее или наибольшее числовое значение кода. Читай последнюю строку условия внимательно. 6. Потерял ведущий ноль в ответе. Код |
💡 Последнее напутствие Задание 4 — почти гарантированный балл, если не решать его в уме. Нарисуй дерево, отметь занятые коды, найди свободные ветки — и ответ окажется прямо перед глазами. Всё задание держится на одной мысли: занятый код закрывает всю ветку под собой. Определи тип задачи (сумма длин, выбор кода или кодирование слова), примени правило коротких веток — и балл твой. А если картина сложная, перепроверь себя коротким кодом на Python. Удачи на экзамене — Профиматика с тобой! |