问一： OpenJ_Bailian - 4147
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
题目链接： http://bailian.openjudge.cn/practice/4147?lang=en_US
汉诺塔问题其实是函数递归的经典题目，但假如只是求最少移动次数的话，它还可以用递推来做。
先谈一下我对递归下汉诺塔解法的理解。
可以先设想一下移动最下面一块木块的时候，它最终必须移动到c柱子，而放在它上面的那些木块肯定都已经被移走，要不然就在b柱子，要不然就在c柱子，而最后一块木块必然是最大的一块，所以假如它能移动，一定是移动到空柱子上，因此放在它上面的所有木块只有从大到小规规矩矩的叠放在b柱子上，那木块才可以移动。那个时候的情况一定是这样：
a柱子：空 ，b柱子：1~n-1 块木块 c柱子： 第n块木块
这个时候因为在场的所有木块都没有比c柱子上的木块大，所以我们在移动的时候完全可以忽略c柱子上的木块，也将c柱子当成是空的柱子，这个时候的情况就是
a柱子： 空 b柱子： 1~n-1 块木块 c柱子：空
看到没有，假如这个时候我们将b柱子当成a柱子，这就是崭新的n-1块汉诺塔的子问题了（滑稽），我们就可以重复调用这个函数啦。
然而一开始的时候我们是需要将0~n-1块汉诺塔移动到b柱子上的，这个时候我们依然可以忽略掉最大那个木块，原因同理，因此开始的时候也可以转化为n-1块汉诺塔从a柱子移动到b柱子的子问题。
我们在定义函数的时候，需要4个变量，n，a，b，c ，注意这里的a，b，c并不是第几号柱子，a表示的是汉诺塔最初堆放在哪里，c表示的就是最终汉诺塔需要放在哪里
上代码：
#include<bits/stdc++.h> using namespace std; void hanoi(int n,char a,char b,char c) { // a: from c:reach if (n == 1) { printf("1:%c->%c\n", a, c); return; } hanoi(n - 1, a, c, b); printf("%d:%c->%c\n", n, a, c); hanoi(n - 1, b, a, c); } int main() { char a, b, c; int n; cin >> n; cin >> a >> b >> c; hanoi(n, a, b, c); return 0; }三根柱子的递推写法：
通过观察上方的递归调用方程，我们发现对于从a移动到c的n块汉诺塔，它总是等于n-1 块汉诺塔从a移动到b加上第n块汉诺塔从a移动到c再加上n-1块汉诺塔从b移动到c，因此方程就很直接了。
假如我们用thr_[i]数组表示i块汉诺塔从a移动到c需要的最小次数，那么就有 ：
thr_[i] = thr_[i - 1] * 2 + 1
是不是很简单（滑稽）
问二：POJ - 1958
题目链接：http://poj.org/problem?id=1958
题意：
四个塔，要求全部用上，把A上的塔转移到D上 12行依次输出12个数，第i行表示有i个塔在A上需要转移到D的最小次数四根柱子的汉诺塔问题，其实一开始我也跟三根柱子的汉诺塔一样思考。
假如给a，b，c，d四根柱子
我一开始是这么想的（wrong answer想法）：看移动最后一块木块，肯定是从a移动到d，然后倒数第二个木块，就从a移动到c，然后其他堆叠到b柱子上，因此情况应该是 柱子a： 0木块 柱子b： 0~n-2木块， 柱子c： 第n-1块木块 柱子d：第n块木块，然后柱子c移动到柱子d，就转化成了一个全新的n-2块汉诺塔的子问题。
我写的主要代码：（wrong answer）
void hanoi(int n,char a,char b,char c,char d) { // 主体 堆叠 次大 最大 if (n == 1) { //printf("%c move to %c\n", a, d); sum++; return; } else if (n == 0) return; hanoi(n - 2, a,c,d,b); //printf("%c move to %c\n", a, c); //printf("%c move to %c\n", a, d); //printf("%c move to %c\n", c, d); sum += 3; hanoi(n - 2, b, a, c, d); }主要的一个原因是，只要有三根柱子，木块就可以转移。
因此最后一个木块是移动到d没错，但是第1~n-2 块木块不一定是全部堆叠到b柱这里，有可能是1~n-1任意一个数量堆积到这里，因此我们需要将所有可能都列举一遍
以four_[i]表示i块四根柱子的汉诺塔从a移动到c的最短操作步数， thr_[i]表示i块3根柱子的汉诺塔从a移动到c的最短操作步数
four_[i] = min( four[j] + thr[i-j] ) 其中j=(1~i) ，有1~n-1任意一个数量的汉诺塔堆积到b，那么剩下的汉诺塔就坍塌成3根柱子的汉诺塔使之堆积到c
代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 20; const int INF = 0x3f3f3f3f; int thr_[maxn], four_[maxn]; int main() { thr_[1] = 1; memset(four_, INF, sizeof(four_)); four_[1] = 1; printf("1\n"); for (int i = 2; i < maxn; i++) thr_[i] = thr_[i - 1] * 2 + 1; for (int i = 2; i <= 12; i++) { for (int j = 1; j < i; j++) { four_[i] = min( 2 * four_[j] + thr_[i - j],four_[i]); } printf("%d\n", four_[i]); } return 0; }
