トリボナッチ文字列

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

定義

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

  • \(Trib_0 = \varepsilon\)
  • \(Trib_1 = a\)
  • \(Trib_2 = ab\)
  • \(Trib_3 = abac\)
  • \(Trib_{n} = Trib_{n-1} \cdot Trib_{n-2} \cdot Trib_{n-3}\) \((n \geq 4)\)

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

  • \(Trib_{\infty} = abacabaabacababacabaabacabacabaab...\)

例

例えば，最初の6個のトリボナッチ文字列は次の通り．

  • \(Trib_1 = a\)
  • \(Trib_2 = ab\)
  • \(Trib_3 = abac\)
  • \(Trib_4 = abacaba\)
  • \(Trib_5 = abacabaabacab\)
  • \(Trib_6 = abacabaabacababacabaabac\)

その長さの系列は 1, 2, 4, 7, 13, 24, 44, .... であり，これはトリボナッチ数列である．

性質

  • フィボナッチ文字列に項を追加して拡張した文字列

アルゴリズム

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

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