---
# System prepended metadata

title: 河內塔
tags: [初階班]

---

# 河內塔

圖片來源:https://tygtw.ddns.net/game/hanoi/
## 河內塔的移動
這是一個N=5的河內塔
我們要把它移動到目標柱(tower3)
步驟:
移動N=4的河內塔到暫存柱(tower2)
移動綠色到目標柱(tower3)
移動N=4的河內塔到目標柱(tower2)
![](https://i.imgur.com/iTenWKJ.png)
![](https://i.imgur.com/STC5djT.png)
![](https://i.imgur.com/kQLKmMS.png)
![](https://i.imgur.com/FbVTDjB.png)

我們先不要管綠色
那要怎麼移動N=4的河內塔呢
移動N=3的河內塔
移動藍色
移動N=3的河內塔

![](https://i.imgur.com/XS1A4z1.png)
![](https://i.imgur.com/ASHIzWU.png)
![](https://i.imgur.com/PWbGGuA.png)
![](https://i.imgur.com/325MAV8.png)

一樣不要管藍色
我們要怎麼移動N=3的河內塔呢
移動N=2的河內塔
移動紫色
移動N=2的河內塔

![](https://i.imgur.com/jIaQbBw.png)
![](https://i.imgur.com/3ObgCyf.png)
![](https://i.imgur.com/RdbUHvQ.png)
![](https://i.imgur.com/U5zV7In.png)

以此類推

我們在這之中可以發現河內塔就是一個遞迴
我們呼叫函式要移動N=3的塔
這個函式不知道怎麼移動
所以把問題拆開
再問了N=2怎麼移動
函式還是不知道怎麼移動
所以她又把問題拆開
問了N=1怎麼移動
他知道了N=1怎麼移動

開始移動N=1
再把問題裝回去移動N=2
再把問題裝回去移動N=3
完成問題

這種用遞迴把大問題拆成小問題的方式式遞迴的一種非常常用的方法


## 河內塔的遞迴關係
我們可以把這個遞迴關係寫成移動次數的關係式

$a_1 = 1$
$a_2 = a_1 + 1 + a_1 = 3$
$a_3 = a_2 + 1 + a_2 = 7$
.
.
$a_n = a_{n-1} + 1 + a_{n-1} = 2^n - 1$

小難題:
現有3個塔A B C
給定一任意長度的河內塔放在塔A
這個河內塔移到塔C
請輸出全部移動過程
:::spoiler 提示
```
void hanoi (int N, char start, char end, char temp){
    .
    .
    .
}
```
:::