フィボナッチ文字列

初期文字 \(a\) と \(b\) による \(n\) 番目のフィボナッチ文字列
n =
a =
b =
・Fib(n) = dummy
注 ： \(n\) に大きい値を入れすぎるとおかしくなります．(入力制限で \(n<35\) としています)

定義

以下の漸化式によって定義される \(Fib_n\) を \(n\) 番目の フィボナッチ文字列 (Fibonacci string) という．

  • \(Fib_0 = \varepsilon\),
  • \(Fib_1 = b\)
  • \(Fib_2 = a\)
  • \(Fib_{n} = Fib_{n-1} \cdot Fib_{n-2}\) \((n \geq 2)\)

また，この手続きを無限に繰り返してできる無限文字列を 無限フィボナッチ文字列 という．

  • \(Fib_{\infty} = abaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaa...\)

\(Fib_n\) は， \(Fib_{n-1}\) に対して次の規則に従った変換を行うことにより生成することもできる． ただし， \(Pd_0 = a\) とする．

  • \(a → ab\)
  • \(b → a\)

例

例えば，最初の10個のフィボナッチ文字列は次の通り．

  • \(Fib_1 = b\)
  • \(Fib_2 = a\)
  • \(Fib_3 = ab\)
  • \(Fib_4 = aba\)
  • \(Fib_5 = abaab\)
  • \(Fib_6 = abaababa\)
  • \(Fib_7 = abaababaabaab\)
  • \(Fib_8 = abaababaabaababaababa\)
  • \(Fib_9 = abaababaabaababaababaabaababaabaab\)
  • \(Fib_{10} = abaababaabaababaababaabaababaabaababaababaabaababaababa\)

その長さの系列は 1, 1, 2, 3, 5, 8, 13, 21, 34, 56, ... であり，これはフィボナッチ数列である．

性質

  • 無限フィボナッチ文字列は周期的でない
  • フィボナッチ文字列の最後の2文字は"ab"と"ba"が交互に現れる
  • フィボナッチ文字列の最後の2文字を取り除く、もしくは最後の2文字の逆転列を最初に付け加えると回文になる。たとえばab = ababaababaで、これは回文である
  • 無限フィボナッチ文字列において、(文字列の長さ)/(aの数)は（黄金比）であり，aとbの比もこれに等しい
  • bbとaaaは発生しない
  • 無限フィボナッチ文字列は循環（どの一部の文字列も無限に再び現れる）する
  • フィボナッチ列は、黄金比の傾きまたはをもつ直線が切り出す列として特徴付けられる
  • 'b'はUpper Wythoff sequence の場所に現れる
  • 'a'はLower Wythoff sequence の場所に現れる

（上記は Wikipediaからの拝借）

アルゴリズム

\(n\) 番目のフィボナッチ文字列を返す

  • 定義に忠実にしたがって作ったもの( /Scripts/Python/fibo1.py)
  • 再帰呼び出しを多用しているので大きな \(n\) に対しては遅くなる．

無限フィボナッチ文字列の \(n\) 番目の文字を返す