Известны двоичные коды части букв, код удовлетворяет условию Фано. Нужно подобрать коды для остальных букв так, чтобы суммарная длина была наименьшей, или найти кратчайший код для одной буквы.
Условие Фано
Никакое кодовое слово не является началом другого.
Нельзя использовать код, который начинается с известного кода или является его началом.
Как решать
Найти свободные ветви — кратчайшие начала, не конфликтующие с известными кодами.
Короткую свободную ветвь выгодно отдать одной букве; если букв больше, чем ветвей, ветви делятся пополам.
Сложить длины полученных кодов.
Типичные ошибки
Забыть, что новый код не может быть началом известного (например, 1 при известном 10).
Делить длинную ветвь, когда есть свободная короче.
Сложить и длины известных кодов, хотя спрашивают только про оставшиеся буквы.
Разобранные варианты
Сначала реши сам, потом открой разбор. В разборе — свободные ветви дерева и программа на Python.
Вариант 1
8 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
Б
Е
Ж
00
11
100
01
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: В, Г, Д, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 101 (длина 3).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 4 букв так, чтобы сумма длин была наименьшей: в ветви 101 — 4 слова. Например: В — 10100, Г — 10101, Д — 10110, З — 10111. Сумма длин: 5 + 5 + 5 + 5 = 20.
Ответ: 20
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['00', '01', '100', '11']
k = 4 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best)
Вариант 2
8 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
В
Г
Ж
000
01
001
101
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Б, Д, Е, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 11 (длина 2), 100 (длина 3).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 4 букв так, чтобы сумма длин была наименьшей: в ветви 11 — 2 слова; в ветви 100 — 2 слова. Например: Б — 110, Д — 111, Е — 1000, З — 1001. Сумма длин: 3 + 3 + 4 + 4 = 14.
Ответ: 14
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['000', '001', '01', '101']
k = 4 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best)
Вариант 3
7 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
Б
Г
Д
Ж
1010
000
1100
1110
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, В, Е.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 01 (длина 2), 001 (длина 3), 100 (длина 3), 1011 (длина 4), 1101 (длина 4), 1111 (длина 4).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 3 букв так, чтобы сумма длин была наименьшей: в ветви 01 — 1 слово; в ветви 001 — 1 слово; в ветви 100 — 1 слово. Например: А — 01, В — 001, Е — 100. Сумма длин: 2 + 3 + 3 = 8.
Ответ: 8
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['000', '1010', '1100', '1110']
k = 3 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best)
Вариант 4
6 букв · код одной буквы
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для всех букв, кроме В, кодовые слова известны.
А
Б
Г
Д
Е
00
100
011
101
111
Укажите кратчайшее кодовое слово для буквы В, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 010, 110.
Шаг 2. Код для В должен быть свободной ветвью или начинаться с неё. Самые короткие свободные ветви имеют длину 3: 010, 110.
Шаг 3. Из них наименьшее числовое значение у 010.
Ответ: 010
Решение на Python.
from itertools import product
known = ['00', '011', '100', '101', '111']
for n in range(1, 10):
found = [''.join(p) for p in product('01', repeat=n)
if all(not (''.join(p).startswith(x) or x.startswith(''.join(p))) for x in known)]
if found:
print(found[0]) # product перебирает в порядке возрастания числового значения
break
Вариант 5
8 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
Г
Д
Ж
З
001
1100
1111
0100
0000
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Б, В, Е.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 10 (длина 2), 011 (длина 3), 0001 (длина 4), 0101 (длина 4), 1101 (длина 4), 1110 (длина 4).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 3 букв так, чтобы сумма длин была наименьшей: в ветви 10 — 1 слово; в ветви 011 — 1 слово; в ветви 1110 — 1 слово. Например: Б — 10, В — 011, Е — 1110. Сумма длин: 2 + 3 + 4 = 9.
Ответ: 9
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['0000', '001', '0100', '1100', '1111']
k = 3 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best)
Вариант 6
9 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З, И. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
Б
Г
Д
Е
011
100
001
010
11
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: В, Ж, З, И.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 000 (длина 3), 101 (длина 3).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 4 букв так, чтобы сумма длин была наименьшей: в ветви 000 — 2 слова; в ветви 101 — 2 слова. Например: В — 0000, Ж — 0001, З — 1010, И — 1011. Сумма длин: 4 + 4 + 4 + 4 = 16.
Ответ: 16
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['001', '010', '011', '100', '11']
k = 4 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best)
Вариант 7
7 букв · код одной буквы
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для всех букв, кроме Д, кодовые слова известны.
А
Б
В
Г
Е
Ж
01
1111
00
1000
1010
1110
Укажите кратчайшее кодовое слово для буквы Д, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 110, 1001, 1011.
Шаг 2. Код для Д должен быть свободной ветвью или начинаться с неё. Самые короткие свободные ветви имеют длину 3: 110.
Ответ: 110
Решение на Python.
from itertools import product
known = ['00', '01', '1000', '1010', '1110', '1111']
for n in range(1, 10):
found = [''.join(p) for p in product('01', repeat=n)
if all(not (''.join(p).startswith(x) or x.startswith(''.join(p))) for x in known)]
if found:
print(found[0]) # product перебирает в порядке возрастания числового значения
break
Вариант 8
8 букв · сумма всех кодов
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
Г
Е
Ж
З
0011
1010
11
0010
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину всех кодовых слов (для всех 8 букв).
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 01 (длина 2), 000 (длина 3), 100 (длина 3), 1011 (длина 4).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 4 букв так, чтобы сумма длин была наименьшей: в ветви 01 — 1 слово; в ветви 000 — 1 слово; в ветви 100 — 1 слово; в ветви 1011 — 1 слово. Например: А — 01, Б — 000, В — 100, Д — 1011. Сумма длин: 2 + 3 + 3 + 4 = 12.
Шаг 4. Спрашивают сумму для всех букв: прибавляем длины известных кодов 14. 12 + 14 = 26.
Ответ: 26
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['0010', '0011', '1010', '11']
k = 4 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best + 14) # плюс длины известных кодов
Вариант 9
9 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З, И. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
Б
В
Г
Д
Е
Ж
01
10
00
1100
1101
1111
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, З, И.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 1110 (длина 4).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 3 букв так, чтобы сумма длин была наименьшей: в ветви 1110 — 3 слова. Например: А — 11100, З — 111010, И — 111011. Сумма длин: 5 + 6 + 6 = 17.
Ответ: 17
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['00', '01', '10', '1100', '1101', '1111']
k = 3 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best)
Вариант 10
10 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
Г
Д
Ж
И
К
1001
0100
0110
1111
1110
1011
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Б, В, Е, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Разбор
Шаг 1. Ищем свободные ветви. Представим коды как пути в двоичном дереве: 0 — влево, 1 — вправо. Известные коды занимают листья. Свободная ветвь — это кратчайшее начало, которое не является началом известного кода и само не начинается с известного кода. Свободные ветви: 00 (длина 2), 110 (длина 3), 0101 (длина 4), 0111 (длина 4), 1000 (длина 4), 1010 (длина 4).
Шаг 2. Сколько стоит ветвь. В ветви длины l можно разместить одно слово длины l, два слова длины l+1, три слова длин l+1, l+2, l+2, четыре слова длины l+2 и так далее: каждое разветвление удлиняет коды.
Шаг 3. Распределяем 4 букв так, чтобы сумма длин была наименьшей: в ветви 00 — 1 слово; в ветви 110 — 1 слово; в ветви 1000 — 1 слово; в ветви 1010 — 1 слово. Например: Б — 00, В — 110, Е — 1000, З — 1010. Сумма длин: 2 + 3 + 4 + 4 = 13.
Ответ: 13
Решение на Python. Перебор наборов слов с отсечением: ищем набор, совместимый с известными кодами, с наименьшей суммой длин.
from itertools import product
known = ['0100', '0110', '1001', '1011', '1110', '1111']
k = 4 # сколько букв нужно закодировать
def ok(w, used):
return all(not (w.startswith(x) or x.startswith(w)) for x in used)
words = [''.join(p) for n in range(1, 7) for p in product('01', repeat=n)]
best = None
def search(start, used, left, total):
global best
if best is not None and total >= best:
return
if left == 0:
best = total
return
for i in range(start, len(words)):
w = words[i]
if ok(w, used):
search(i + 1, used + [w], left - 1, total + len(w))
search(0, known, k, 0)
print(best)
Для самостоятельного решения
Варианты 11–15 без разборов. Ответ можно проверить кнопкой.
Вариант 11
8 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
Д
Е
З
00
1000
0110
1010
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Б, В, Г, Ж.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Вариант 12
7 букв · код одной буквы
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для всех букв, кроме Б, кодовые слова известны.
А
В
Г
Д
Е
Ж
10
00
0100
1110
011
0101
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Вариант 13
9 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З, И. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
В
Г
Д
Е
И
11
101
100
0001
01
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Вариант 14
8 букв · сумма всех кодов
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
А
Г
Е
Ж
З
110
1010
011
001
100
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину всех кодовых слов (для всех 8 букв).
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Вариант 15
10 букв · сумма для оставшихся
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З, И, К. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
В
Д
Е
Ж
И
К
010
0111
111
1101
10
00
Какое наименьшее количество двоичных знаков требуется для кодирования оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, Г, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.