トリボナッチ文字列

初期文字 \(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に対しては遅くなる．

• 再帰ではなくループを使ったもの（ /Scripts/Python/tribo2.py ）