Padovan文字列

初期文字 \(a\)\(b\) による \(n\) 番目のPadovan文字列
n =
a =
b =
c =
・Pad(n) = dummy
\(n\) に大きい値を入れすぎるとおかしくなります.(入力制限で \(n < 55\) としています.50を超えると処理に時間がかかります.)
アルゴリズムは文字の置き換えを使用.

定義

\(n\) 番目の Padovan文字列 (Padovan string) \(Pad_n\) を次の漸化式で定義する.

  • \(Pad_0 = a\)
  • \(Pad_1 = b\)
  • \(Pad_2 = c\)
  • \(Pad_{n} = Pad_{n-3} + Pad_{n-2}\) \((n \geq 3)\)

また,\(Pad_{n}\) は,\(Pad_{n-1}\) に対して次の規則に従った変換を行うことにより生成することもできる. ただし,\(Pad_0 = a\) とする.

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

例えば,最初の10個のPadovan文字列は次の通り.

  • \(Pad_0 = a\)
  • \(Pad_1 = b\)
  • \(Pad_2 = c\)
  • \(Pad_3 = ab\)
  • \(Pad_4 = bc\)
  • \(Pad_5 = cab\)
  • \(Pad_6 = abbc\)
  • \(Pad_7 = bccab\)
  • \(Pad_8 = cababbc\)
  • \(Pad_9 = abbcbccab\)

その長さの系列は 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 であり,これはPadovan数列である.

性質

アルゴリズム集

\(n\) 番目のPadovan文字列を返す

漸化式を用いたもの /Scripts/Python/padovan1.py

以下の変換規則を用いたもの /Scripts/Python/padovan2.py

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

無限Padovan文字列の \(n\) 番目の文字を返す