Азбука Морзе [Комбинаторика]

[Whitaker]

Здравствуйте уважаемые!
Попалась такая задачка. Подскажите пожалуйста как ее решить.
Некоторый алфавит состоит из 6 букв, которые для передачи по телеграфу кодированы так: ., -, .., - -,-., .-
При передаче одного слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка из точек и тире, содержащая 12 знаков. Сколькими способами можно прочитать переданное слово?

С уважением, Whitaker.

[Хорхе]

Алфавит, понятное дело, не имеет значения, а количество способов равно количеству композиций в сумму единиц и двоек, то есть числу Фибоначчи.

[Whitaker]

Хорхе а почему количество равно количеству композиций в сумму единиц и двоек?

[Хорхе]

Потому что у нас буквы в алфавите состоят из одного знака и из двух. Композицией последовательность букв определяется однозначно, и наоборот.

-- Чт дек 01, 2011 22:02:05 --

Например, meatman = 2+1+2+1+2+2+2 = -- . .- - -- .- -.
teammate = 1+1+2+2+2+2+1+1 = - . .- -- -- .- - .

[Whitaker]

Но ведь etmamate - 1+1+2+2+2+2+1+1 ?
Неоднозначное получается что-то

[Хорхе]

etmamate отвечает другой исходной последовательности точек и тире.

Для фиксированной последовательности точек и тире (а в условии она фиксирована) композиция, очевидно, однозначно определяет слово.

[Whitaker]

Хорхе в сообщении #510545 писал(а):

Алфавит, понятное дело, не имеет значения, а количество способов равно количеству композиций в сумму единиц и двоек, то есть числу Фибоначчи.

Но ведь она всё-таки соотвествует последовательности: 11222211?

[Хорхе]

Вот у Вас есть последовательность
-.-

Сколько слов из нее можно получить?

[Whitaker]

Хорхе в сообщении #510605 писал(а):

Вот у Вас есть последовательность
-.-

Сколько слов из нее можно получить?

Всего лишь три

[Хорхе]

Ну вот, и это TA=1+2, NT=2+1, TET=1+1+1.

Слова TEE"="1+1+1", IT"="2+1 и ME"="2+1 получить из нее нельзя.

[Whitaker]

T,A,E - это буквы алфавита?

[Хорхе]

T=-
A=.-
E=.
N=-.
(там была ошибочка, исправил)

[Whitaker]

Хорхе в сообщении #510545 писал(а):

Алфавит, понятное дело, не имеет значения, а количество способов равно количеству композиций в сумму единиц и двоек, то есть числу Фибоначчи.

Хорхе, а какая связь между числом композиций в сумму единиц и двоек и числом Фибоначчи?

[svv]

Пусть $A_k$ -- количество способов, которыми можно последовательность из $k$ знаков разбить на одно- и двухзнаковые буквы.

Рассмотрим последовательность из $n$ знаков. Последний знак входит либо в однознаковую букву, либо в двухзнаковую.
Если последний знак входит в однознаковую букву, то часть последовательности без последней буквы содержит $n-1$ знаков и может быть разбита на буквы $A_{n-1}$ способами.
Если последний знак входит в двухзнаковую букву, то часть последовательности без последней буквы содержит $n-2$ знаков и может быть разбита на буквы $A_{n-2}$ способами.
В каждом из этих способов мы имеем вполне определенное разбиение (знаем, как отделить последнюю букву, и знаем, как разбить предыдущую часть последовательности).

Итого $A_n=A_{n-1}+A_{n-2}$ способов, что совпадает с рекуррентной формулой для чисел Фибоначчи. Считайте, что это шаг индукции, а базу Вы легко докажете сами.

[Whitaker]

svv я Вас понял
Действительно получается последовательность Фибоначчи