---
# System prepended metadata

title: 'a117: 03-3-三色河內塔'
tags: [APCS]

---

---
tags: APCS
langs: zh-hant
type: slide
slideOptions:
  theme: white
  transition: slide
  # center: false
  parallaxBackgroundImage: 'https://s3.amazonaws.com/hakim-static/reveal-js/reveal-parallax-1.jpg'
---

<style>

img[alt ~= "bdr"] { border: 1px solid lightgrey; padding: 5pt}
img[alt ~= "mh"] {max-height: 64%}
div.flex {display: flex; justify-content: space-between;}
div.flex.block {
    justify-content: center;
    align-items: center;
    color: #29292b;
    text-shadow: 0 0 3px #eee;
    background-color: rgba(255, 255, 0, 0.2);
}
.flex>p {margin: 0}
.flex img:only-child {margin: 0}
.flex.nmw img {max-width: none; max-height: none}
div.big {font-size: 100pt}
.center {text-align: center}
.reveal section img {border: 1px solid #eee; background-color: transparent}
.relative {position: relative}
.absolute {position: absolute}
.border {border: 3px solid red}
.box {border: 3px solid red; position: absolute}
table.celled td {border: 1px solid lightgrey;}
table.celled tbody tr:last-child td  {border-bottom: 1px solid lightgrey;}

.reveal .slides {
    text-align: justify;
}

table#posinfo td {
  width: 170px;
  height: 170px;
  position: relative;
  text-align: center;
}

table#posinfo td span {
  position: absolute;
  left: 3pt;
  top: 3pt;
  font-size: 12pt;
}
</style>

# a117: 03-3-三色河內塔

---

下圖為河內塔問題(Towers of Hanoi)的一種，共有A、B、C三個柱子，一開始A柱子可以放個數為3倍數的套環，都是花白灰相間的三種不同顏色套環，每種大小的套環都有三個，花色在上，白色在中，灰色在下。套環依序由上到下的編號分別為1~N，假設每次的移動都只能從柱子的頂端移動一個套環，搬到其他柱子放，而且編號較大的套環永遠都不能放在較小套環的上方。最後要將所有花套環移動到A，白套環移動到B，以及所有灰套環移動到C。請寫出一個程式，輸入套環總數(為 3的倍數，包含花白灰三種套環)，計算並輸出所有套環的最佳移動順序(移動次數最少)及其移動次數。

----

![](https://i.imgur.com/RdL9E71.png)

---

## 原始版本

<div class="flex">

![](https://i.imgur.com/o9dCdQa.png)

![](https://i.imgur.com/CcV8el1.png)

</div>

將 n 個盤子由 A 移動到 C

----

``` cpp
//
// n: 移動盤子數
// from: 來源柱
// to: 目的柱
// by: 輔助柱
//
void move(int n, char from, char to, char by)
{
}
```

----

終止條件：
移動的盤子數量 <= 0

----

``` cpp
int cnt = 0;
//
// n: 移動盤子數
// from: 來源柱
// to: 目的柱
// by: 輔助柱
//
void move(int n, char from, char to, char by)
{
    if (n <= 0)
        return;
}
```



----

<div class="flex">

![](https://i.imgur.com/xMKuCcX.png)

![](https://i.imgur.com/5TWo4Yt.png)<!-- .element: class="fragment" -->

</div>

1. 從 A 搬 n-1 個盤子到 B

----

<div class="flex">

![](https://i.imgur.com/5TWo4Yt.png)

![](https://i.imgur.com/2ECoKNn.png)<!-- .element: class="fragment" -->

</div>

2. 從 A 搬最下面的 n 號盤子到 C

----

<div class="flex">

![](https://i.imgur.com/2ECoKNn.png)

![](https://i.imgur.com/h8jUVhV.png)<!-- .element: class="fragment" -->

</div>

3. 從 B 搬 n-1 個盤子到 C

----

![](https://i.imgur.com/h8jUVhV.png)

----

``` cpp
//
// n: 移動盤子數
// from: 來源柱
// to: 目的柱
// by: 輔助柱
//
void move(int n, char from, char to, char by)
{
    if (n <= 0)
        return;
    move(n-1, from, by, to);
    cout << "ring " << n << " : " << from << " => " << to << '\n';
    cnt++;
    move(n-1, by, to, from);
}
```

---

題目想做的事情，不是將全部的盤子挪到另一根柱子上，而是將盤子依序分配到 3 根柱子

----

<div class="flex">

![](https://i.imgur.com/xMKuCcX.png)

![](https://i.imgur.com/LjZczdK.png)

</div>

----

``` cpp
// n: 要分配的盤子個數
// from: 來源柱，第 3 大的盤子要給誰
// to: 目的柱，最大的盤子要給誰
// by: 輔助柱，次大的盤子要給誰
void distribute(int n, char from, char to, char by)
{
    if (n <= 0)
        return;
}
```

----

<div class="flex">

![](https://i.imgur.com/xMKuCcX.png)

![](https://i.imgur.com/Y1YePq0.png)<!-- .element: class="fragment" -->

</div>

1. 先把 A 柱上方的 n-1 個盤子挪到 B 柱

``` cpp
move(n-1, from, by, to);
```

----

<div class="flex">

![](https://i.imgur.com/Y1YePq0.png)

![](https://i.imgur.com/5g51fRk.png)<!-- .element: class="fragment" -->

</div>

2. 將 n 號盤從 A 柱挪到 C 柱

``` cpp
cout << "ring " << n << " : " << from << " => " << to << '\n';
```

----

<div class="flex">

![](https://i.imgur.com/5g51fRk.png)

![](https://i.imgur.com/XGpgVap.png)<!-- .element: class="fragment" -->

</div>

3. 把 B 柱上方的 n-3 個盤子挪到 C 柱

``` cpp
move(n-3, by, to, from);
```

----

<div class="flex">

![](https://i.imgur.com/XGpgVap.png)

![](https://i.imgur.com/d7RT88f.png)<!-- .element: class="fragment" -->

</div>

4. 把 n-2 號盤挪到 A 柱

``` cpp
cout << "ring " << n-2 << " : " << by << " => " << from << '\n';
```

----

<div class="flex">

![](https://i.imgur.com/d7RT88f.png)

![](https://i.imgur.com/Ake8UzK.png)<!-- .element: class="fragment" -->

</div>

5. 把 C 柱上方的 n-5 個盤子挪到 A 柱

``` cpp
move(n-5, to, from, by);
```

----

<div class="flex">

![](https://i.imgur.com/Ake8UzK.png)

![](https://i.imgur.com/JDRB8oX.png)<!-- .element: class="fragment" -->

</div>

6. 把 n-4 號盤挪到 B 柱

``` cpp
cout << "ring " << n-4 << " : " << to << " => " << by << '\n';
```

----

``` cpp
void distribute(int n, char from, char to, char by)
{
    if (n <= 0)
        return;
    move(n-1, from, by, to);
    cout << "ring " << n << " : " << from << " => " << to << '\n';
    cnt++;
    move(n-3, by, to, from);
    cout << "ring " << n-2 << " : " << by << " => " << from << '\n';
    cnt++;
    move(n-5, to, from, by);
    cout << "ring " << n-4 << " : " << to << " => " << by << '\n';
    cnt++;
    distribute(n-6, from, to, by);
}
```

----

咦？這樣好像只能處理 6 個倍數？

再重新觀察一遍

----

<div class="flex">

![](https://i.imgur.com/d68oTl7.png)

![](https://i.imgur.com/5g51fRk.png)<!-- .element: class="fragment" -->

</div>

----

<div class="flex">

![](https://i.imgur.com/2yWNOED.png)

![](https://i.imgur.com/d7RT88f.png)<!-- .element: class="fragment" -->

</div>

----

<div class="flex">

![](https://i.imgur.com/ZMHEaic.png)

![](https://i.imgur.com/hdm5zIE.png)<!-- .element: class="fragment" -->

</div>

----

``` cpp
void distribute(int n, char from, char to, char by)
{
    if (n <= 0)
        return;
    move(n-1, from, by, to);
    cout << "ring " << n << " : " << from << " => " << to << '\n';
    cnt++;
    distribute(n-2, by, from, to);
}
```