ГДЗ по информатике, 10 класс, Босова, номер 4.9: Обработка информации

Выпишем имеющиеся коды:

• A→1110
• B→0
• V→10
• G→110

Проверим, нарушают ли они префиксное условие между собой:

• Код B=0 не является началом 1110, 10, 110. Не является началом ничего из них.
• Код V=10 не является началом 1110 (11...), 110 (11...). Не начинается с 0.
• Код G=110 не является началом 1110 (111...). Не начинается с 0 или 10.
• Код A=1110 самый длинный, он не может быть началом других.

Таким образом, текущий набор кодов уже является префиксным. Нам нужно добавить код для D, который также будет соответствовать этому правилу.

Будем перебирать двоичные последовательности по возрастанию длины, начиная с минимально возможной.

Длина 1

• 0: Занят буквой B. Нельзя использовать, так как это дублирование.
• 1: Является началом кодов V(10), G(110), A(1110). Если мы выберем код 1 для D, то строка 10 можно прочитать как DV или просто V. Это нарушение однозначности. Нельзя.

Длина 2

• 00: Начинается с 0 (код B). Строку 00 можно прочитать как BB или D. Нарушение. Нельзя.
• 01: Начинается с 0 (код B). Строку 01... можно начать читать как B, а остаток как часть другого кода. Но главное: сам код 01 не является началом существующих кодов (10,110,1110 начинаются с 1; 0 короче). Однако, если код D=01, то при встрече последовательности 01 мы однозначно считаем её как D. А что если встречается 010? Это DB или D...? Нет, проблема в том, что 01 не должно быть началом других кодов. Существующие коды начинаются с 0 только B=0. Код B короче D, поэтому B не может быть началом D. Может ли D быть началом B? Нет, 01 длиннее 0. Может ли D быть началом V,G,A? Они начинаются с 1. Значит, 01 не конфликтует с ними как префикс. Но давайте проверим обратное: не являются ли существующие коды префиксами 01? 0 — да! Код B=0 является префиксом кода D=01. Это значит, что последовательность 01 можно интерпретировать как B followed by something starting with 1, or just D. Например, поток 010: это D then 0(B)? Или B then 10(V)? Да, 010=D+B (01 then 0) и 010=B+V (0 then 10). Однозначность нарушена. Нельзя.
• 10: Занят буквой V. Дублирование. Нельзя.
• 11: Является началом кодов G(110) и A(1110). Поток 110 можно прочитать как DG (11 then 0) или просто G (110). Нарушение. Нельзя.

Длина 3

• 000: Префикс 0 занят B. Нарушение (как и 01).
• 001: Префикс 0 занят B. Нарушение.
• 010: Префикс 0 занят B. Нарушение.
• 011: Префикс 0 занят B. Нарушение.
• 100: Префикс 10 занят V. Нарушение (100=V+0(B) vs D?). Да, 100 можно разложить как V,B (10,0) или D (100). Нарушение.
• 101: Префикс 10 занят V. Нарушение (101=V,...).
• 110: Занят буквой G. Дублирование.
• 111: Является началом кода A(1110). Поток 1110 можно прочитать как DA (111 then 0?? No, A is 1110). Wait. If D=111, then string 1110 is D followed by 0 (B)? Or is it A? Yes, 1110=A. Also 1110=D+B (111 then 0). Ambiguity. Cannot use.

Длина 4