AAA
/ \
BAA-CAA
/     \
BCA     CBA
/ \     / \
CCA-ACA-ABA-BBA
/             \
CCB             BBC
/ \             / \
ACB-BCB         CBC-ABC
/     \         /     \
ABB     BAB     CAC     ACC
/ \     / \     / \     / \
BBB-CBB CAB-AAB-AAC-BAC-BCC-CCC

#{{{
\begin{eqnarray}
\nonumber \\
\text{證明 } S_n &=& 2^n - 1, n \in \mathbb{N^+} \nonumber \\
\nonumber \\
n = 1, \nonumber \\
S_1 &=& 2^1 - 1 = 1 \text{ (成立)} \nonumber \\
\nonumber \\
\text{假設 } n = k, \nonumber \\
S_{k} &=& 2^k - 1 \nonumber \\
\nonumber \\
n = k + 1, \nonumber \\
S_{k + 1} &=& S_k + 1 + S_k \nonumber \\
&=& 2^k - 1 + 1 + 2^k - 1 \nonumber \\
&=& 2^k + 2^k - 1 + 1 - 1 \nonumber \\
&=& 2 \times 2^k - 1 \nonumber \\
&=& 2^{k + 1} - 1 \nonumber \\
\nonumber \\
\therefore S_n &=& 2^n - 1, n \in \mathbb{N^+} \text{ 是正確的}
\end{eqnarray}
}}}#

#### 程式寫出來了，但還是不知道怎麼玩河內塔……

• 0. 判斷碟片的數量是奇數還是偶數，來決定最小的碟片和第二小的碟片移動時的方向。偶數往右；奇數往左。
• 1. 移動最小的碟片一個桿子的距離。
• 2. 移動第二小的碟片兩個桿子的距離。
• 3. 移動最小的碟片一個桿子的距離。(將最小的碟片移動到第二小的碟片上。)
• 4. 移動其它的碟片。

#### 不用堆疊空間的河內塔迭代演算法

Move a disk from A to C.
Move a disk from A to B.
Move a disk from C to B.
Move a disk from A to C.
Move a disk from B to A.
Move a disk from B to C.
Move a disk from A to C.

Move a disk from A to B.
Move a disk from A to C.
Move a disk from B to C.
Move a disk from A to B.
Move a disk from C to A.
Move a disk from C to B.
Move a disk from A to B.

Move a disk from B to C.
Move a disk from B to A.
Move a disk from C to A.
Move a disk from B to C.
Move a disk from A to B.
Move a disk from A to C.
Move a disk from B to C.

• 0: A→B
• 1: A→C
• 2: B→A
• 3: B→C
• 4: C→A
• 5: C→B

• 1: A→B
• 0: A→C
• 4: B→A
• 5: B→C
• 2: C→A
• 3: C→B

• 3: A→B
• 2: A→C
• 5: B→A
• 4: B→C
• 0: C→A
• 1: C→B

#### 利用碟片的輸出規律來實現不用堆疊空間的河內塔迭代版函數

1  2  1  3  1  2  1  4  1  2  1  3  1  2  1

1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1

1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  6  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1

#{{{
a_n = \lfloor log_2{(n \text{ } XOR \text{ } (n + 1))} \rfloor + 1, n \in \mathbb{N^0}
}}}#