汉诺塔非递归算法

汉诺塔非递归算法.我只是将盘子的数量等于2，3的情况代到网上别人给的算法中验证了一下，没有错。并没有证明算法的正确性。算法是否有效，有待大家证明。 8i"CU:(  
puMVvo  
include <iostream> G--vwvL  
#include <stdlib.h> e[x,@P`  
%GjG.11V,_  
#ifdef _WIN32 [5xm>Y&}  
using namespace std; Lb$Uba-_  
#endif |6-9vU!LK?  
60~*$`  
static void hanoi(int height) /TbJCZ  
{ MDa[bQNM  
  int fromPole, toPole, Disk; ZOqA8#\  
  int *BitStr = new int[height],   //用来计算移动的盘的号码 CxaI@+  
    *Hold   = new int[height];   //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 7Z
]?a  
  char Place[] = {'A', 'C', 'B'}; =z5=?  
  int i, j, temp; qX5]\nX&G  
P
q~#SxA~  
  for (i=0; i < height; i++)               IJ.H/l}h  
  { WuVs
W3@  
    BitStr = 0; iU.` TqR7  
    Hold = 1; u@D5SkT  
  } X ([^i;mr  
  temp = 3 - (height % 2);               //第一个盘的柱号 \t{4pobo  
  int TotalMoves = (1 << height) - 1; A["6dbvv  
  for (i=1; i <= TotalMoves; i++) GAH<  
  { uu4!e{K  
    for (j=0 ; BitStr[j] != 0; j++)         //计算要移动的盘 FBP #_"z  
    { @I Y<i5(  
        BitStr[j] = 0; Flpl,|n a  
    } 2FL_!;p;2E  
    BitStr[j] = 1; 1;./e&%%  
    Disk = j+1; zk70D_}L  
    if (Disk == 1) vyc<RjS_x  
    { d<?Zaehe\  
        fromPole = Hold[0]; ++w{)Io Z  
        toPole = 6 - fromPole - temp; //1+2+3等于6，所以6减去其它两个，剩下那个就是要移去的柱子 ~+ae68{p  
        temp = fromPole;     //保存上一次从哪个柱子移动过来的 U'b}%[  
    } \zVp8MMf  
    else eiOAbO#U  
    { z1RHdu0;z  
        fromPole = Hold[Disk-1]; )e[q%%ks  
        toPole = 6 - Hold[0] - Hold[Disk-1]; Wsd_RT}ww  
    }     X%!?\3S  
    cout << "Move disk " << Disk << " from " << Place[fromPole-1] ?>=vKU5  
        << " to " << Place[toPole-1] << endl; OvdBUcp[  
    Hold[Disk-1] = toPole; +:#g6(P]  
  } BB,-HhYT0  
} ,EH-Sf2Cb  
tF*Sg{:bCa  
#@Tm5z  
Lo'G
fHE  
+7"UF) ~k  
int main(int argc, char *argv[]) kVWrZ>McK  
{ '
#K~hep  
  cout << "Towers of Hanoi: " << endl ZnbpIJ8cV  
      << "moving a tower of n disks from pole A to pole B by using pole C" << endl; JKYtBXOl  
  cout << "Input the height of the original tower: "; M9Z9s11{H  
  int height; pOy(XUV9O  
  cin >> height; |<]wM(GxE  
  hanoi(height); |a1zJ_t4  
UGOe(JB  
  system("PAUSE"); 4`CO>Q  
  return EXIT_SUCCESS; (s1iYK  
} F":dS-u&L  
GYT0zMMf  
y#ON=8l  
;rh=63g  
问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上 i+-=I+L3  
qk&BCkPT  
到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一 "H=fWz5z  
VF-[O  
次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。 u8~5e  
3wgZDF38  
算法要点有二： T2T?)_f /  
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次，设m为n位的二进制数，则m的取值范 W.7u6F`  
='/#G0W  
围为0～2^n -1。让m每次递增1，可以发现，m中最低一位的刚刚由0变为1的位置的位置编号，和即将要移 }q/[\3  
5',b~Pp  
动的盘子编号有确定关系。 jN+2+P%OL  
up3mum  
2、这个盘子往哪个柱子上移。 \bSakh71  
a.第一次需要移动1号盘，n为奇数时，1号盘首先移动到柱子B，为偶数时首先移动到柱子C。 H/#WpRg  
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子，因为移动的盘子 fK4O N'[R:  
Xp|$z~  
不能叠放到1号盘上，所以该盘可以移动的位置就是没有1号盘的那个柱子。 DqH]FS?]  
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的，因为移动的 z_&T>ME  
C5^N)-]"  
顺序（顺时针或逆时针）一旦确定，就不会更改，所以排除from的那个柱子后，移动方向也就唯一了。