汉诺塔非递归算法

汉诺塔非递归算法.我只是将盘子的数量等于2，3的情况代到网上别人给的算法中验证了一下，没有错。并没有证明算法的正确性。算法是否有效，有待大家证明。 g<5Pc,  
#AnSjl  
include <iostream> +s 0
Bt '  
#include <stdlib.h> 
u5|e9(J  

^i k|l=  
#ifdef _WIN32 ~(E8~)f)  
using namespace std; f9bz:_;W_  
#endif S#z8H+'  
2gI_*fG1  
static void hanoi(int height) C+IE<=%F  
{ cr;`
0  
  int fromPole, toPole, Disk; :iC\#i]6  
  int *BitStr = new int[height],   //用来计算移动的盘的号码 VNot4 62L  
    *Hold   = new int[height];   //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 1:Gd{z  
  char Place[] = {'A', 'C', 'B'}; 5"]2@@b4  
  int i, j, temp; +>%+r  
)Ea_:
C'  
  for (i=0; i < height; i++)               Xr;noV-X  
  { W3j|%  
    BitStr = 0; l[0P*(I,  
    Hold = 1; 6spk*
 8e  
  } h\ek2K  
  temp = 3 - (height % 2);               //第一个盘的柱号 ,H1~_|)<  
  int TotalMoves = (1 << height) - 1; dNt|"9~&  
  for (i=1; i <= TotalMoves; i++) S.4YC>E  
  { oeKc-[r  
    for (j=0 ; BitStr[j] != 0; j++)         //计算要移动的盘 D6:J*F&?  
    { 2^lT!X@  
        BitStr[j] = 0; ?
pY!sG  
    } &;3z 1s/  
    BitStr[j] = 1; U2?gODh'  
    Disk = j+1; VO6y9X"  
    if (Disk == 1) /pN2
Jst  
    { Wm&f+{LO+K  
        fromPole = Hold[0]; +# >%bq x  
        toPole = 6 - fromPole - temp; //1+2+3等于6，所以6减去其它两个，剩下那个就是要移去的柱子 AWNd(B2o  
        temp = fromPole;     //保存上一次从哪个柱子移动过来的 G{Q'N04
RA  
    } <LZvh8  
    else mR@X
t#  
    { n?tAa|_  
        fromPole = Hold[Disk-1]; Y%9F  
        toPole = 6 - Hold[0] - Hold[Disk-1]; rq?x]`u   
    }      n(1"6  
    cout << "Move disk " << Disk << " from " << Place[fromPole-1] &4
FdA|9T  
        << " to " << Place[toPole-1] << endl; &3?yg61Ag  
    Hold[Disk-1] = toPole; rl7Y
=*Dv  
  } ]vFmY  
} }w8AnaC  
aH"c0A  
?d)|vX3Uf  
EKD>c$T^  
?8m/]P/~  
int main(int argc, char *argv[]) 6p{x2>2y[  
{ []Ea0jYu  
  cout << "Towers of Hanoi: " << endl N^N?!I  
      << "moving a tower of n disks from pole A to pole B by using pole C" << endl; ,~iAoxD5jY  
  cout << "Input the height of the original tower: "; 0G 1o3[F  
  int height; ~` hcgCi%  
  cin >> height; 3NWAyCq-  
  hanoi(height); 21j+c{O  
;~;St>?\R\  
  system("PAUSE"); g7F Z -  
  return EXIT_SUCCESS; dfcG'+RU}  
} #^V"=RbD  
}(''|z#UE  
\ChcJth@o<  
Y'
h'8 \  
问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上 0/]vmDr  
".ZiR7Z:$Y  
到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一 bm.H0rHR4  
QD~`UJe>  
次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。 YPEd XU8}  
U:e9Vq'N m  
算法要点有二： b2%[9)"I.  
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次，设m为n位的二进制数，则m的取值范 h`j gF  
/XB1U[b  
围为0～2^n -1。让m每次递增1，可以发现，m中最低一位的刚刚由0变为1的位置的位置编号，和即将要移 0xcqX!(  
uy{KV"%"^g  
动的盘子编号有确定关系。 1hG O*cq!  
BI]t}7  
2、这个盘子往哪个柱子上移。 WG{/I/bJ
_  
a.第一次需要移动1号盘，n为奇数时，1号盘首先移动到柱子B，为偶数时首先移动到柱子C。 mio'm  
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子，因为移动的盘子 cf'Z#NfQ  
?Gfe?  
不能叠放到1号盘上，所以该盘可以移动的位置就是没有1号盘的那个柱子。 V:J6eks
_  
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的，因为移动的 Us5JnP5  
sSK$  
顺序（顺时针或逆时针）一旦确定，就不会更改，所以排除from的那个柱子后，移动方向也就唯一了。