Hanoi 文字列¶
ハノイの塔の解を表現する文字列．
\(N\) 番目のHanoi文字列
・H2N = dummy
・H2N+1 = dummy
注 ：\(n\) を大きい数にするとおかしくなります．(入力制限で \(n<20\) としています)
定義¶
2N枚の円盤を用いる時の解は次の式で表される．
\(H_0 = \varepsilon\)
\(H_{2N+1}=H_{2N} a \sigma^{-1}(H_{2N}) (N \geq 0)\)
\(H_{2N}=H_{2N-1} \overline{c} \sigma(H_{2N-1}) (N \geq 1)\)
\(\sigma，\sigma^{-1}\) はそれぞれ次の通りである．
\(\sigma(a) \to b\) \(\sigma(b) \to c\) \(\sigma(c) \to a\) \(\sigma(\overline{a}) \to \overline{b}\) \(\sigma(\overline{b}) \to \overline{c}\) \(\sigma(\overline{c}) \to \overline{a}\)
\(\sigma^{-1}(a) \to c\) \(\sigma^{-1}(b) \to a\) \(\sigma^{-1}(c) \to b\) \(\sigma^{-1}(\overline{a}) \to \overline{c}\) \(\sigma^{-1}(\overline{b}) \to \overline{a}\) \(\sigma^{-1}(\overline{c}) \to \overline{b}\)