汉诺塔非递归算法

汉诺塔非递归算法.我只是将盘子的数量等于2，3的情况代到网上别人给的算法中验证了一下，没有错。并没有证明算法的正确性。算法是否有效，有待大家证明。 uCUQxFp  
MdEZ839J  
include <iostream> ]j_S2lt  
#include <stdlib.h> hc~--[1c:  
>Qt#6X|  
#ifdef _WIN32 mC J/gWDY  
using namespace std; =_Qt&B)  
#endif - n11L  
n%Nf\z  
static void hanoi(int height) ]km8M^P  
{ (x?A#o>%  
  int fromPole, toPole, Disk; \JN<"/  
  int *BitStr = new int[height],   //用来计算移动的盘的号码  lR;<6  
    *Hold   = new int[height];   //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 1 ht4LRFi  
  char Place[] = {'A', 'C', 'B'}; nm\n\j~  
  int i, j, temp; xNq&_oY7  
3-LO  
  for (i=0; i < height; i++)               ~u}[VP  
  { dsJ}C|N  
    BitStr = 0; $WTu7lVV[1  
    Hold = 1; #2x\d  
  } M,cI0i  
  temp = 3 - (height % 2);               //第一个盘的柱号 MLa]s* ; d  
  int TotalMoves = (1 << height) - 1; BflF*-s ^  
  for (i=1; i <= TotalMoves; i++) bQ  
  { !|Vjv}UO  
    for (j=0 ; BitStr[j] != 0; j++)         //计算要移动的盘 u%h]k ,(E  
    { _|H]X+|  
        BitStr[j] = 0; "kf7??Z  
    } m,*t}j0 7  
    BitStr[j] = 1; A
O/J:`  
    Disk = j+1; i3#]_ p{  
    if (Disk == 1) mL3'/3-7:V  
    { }54\NSj0  
        fromPole = Hold[0]; Ct #hl8b:  
        toPole = 6 - fromPole - temp; //1+2+3等于6，所以6减去其它两个，剩下那个就是要移去的柱子 !BK^5,4?--  
        temp = fromPole;     //保存上一次从哪个柱子移动过来的 %&e5i  
    } /Q{Jf+>R>  
    else a>""MC2  
    { HykJ}ezX4  
        fromPole = Hold[Disk-1]; ng<|lsZd  
        toPole = 6 - Hold[0] - Hold[Disk-1]; Cn+TcdHX  
    }     8
kO|t!?:U  
    cout << "Move disk " << Disk << " from " << Place[fromPole-1] N"HN]Y@w  
        << " to " << Place[toPole-1] << endl; ~_^nWT*BV  
    Hold[Disk-1] = toPole; 2R|2yAh  
  } 0/-[k  
} R,6?1Z:J  
EeL~`$f  
!~>u\h  
:Wb+&|dU  
EY> %#0  
int main(int argc, char *argv[]) @8V8gV?zm  
{ E%/E%9-7\  
  cout << "Towers of Hanoi: " << endl 2+y4Gd 7  
      << "moving a tower of n disks from pole A to pole B by using pole C" << endl; _3kAN.g  
  cout << "Input the height of the original tower: "; iCz,|;w%  
  int height; =o+t_.)N  
  cin >> height; Lqwc:%Y:_  
  hanoi(height); g($y4~#  
Qv']*C[!z  
  system("PAUSE"); nA%-<  
  return EXIT_SUCCESS; aD%")eP%&  
} UW)k]@L  
eQzSWn[  
JX>_imo  
_gw~A{O  
问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上 _(oJ8h(  
kdgQ -UN$  
到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一 7\5 [lM  
K<\TF+  
次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。 #!Kg?BR2  
b
"{7f  
算法要点有二： Uv5E$Y"e10  
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次，设m为n位的二进制数，则m的取值范 !U=;e?o  
y{"8VT)  
围为0～2^n -1。让m每次递增1，可以发现，m中最低一位的刚刚由0变为1的位置的位置编号，和即将要移 L88
oh&M  
lD 9'^J  
动的盘子编号有确定关系。 ;~xkT'  
KA%tVBl  
2、这个盘子往哪个柱子上移。 o2F6K*u
}  
a.第一次需要移动1号盘，n为奇数时，1号盘首先移动到柱子B，为偶数时首先移动到柱子C。
coU`2n/  
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子，因为移动的盘子 >&BgF*mm  
LH0\Sm
hU  
不能叠放到1号盘上，所以该盘可以移动的位置就是没有1号盘的那个柱子。 `YIpZ rB  
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的，因为移动的 "64pVaT4  
H:p(C?tk{  
顺序（顺时针或逆时针）一旦确定，就不会更改，所以排除from的那个柱子后，移动方向也就唯一了。