Как решить: Ваня недавно открыл для себя азбуку Морзе?

Азбука Морзе v2

Ваня недавно открыл для себя азбуку Морзе, где каждую букву можно представить в виде двух сигналов длинного (тире) и короткого (точка). Но его беспокоит, что без использования разделителя между отдельными буквами одно и то же сообщение можно расшифровать несколькими способами, поэтому Ваня начал размышлять, как можно усовершенствовать данную систему кодировки букв.

Ваня узнал, что для однозначной расшифровки сообщения нужно, чтобы ни одна последовательность точек и тире для одной буквы не была началом другой последовательности для другой буквы. Вооружившись этой идеей и подсчитав, сколько раз каждый символ встречается в тексте, Ваня задумался: как придумать такие

кодовые слова для символов, чтобы закодировать текст с минимальным количеством точек и тире?

В таблице показано, сколько букв в тексте насчитал Ваня.

Помогите ему придумать для каждой буквы такую последовательность точек и тире, чтобы их суммарное количество, необходимое для кодирования текста, было минимальным. Обратите внимание: Ваня хочет, чтобы в дальнейшем данный текст можно было однозначно расшифровать.

Как решить: Ваня недавно открыл для себя азбуку Морзе?
0
Жалоба

Ответы (2)

Запишем все буквы в порядке убывания числа употреблений буквы в тексте и назначим более длинные последовательности точек и тире буквам с меньшей частотой употребления в тексте:

Буква ​ ​ ​ ​ ​ ​ ​ Число ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ Последовательность

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ употреблений ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ шифрования

А ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 100 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ —

Б ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 90 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ . —

В ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 25 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ . .— .

Р ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 15 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ . . .—

Г ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 11 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ . .— — .

О ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 10 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ . .— — —

П ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 9 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ . . . . —

У ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 5 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ . . . . .

Весь текст займёт

100+90*2+25*4+15*4+(11+10+9+5)*5=615 символов азбуки Морзе (один символ это либо точка либо тире)

Ответить
+2

Если Ваня формирует текст без раздилительных знаков, то, для определения начала кода буквы нужно установить чтобы каждая буква начиналась с одного и того же символа. Все равно какой это будет символ - точка или тире. Возьмем, к примеру тире. Внутри кода буквы тире не должно появляться, иначе это будет воспринято как новая буква.

Таким образом, все буквы будут иметь вид: вначале тире, затем разное количество точек:

1) -

2) -.

3) -..

4) -... и так далее.

Чтобы текст получился наиболее компактным, нужно назначить самые короткие коды наиболее употребляемым буквам, а самые длинные - малоупотребляемым.

В этом случае, кодировка должна быть такой:

Буква ​ ​ ​ ​ ​ ​ ​ Число ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ Код ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ Количество знаков

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ употреблений ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ в коде ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

А ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 100 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​​ ​ ​ ​​ ​ ​ ​1

Б ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 90 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — . ​ ​ ​ ​ ​ ​ ​ ​ ​​ ​ ​​ ​ ​ ​ ​2

В ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 25 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — . . ​ ​ ​ ​ ​ ​ ​ ​​ ​ ​ ​ ​ ​3

Р ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 15 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — . . . ​ ​ ​ ​ ​ ​ ​​ ​ ​ ​ ​4

Г ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 11 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — . . . . ​ ​ ​ ​ ​ ​ ​ ​ ​ ​5

О ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 10 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — . . . . . ​ ​ ​ ​ ​ ​ ​ ​​6

П ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 9 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — . . . . . . ​ ​ ​ ​ ​ ​7

У ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 5 ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ — . . . . . . . ​ ​ ​ ​​8

В этом случае длина всего текста составит:

100 + 90*2 + 25*3 + 15*4 + 11*5 + 10*6 + 9*7 + 5*8 = 633 знака

Ответить
+2
Этот код противоречит условию задачи:
Необходимо, чтобы ни одна последовательность точек и тире для одной буквы не была началом другой последовательности.
А здесь код каждой буквы, кроме У, является началом кода следующей буквы.
Ответить
© 2012-2026 myanswer.ru
Все вопросы, размещенные на данном сайте, созданы пользователями или собраны из открытых источников. Связаться