.. -*- coding: utf-8; -*- ========================================== Padovan文字列 ========================================== | 初期文字 :math:`a` と :math:`b` による :math:`n` 番目のPadovan文字列 .. raw:: html    
n =
a =
b =
c =
・Pad(n) = dummy
| **注** ::math:`n` に大きい値を入れすぎるとおかしくなります.(入力制限で :math:`n < 55` としています.50を超えると処理に時間がかかります.) | アルゴリズムは文字の置き換えを使用. 定義 ========================================= :math:`n` 番目の **Padovan文字列** *(Padovan string)* :math:`Pad_n` を次の漸化式で定義する. - :math:`Pad_0 = a` - :math:`Pad_1 = b` - :math:`Pad_2 = c` - :math:`Pad_{n} = Pad_{n-3} + Pad_{n-2}` :math:`(n \geq 3)` また,:math:`Pad_{n}` は,:math:`Pad_{n-1}` に対して次の規則に従った変換を行うことにより生成することもできる. ただし,:math:`Pad_0 = a` とする. - :math:`a → b` - :math:`b → c` - :math:`c → ab` 例えば,最初の10個のPadovan文字列は次の通り. - :math:`Pad_0 = a` - :math:`Pad_1 = b` - :math:`Pad_2 = c` - :math:`Pad_3 = ab` - :math:`Pad_4 = bc` - :math:`Pad_5 = cab` - :math:`Pad_6 = abbc` - :math:`Pad_7 = bccab` - :math:`Pad_8 = cababbc` - :math:`Pad_9 = abbcbccab` その長さの系列は 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 であり,これはPadovan数列である. 性質 ======================== アルゴリズム集 ========================================= :math:`n` 番目のPadovan文字列を返す ----------------------------------------- 漸化式を用いたもの :download:`/Scripts/Python/padovan1.py` .. literalinclude:: /Scripts/Python/padovan1.py :pyobject: pad 以下の変換規則を用いたもの :download:`/Scripts/Python/padovan2.py` - :math:`a → b` - :math:`b → c` - :math:`c → ab` .. literalinclude:: /Scripts/Python/padovan2.py :pyobject: pad 無限Padovan文字列の :math:`n` 番目の文字を返す ------------------------------------------------ .. todo:: | **誰かよろしく.** 愚直な,遅いバージョン以外にも,効率のよいものが書けるのか? | 何番目の文字列に出現するかを求めてから文字を返す