Słowa Fibonacciego
Wygląd
Słowa Fibonacciego – ciąg słów stosowany w informatyce teoretycznej między innymi do analizy złożoności algorytmów tekstowych.
Definicja słów Fibonacciego
[edytuj | edytuj kod]Słowa Fibonacciego są słowami nad alfabetem zdefiniowany rekurencyjnie jako:
Gdzie symbol oznacza konkatenację.
Początkowe słowa Fibonacciego
[edytuj | edytuj kod]Własności słów Fibonacciego
[edytuj | edytuj kod]- gdzie jest -tą liczbą Fibonacciego.
Niech oznacza słowo z ostatnimi dwoma literami zamienionymi kolejnością. Zachodzi:
Zobacz też
[edytuj | edytuj kod]Uwagi
[edytuj | edytuj kod]Nie ma jednej konwencji dotyczącej oznaczania początkowych słów Fibonacciego. W niektórych źródłach przyjmuje się w innych z kolei
Alfabet nie jest konieczny (choć jest często używany). Można równie dobrze używać alfabetu lub innego dwuznakowego.
Bibliografia
[edytuj | edytuj kod]- Lech Banachowski, Krzysztof Diks, Wojciech Rytter, Algorytmy i struktury danych, Warszawa: WNT, 1996, s. 169, ISBN 83-204-1995-6, OCLC 69370054 .
Linki zewnętrzne
[edytuj | edytuj kod]Fibonacci word (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].