<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的倍數，包含花白灰三種套環)，計算並輸出所有套環的最佳移動順序(移動次數最少)及其移動次數。 ----  --- ## 原始版本 <div class="flex">   </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">  <!-- .element: class="fragment" --> </div> 1. 從 A 搬 n-1 個盤子到 B ---- <div class="flex">  <!-- .element: class="fragment" --> </div> 2. 從 A 搬最下面的 n 號盤子到 C ---- <div class="flex">  <!-- .element: class="fragment" --> </div> 3. 從 B 搬 n-1 個盤子到 C ----  ---- ``` 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">   </div> ---- ``` cpp // n: 要分配的盤子個數 // from: 來源柱，第 3 大的盤子要給誰 // to: 目的柱，最大的盤子要給誰 // by: 輔助柱，次大的盤子要給誰 void distribute(int n, char from, char to, char by) { if (n <= 0) return; } ``` ---- <div class="flex">  <!-- .element: class="fragment" --> </div> 1. 先把 A 柱上方的 n-1 個盤子挪到 B 柱 ``` cpp move(n-1, from, by, to); ``` ---- <div class="flex">  <!-- .element: class="fragment" --> </div> 2. 將 n 號盤從 A 柱挪到 C 柱 ``` cpp cout << "ring " << n << " : " << from << " => " << to << '\n'; ``` ---- <div class="flex">  <!-- .element: class="fragment" --> </div> 3. 把 B 柱上方的 n-3 個盤子挪到 C 柱 ``` cpp move(n-3, by, to, from); ``` ---- <div class="flex">  <!-- .element: class="fragment" --> </div> 4. 把 n-2 號盤挪到 A 柱 ``` cpp cout << "ring " << n-2 << " : " << by << " => " << from << '\n'; ``` ---- <div class="flex">  <!-- .element: class="fragment" --> </div> 5. 把 C 柱上方的 n-5 個盤子挪到 A 柱 ``` cpp move(n-5, to, from, by); ``` ---- <div class="flex">  <!-- .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">  <!-- .element: class="fragment" --> </div> ---- <div class="flex">  <!-- .element: class="fragment" --> </div> ---- <div class="flex">  <!-- .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); } ```