.. -*- coding: utf-8; -*-

=============================
トリボナッチ文字列
=============================
| 初期文字 :math:`a` ， :math:`b` ， :math:`c` による :math:`n` 番目のトリボナッチ文字列

.. raw:: html
         
   　　　<script type="text/javascript"  src="../../_static/tribo.js">
         </script>

          <form onsubmit="return false;" autocomplete="off">
          <div>
          n = <input id="n" type="int" size="64" value="0"/>
		  </div>
		  <div>
		  a = <input id="a" type="text" size="64" value="a"/>
		  </div>
		  <div>
		  b = <input id="b" type="text" size="64" value="b"/>
          </div>
          <div>
		  c = <input id="c" type="text" size="64" value="c"/>
          </div>
		  </form>
		  <div style="word-wrap:break-word;"> ・Trib(<n>dummy</n>) = <tribo>dummy</tribo> </div>

| **注** ： :math:`n` に大きい値を入れすぎるとおかしくなります．(入力制限で :math:`n<25` としています)


定義
=========================================

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

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

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

- :math:`Trib_{\infty} = abacabaabacababacabaabacabacabaab...`

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

- :math:`Trib_1 = a`
- :math:`Trib_2 = ab`
- :math:`Trib_3 = abac`
- :math:`Trib_4 = abacaba`
- :math:`Trib_5 = abacabaabacab`
- :math:`Trib_6 = abacabaabacababacabaabac`


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



性質
========================

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


アルゴリズム
=========================================

:math:`n` 番目のトリボナッチ文字列を返す
--------------------------------------------

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

.. literalinclude:: /Scripts/Python/tribo1.py
   :pyobject: trib

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

.. literalinclude:: /Scripts/Python/tribo2.py
   :pyobject: trib