主題
題目連結：
題目大意：
典型河內塔（Hanoi Tower）。
輸入給定兩個正整數 N （1 ≦ N ≦ 60，1 ≦ i < 2 ^ N），代表 1 號塔有 N 個盤子，求最佳走法下（最少步數）的第 i 步是哪個盤子 A 從哪個塔 B 搬到另一個塔 C 。
輸出所求步驟之格式為「move A from B to C」。
範例輸入：
範例輸入一：
3 3
範例輸入二：
20 524288
範例輸出：
範例輸出一：
move 1 from 3 to 2
範例輸出二：
move 20 from 1 to 3
解題思維：
典型的遞迴型之河內塔寫法如下：
void Hanoi (int disks, char start, char temporary, char end)
{
if (disks) {
Hanoi(disks - 1, start, end, temporary);
cout << "Move disk " << disks << " from " << start << " to " << end << '\n';
Hanoi(disks - 1, temporary, start, end);
}
}
中間三個步驟之意義依序為：
遞迴將上面 disks - 1 個盤子從 start 移到 temporary；
將第 disks 個盤子從 start 移到 end；
遞迴將剛剛移走的 disks - 1 個盤子從 temporary 移回到 end。
因此可以看到 n 個盤子河內塔的最佳步數為 2 ^ n - 1 。
而對於盤子 n ，第一次遞迴呼叫 Hanoi() 後，會執行 2 ^ (n - 1) - 1 步；然後中間移動了一步；其後又遞迴呼叫一次 Hanoi() ，執行 2 ^ (n - 1) - 1 步。
因此用一個變數 nowStep，初始化之值為 0 。
當 nowStep + (2 ^ (n - 1) - 1) + 1 （代表做了第一次遞迴呼叫以及移動第 n 個盤子之步驟）小於目標步數 i 時，代表該步一定是在第二次呼叫 Hanoi() 時執行的。因此將 nowStep 加上 2 ^ (n - 1) ，然後遞迴第二部分的 Hanoi()。
如果 nowStep + (2 ^ (n - 1) - 1) + 1 等於 i，代表移動第 n 個盤子恰好是第 i 步，所以根據目前 start 、 end 和輸出格式輸出。
如果以上皆非，則代表第 i 步是在第一次遞迴呼叫時執行的，因此去遞迴第一次的 Hanoi()。
而以上作法不一定要用遞迴實現，因此每次都只會去找一個區塊（第一次遞迴、移動第 n 個盤子或是第二次遞迴），所以也可以寫成寫成迭代式的。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
