汉诺塔非递归算法

汉诺塔非递归算法.我只是将盘子的数量等于2，3的情况代到网上别人给的算法中验证了一下，没有错。并没有证明算法的正确性。算法是否有效，有待大家证明。 zqekkR]  
=9;[C:p0-  
include <iostream> |n|U;|'^  
#include <stdlib.h> -!'Oy%a#  
V_+}^  
#ifdef _WIN32 F.~n  
using namespace std; )){PBT}t]  
#endif &jXca|wAR  
629~Uc6]  
static void hanoi(int height) 9atjK4+o  
{ xecieC  
  int fromPole, toPole, Disk; jy\W_CT  
  int *BitStr = new int[height],   //用来计算移动的盘的号码 p|FlWR'mA  
    *Hold   = new int[height];   //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 Eu`2w%qz  
  char Place[] = {'A', 'C', 'B'}; 2y9:'c|  
  int i, j, temp; T@K7DkP@  
w|!YoMk+o  
  for (i=0; i < height; i++)               nV!2Dfd  
  { Xk{!' 0  
    BitStr = 0; Z-^uM`],G  
    Hold = 1; ]+}ZfHp  
  } ,h%D4EVx  
  temp = 3 - (height % 2);               //第一个盘的柱号 pr62:  
  int TotalMoves = (1 << height) - 1; (*Gi~?-  
  for (i=1; i <= TotalMoves; i++) RL7C YB  
  { =F'l's^j  
    for (j=0 ; BitStr[j] != 0; j++)         //计算要移动的盘 fnLR  
    { + >T7Q`64  
        BitStr[j] = 0; vh9kwJyT  
    } H$NP1^5!  
    BitStr[j] = 1; Gt^|+[gD  
    Disk = j+1; Wphe%Of  
    if (Disk == 1) ewb*?In  
    { ntrY =Y  
        fromPole = Hold[0]; 8Zcol$XS'  
        toPole = 6 - fromPole - temp; //1+2+3等于6，所以6减去其它两个，剩下那个就是要移去的柱子 n~1tm  
        temp = fromPole;     //保存上一次从哪个柱子移动过来的 b34zhZ  
    } }G>v]bV0V  
    else Ez06:]Jd  
    { c[(yU#@  
        fromPole = Hold[Disk-1]; A5CdLwk  
        toPole = 6 - Hold[0] - Hold[Disk-1]; i&A{L}eCr:  
    }     .+{nA}Bc  
    cout << "Move disk " << Disk << " from " << Place[fromPole-1] EpRXjz  
        << " to " << Place[toPole-1] << endl; /~H[= Pf  
    Hold[Disk-1] = toPole; /[\6oa  
  } <u6
c2!I{  
} MZCL:#  
.@y{
)/  
bWGyLo,  
o\_ Td  
@rPI$ia1~  
int main(int argc, char *argv[]) T6sr/<#<(  
{ kVV\*"9y  
  cout << "Towers of Hanoi: " << endl fC=fJZU7$  
      << "moving a tower of n disks from pole A to pole B by using pole C" << endl; <T(s\N5B=  
  cout << "Input the height of the original tower: "; =}~NRmmF  
  int height; I["F+kt^^  
  cin >> height; e(?:g@]-r  
  hanoi(height); 6?53q e  
GLo\q:5A  
  system("PAUSE"); 0L!er%GM  
  return EXIT_SUCCESS; 4fu'QZ(}  
}  5Waw?1GL  
Wr]O  
fm3(70F\  
8# 6\+R  
问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上 ^36M0h|R  
VYL@RL'  
到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一 6P0y-%[Gk  
cDfx)sL  
次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。 LiiK3!^i  
<\>+~p,  
算法要点有二： @)9REA(
U  
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次，设m为n位的二进制数，则m的取值范 Jb(
DJ-&  
oR-O~_)U  
围为0～2^n -1。让m每次递增1，可以发现，m中最低一位的刚刚由0变为1的位置的位置编号，和即将要移 * eA{[  
Gh2#-~|cB  
动的盘子编号有确定关系。 t[%x}0FP-F  
^Ku\l #B  
2、这个盘子往哪个柱子上移。 ~RcNZ\2y  
a.第一次需要移动1号盘，n为奇数时，1号盘首先移动到柱子B，为偶数时首先移动到柱子C。 VT'0DQ!NIq  
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子，因为移动的盘子 x}v1
X`6b  
&J\B\`  
不能叠放到1号盘上，所以该盘可以移动的位置就是没有1号盘的那个柱子。 \eEds:Hg  
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的，因为移动的 WLE%d]'%M  
5i^`vmK  
顺序（顺时针或逆时针）一旦确定，就不会更改，所以排除from的那个柱子后，移动方向也就唯一了。