汉诺塔非递归算法

汉诺塔非递归算法.我只是将盘子的数量等于2，3的情况代到网上别人给的算法中验证了一下，没有错。并没有证明算法的正确性。算法是否有效，有待大家证明。 h2SVDKj  
WPmH4L>T  
include <iostream> `m.).Hda  
#include <stdlib.h> =o@CCUKpj  
'edd6yTd  
#ifdef _WIN32 R
pAqnDX)  
using namespace std; r
fgkw  
#endif l$PSID  
3 ?1qI'5  
static void hanoi(int height) (}W+W\.  
{ =z5'A|Wa=,  
  int fromPole, toPole, Disk; b1(7<o  
  int *BitStr = new int[height],   //用来计算移动的盘的号码 3 %ppvvQ  
    *Hold   = new int[height];   //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 F3XB};  
  char Place[] = {'A', 'C', 'B'}; LyaFWx  
  int i, j, temp; 1VlRdDg  
4$);x/ a  
  for (i=0; i < height; i++)               /!l$Y?  
  { b?p<y`  
    BitStr = 0; X0\2qD  
    Hold = 1; -bN;n
S
gb  
  } )"W(0M]>  
  temp = 3 - (height % 2);               //第一个盘的柱号 Z r}5)ZR.  
  int TotalMoves = (1 << height) - 1; EqN<""2  
  for (i=1; i <= TotalMoves; i++) FUVoKX!#  
  { |a3v!va  
    for (j=0 ; BitStr[j] != 0; j++)         //计算要移动的盘  `UC  
    { #Sxk[[KwH*  
        BitStr[j] = 0; cjf 8N:4N0  
    } .l| [e  
    BitStr[j] = 1; 66P'87G  
    Disk = j+1; #y<KO`Es  
    if (Disk == 1) iYqZBLf{S  
    {
kYlsjM  
        fromPole = Hold[0]; 0pO{{F  
        toPole = 6 - fromPole - temp; //1+2+3等于6，所以6减去其它两个，剩下那个就是要移去的柱子 T
<hS  
        temp = fromPole;     //保存上一次从哪个柱子移动过来的 s$cr|p;7#
 
    } '
MM%Sm,  
    else 81gcM
?  
    { O_zW/#  
        fromPole = Hold[Disk-1]; LW={| 3}  
        toPole = 6 - Hold[0] - Hold[Disk-1]; P=.yXirm?  
    }     mv5=>Xc6  
    cout << "Move disk " << Disk << " from " << Place[fromPole-1] +VJS/  
        << " to " << Place[toPole-1] << endl; ! :[`>=!  
    Hold[Disk-1] = toPole; :bh#,]'  
  } F/ZB%;O9  
} _JVFn=  
PQl^jS  
lO (MF  
[~3[Tu( C  
b`%3>  
int main(int argc, char *argv[]) Zj+S"`P  
{ eP d  
  cout << "Towers of Hanoi: " << endl (=2-*((&(A  
      << "moving a tower of n disks from pole A to pole B by using pole C" << endl; W'|NYw_B  
  cout << "Input the height of the original tower: "; :]Nn(},  
  int height; YXJreM5  
  cin >> height; kPhdfF*Q  
  hanoi(height); <Km ^>9  
~4 ~c+^PF  
  system("PAUSE"); Ic 5TtN~/>  
  return EXIT_SUCCESS; !2.(iuE  
} mH1T|UI  
N\,[(LbA
&  
}McqoZ%F  
:3J0Q  
问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上 L701j.7"  
;PS V3Zh  
到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一 v qt#JdPp9  
'n:|D7t  
次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。 @U8}K#  
M id v  
算法要点有二： jR1o<]
?  
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次，设m为n位的二进制数，则m的取值范 J0ysZ]  
9HsiAi*  
围为0～2^n -1。让m每次递增1，可以发现，m中最低一位的刚刚由0变为1的位置的位置编号，和即将要移 3V(]*\L  
oZD+AF$R  
动的盘子编号有确定关系。  hT
Ewp.  
4YV0v,z  
2、这个盘子往哪个柱子上移。 >>cb0fH
5  
a.第一次需要移动1号盘，n为奇数时，1号盘首先移动到柱子B，为偶数时首先移动到柱子C。 #r=Jc8J_  
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子，因为移动的盘子 Tvd}5~ 5?  
[P'"|TM[~  
不能叠放到1号盘上，所以该盘可以移动的位置就是没有1号盘的那个柱子。 </hv{<  
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的，因为移动的 IP LKOT~  
syJLcK+e  
顺序（顺时针或逆时针）一旦确定，就不会更改，所以排除from的那个柱子后，移动方向也就唯一了。