Слово Фибоначчи — различия между версиями
(→Лемма) |
|||
Строка 4: | Строка 4: | ||
а каждой строке <tex>x</tex> из <tex>A^+</tex> ставит в соответсвие строку из <tex>A^+</tex> по следующему правилу : | а каждой строке <tex>x</tex> из <tex>A^+</tex> ставит в соответсвие строку из <tex>A^+</tex> по следующему правилу : | ||
<tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex> , где <tex>x[1], x[2], \dots, x[n]</tex> уже являются элементами <tex>A</tex>. | <tex>h(x) = h(x[1])h(x[2])...h(x[n])</tex> , где <tex>x[1], x[2], \dots, x[n]</tex> уже являются элементами <tex>A</tex>. | ||
− | + | *<tex>h : A \rightarrow A^+</tex> | |
+ | *<tex>h : A^+ \rightarrow A^+</tex> | ||
}} | }} | ||
Версия 15:02, 1 мая 2012
Определение
Определение: |
Морфизмом называется отображение а каждой строке из ставит в соответсвие строку из по следующему правилу : , где уже являются элементами . | , которое каждой букве из алфавита ставит в соответствие строку из множества ,
Любой морфизм можно применять к исходной строке любое число раз, тем самым генерируя последовательность итераций по следующему правилу:
.
где и для любого целого .
Например:
.
Определение: |
Строками Фибоначчи являются строки, полученные последовательным применением морфизма | к строке , т.е. .
Первые несколько строк Фибоначчи:
Лемма
Лемма: |
Строки Фибоначчи удовлетворяют рекуррентному соотношению . |
Доказательство: |
Доказательство нетрудно получить методом математической индукции. База: При равенство очевидно.Переход: Пусть . . Т.к. h — линейна (т.е. ), то можно продолжить равенство: . |
Также нетрудно заметить, что длины строк Фибоначчи совпадают с числами Фибоначчи.
Литература
- Билл Смит. Методы и алгоритмы вычислений на строках. Пер. с англ. — М.:ООО"И.Д.Вильямс", 2006. — 496 с.: ил. — Парал. тит. англ. ISBN 5-8459-1081-1 (рус.)