学步园

问题

      初始时，给定3根柱子A，B，C，N个大小不一的圆盘，这些圆盘从小到大排列在其中的一根柱子上，假设为A，现在要通过B，将这N个圆盘全部移动到C柱子上，每次只能移动一个，移动的过程中不许出现大盘子放在小盘上面的情况，问完成这个任务至少需要将盘子移动多少次？

分析和程序

      设N个盘子至少需要T(N)次移动，显然T(0)=0，T(1)=1。考虑到要将N个盘子从A通过B的辅助移动到C，则必须将A上的N-1个先从A通过C的辅助移动到B，然后将A上的最大的盘子从A移动到C，最后将B上的N-1个盘子从B通过A的辅助移动到C。上面没有直接说从A移动到C，而是啰嗦说：从A通过B的辅助移动到C，是为了表明“将N个盘子从A通过B的辅助移动到C”与将“A上的N-1个先从A通过C的辅助移动到B”相对于移动次数来说，虽然移动方向变了，但本质是一样的，只不过是问题的规模变小了，N个盘子和N-1个盘子的问题，一个最小次数为T(n)，一个为T(n-1)。

       好了，继续分析，n个盘子移动时，通过T(n-1)次的从A到B，1次的从A到C，T(n-1)次的从B到C，一共是2T(n-1)+1次，完全可以把问题搞定。但要找的是将N个盘子从A移到C的最少次数，显然发现了一个数不能就说它是最小的次数了，应该贪婪点，继续找！在继续找的过程中，至少有了个前提，我们找的不能比2T(n-1)+1次大，这样我们就有第一个等式了，T(n)<=2T(n-1)+1。

       但贪婪归贪婪，能否找到呢？回过头来想，T(n-1)次的从A到B，1次的从A到C，T(n-1)次的从B到C，这2T(n-1)+1次移动都是我们必须做的，而且每步中已经不可能有更少次数的方法来代替了（我们已经假定T(n-1)次是完成N-1个盘子的任务的最少移动次数，这个次数是确定的），所以总的的次数不会小于这个次数，于是有了第二个等式，T(n)>=2T(n-1)+1。 

      结合起来，就有了 T(n)=2T(n-1)+1，T(0)=1^[1] ，用整体的思想来进行化简（左右两边各加1），我们不难推出总次数的显式解：T(n)=2^n-1，有了这些思想，就可以很容易的编程了：

/*gigglesun 2010/4/16<br /> **<br /> **The tower of hanoi problem:When given a tower of disks stacked in decreasing size<br /> **,how to transfer the entire tower to one of the other pegs,one at a time and never a<br /> **larger one onto a smaller one<br /> **/</p> <p>#include <iostream><br /> using namespace std;<br /> #define FROM 'A'<br /> #define MID 'B'<br /> #define TO 'C'<br /> int cnt = 0;</p> <p>void move(int diskNum,char f,char m,char t)<br /> {<br /> if(diskNum == 1)<br /> {<br /> cnt++;<br /> cout <<cnt<<"/t"<<f<<"/t->/t"<<t<<endl;<br /> }<br /> else<br /> {<br /> move(diskNum - 1,f,t,m);<br /> move(1,f,m,t);<br /> move(diskNum - 1,m,f,t);<br /> }<br /> }</p> <p>int main()<br /> {<br /> cout<<"Pegs are put as A/|/tB/|/tC/|"<<endl;<br /> cout<<"Input the number of disks on peg A/n";<br /> int diskNum;<br /> cin >> diskNum;</p> <p> cout<<"From A to C,we should move as follows:"<<endl;<br /> cout<<"times/tfrom/t/tto"<<endl;<br /> move(diskNum,FROM,MID,TO);</p> <p> return 0;</p> <p>}</p> <p>

输出结果：

Pegs are put as A|       B|      C|
Input the number of disks on peg A
4
From A to C,we should move as follows:
times   from            to
1       A       ->      B
2       A       ->      C
3       B       ->      C
4       A       ->      B
5       C       ->      A
6       C       ->      B
7       A       ->      B
8       A       ->      C
9       B       ->      C
10      B       ->      A
11      C       ->      A
12      B       ->      C
13      A       ->      B
14      A       ->      C
15      B       ->      C

将N=4代入数学公式也是15，多试几个数，也正确，说明我们的分析很正确，数学很强大！

       但不要高兴得太早，要是这时候你碰到一个苛刻的老板，说：A和C的距离太远，要是你一不小心将我的盘子打碎了怎么办？我不许你从A往C或是从C往A直接放盘子，所有的从A往C或是从C往A的盘子你都必须先往B上放下歇会再接着干，当然还是一次一个，小的必须在大的上面。于是你边干边想，N个盘子要搬多少次呢？ 

       还好你够聪明：N个盘子，由于每个盘子都必须经过B，必须将A的上面N - 1个从A移到到C（T(n-1)次），再将最下面的从A移动到B（1次），由于B上的这个是最大的，你接着必须将C上的刚移到的N-1个再移回到A（T(n-1)次），移的过程中依然可以在B上歇脚（这一点很重要），才能将B上的这个盘子移到C （1次），这样你终于移完了一个盘子到C，现在接下来，你只要再将A上的这N-1个盘子从A移到C（T(n-1)次）。一次减少一个，越搬越少，全部移完就大功告成了。

      同样，T(n)=T(n-1)+1+T(n-1)+1+T(n-1)=3T(n-1)+2，不难可以得出T(n)=3^n-1，算出来后你想，每个盘子“放”在A，B，C上的柱子上，一共才有3^n个可能状态，你搬了3^n-1次，加上初始的状态，你搬的过程中居然碰到了在A，B，C上的所有小盘在上，大盘在下的盘子的可能情况，oh,my god...

     再拿计算机来检验下你的结果：

/*by gigglesun 2010/4/16<br /> **<br /> **The tower of hanoi problem:When given a tower of disks stacked in decreasing size on<br /> **A,how to transfer the entire tower to one of the other peg C through B,one at a time ,<br /> **and never a larger one onto a smaller one,besides, direct moves from A to C or C to A are disallowed.<br /> **/</p> <p>#include <iostream><br /> using namespace std;<br /> #define FROM 'A'<br /> #define MID 'B'<br /> #define TO 'C'<br /> int cnt = 0;</p> <p>void move(int diskNum,char f,char m,char t)<br /> {<br /> if(diskNum == 1 && ((f == FROM)&&(t == TO) || (f == TO)&&(t == FROM)))<br /> {<br /> cnt++;<br /> cout <<cnt<<"/t"<<f<<"/t->/t"<<m<<endl;<br /> cnt++;<br /> cout <<cnt<<"/t"<<m<<"/t->/t"<<t<<endl;<br /> }<br /> else if (diskNum == 1)<br /> {<br /> cnt++;<br /> cout <<cnt<<"/t"<<f<<"/t->/t"<<t<<endl;<br /> }<br /> else<br /> {<br /> move(diskNum - 1,f,m,t);//从A将n - 1个从A到C<br /> move(1,f,t,m);//将A最下面的从A移到B<br /> move(diskNum - 1,t,m,f);//将C上n - 1个从C到A<br /> move(1,m,f,t);//将B最下面的从B移到C<br /> move(diskNum - 1,f,m,t);//再将A上这n - 1个从A到C<br /> }<br /> }</p> <p>int main()<br /> {<br /> cout<<"Input disks numbers in A:"<<endl;<br /> cout<<"Pegs are put as A/|/tB/|/tC/|"<<endl;<br /> cout<<"Input the number of disks on peg A/n";<br /> int diskNum;<br /> cin >> diskNum;</p> <p> cout<<"From A to C,we should move as follows:"<<endl;<br /> cout<<"times/tfrom/t/tto"<<endl;<br /> move(diskNum,FROM,MID,TO);</p> <p> return 0;</p> <p>}</p> <p>

运行结果：

Input disks numbers in A:
Pegs are put as A|       B|      C|
Input the number of disks on peg A
3
From A to C,we should move as follows:
times   from            to
1       A       ->      B
2       B       ->      C
3       A       ->      B
4       C       ->      B
5       B       ->      A
6       B       ->      C
7       A       ->      B
8       B       ->      C
9       A       ->      B
10      C       ->      B
11      B       ->      A
12      C       ->      B
13      A       ->      B
14      B       ->      C
15      B       ->      A
16      C       ->      B
17      B       ->      A
18      B       ->      C
19      A       ->      B
20      B       ->      C
21      A       ->      B
22      C       ->      B
23      B       ->      A
24      B       ->      C
25      A       ->      B
26      B       ->      C

   拿计算机检验后，发现老板的方法确实不是个好办法。你向老板抱怨你的辛苦，因为6个盘子的任务就至少要搬728次了，老板也体谅到了你的辛苦，但老板对盘子的安全问题依然很在乎。你向老板建议：将三柱改为四柱，多放了一根柱子歇脚，间距相等。这样，柱子和柱子间的距离更短了，老板觉得多了一根柱子，距离变短了，要求也没变化，感到很放心，答应了你的请求，并且怀疑你是否真能减少工作量。你是个聪明的数学家，早就算好多放一根柱子后需要的最少的搬运次数，你是这样想的：

1. 首先：把A柱上部分的n - r个盘子通过C柱和D柱移到B柱上,需要F(n - r) 步;
2. 接着：用三柱方法把A柱剩余的r个盘子通过C柱移到D柱上,需要T(r) = 2^r - 1步;
3. 最后：再用四柱方法把B柱的n-r个盘子通过A柱和C柱移到D柱上,需要F(n - r)步;

  据此,计算出总步数为f(n,r),随后对所有的r(1≤r≤n)逐一进行心算比较。选择一个r使得f(n,r)取最小值，你得到：

 F(n)=minf(n,r)= min[2F(n - r) + T(r)]= min[2F(n - r) + 2^r - 1]^[2]

还好，你一下就知道一个盘子时需要1次（虽然这种搬法是前一个规则不允许的，但老板同意了），二个盘子时为3次，根据这，你发现现在搬六个盘子只需要17次就搞定了，甚至比最初的三柱的2^6-1=63还少，大大减少了你的工作量，你不禁为你的聪明自喜，至于过程，你也很快就想到了：

/*by gigglesun 2010/4/20<br /> **<br /> **The tower of hanoi problem:When given a tower of disks stacked in decreasing size on<br /> **A,how to transfer the entire tower to one of the other peg D through B,C,one at a time ,<br /> **and never a larger one onto a smaller one,4 Pegs this time.<br /> **/</p> <p>#include <iostream><br /> #include <cmath><br /> using namespace std;<br /> #define FROM 'A'<br /> #define MID1 'B'<br /> #define MID2 'C'<br /> #define TO 'D'<br /> int cnt = 0;</p> <p>//find_k的实现参考了文献[2]<br /> int find_k(int diskNum)<br /> {<br /> int k =( (sqrt(8*diskNum + 1) - 1) / 2);<br /> return k;<br /> }<br /> void ThreePegHanoi(int disNum,char from,char mid ,char to)<br /> {<br /> if(disNum == 1)<br /> {<br /> cnt++;<br /> cout <<cnt<<"/t"<<from<<"/t->/t"<<to<<endl;<br /> }<br /> else<br /> {<br /> ThreePegHanoi(disNum - 1,from,to,mid);<br /> ThreePegHanoi(1,from,mid,to);<br /> ThreePegHanoi(disNum - 1,mid,from,to);<br /> }</p> <p>}</p> <p>void FourPegHanoi(int diskNum,char from,char mid1,char mid2,char to)<br /> {<br /> int k = find_k(diskNum);<br /> if(diskNum == 1)<br /> {<br /> cnt++;<br /> cout <<cnt<<"/t"<<from<<"/t->/t"<<to<<endl;<br /> }<br /> else<br /> {<br /> FourPegHanoi(diskNum - k,from,mid2,to,mid1);//从A将上面disNum -k个碟子通过C柱和D柱移到B柱上<br /> ThreePegHanoi(k,from,mid2,to);//将A最下面的k个从A通过C移到D<br /> FourPegHanoi(diskNum - k,mid1,from,mid2,to);//把B柱上的k个碟子通过A柱和C柱移到D柱<br /> }<br /> }</p> <p>int main()<br /> {<br /> cout<<"Input disks numbers in A:"<<endl;<br /> cout<<"Pegs are put as A/|/tB/|/tC/|/tD/|"<<endl;<br /> cout<<"Input the number of disks on peg A/n";<br /> int diskNum;<br /> cin >> diskNum;</p> <p> cout<<"From A to D,we should move as follows:"<<endl;<br /> cout<<"times/tfrom/t/tto"<<endl;<br /> FourPegHanoi(diskNum,FROM,MID1,MID2,TO);</p> <p> return 0;</p> <p>}<br /> /*输出结果<br /> **<br /> Input disks numbers in A:<br /> Peg are put as A| B| C| D|<br /> Input the number of disks on peg A<br /> 6<br /> From A to D,we should move as follows:<br /> times from to<br /> 1 A -> C<br /> 2 A -> D<br /> 3 A -> B<br /> 4 D -> B<br /> 5 C -> B<br /> 6 A -> D<br /> 7 A -> C<br /> 8 D -> C<br /> 9 A -> D<br /> 10 C -> A<br /> 11 C -> D<br /> 12 A -> D<br /> 13 B -> A<br /> 14 B -> C<br /> 15 B -> D<br /> 16 C -> D<br /> 17 A -> D</p> <p>**<br /> */

   至此，搬盘子的任务终于被你的聪明才智化解了。

     补充：曾在wiki上搜索hanoi,看到过一个Binary solutions，发现想法很巧妙漂亮，但仔细研究后感觉其给的例子有问题，找相关原始材料也很难找；我试着第一次按我的想法编辑了下这个小条目，居然能够保存，现在大家看到的那个Binary solutions的实例部分是我编辑后的结果，哈哈，提醒大家小心（wiki上像我这样的小民说不定还很多）。如果有谁实现过这个算法或有相关的资料，希望能和我交流分享下，我的邮箱gigglesun AT 163.com。

参考文献：

[1]concrete mathematics page1-4 second edition by Graham knuth patashnik

[2]四柱汉诺塔之初步探究 北京大学学报(自然科学版) ,第40卷,第1期,杨　楷　徐　川