汉诺塔非递归算法.我只是将盘子的数量等于2,3的情况代到网上别人给的算法中验证了一下,没有错。并没有证明算法的正确性。算法是否有效,有待大家证明。 *I7$\0Q
c}K>#{YeB
include <iostream> KTX;x2r
#include <stdlib.h> R1Jj 3k
9l9h*Pgt
#ifdef _WIN32 I9GRSm;0<
using namespace std; |` gSkv
#endif aKdi
vCE1R]^A.]
static void hanoi(int height) cl s-x@
Kd
{ Q$_S/d%*
int fromPole, toPole, Disk; G%N3h'zDi
int *BitStr = new int[height], //用来计算移动的盘的号码 VHhW_ya1g{
*Hold = new int[height]; //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 _:|/4.]`_
char Place[] = {'A', 'C', 'B'}; \Q[u ?/TF
int i, j, temp; n DLr17
zx
for (i=0; i < height; i++) vr#_pu)f4
{ }lzUl mRTe
BitStr = 0; alM
^
X
Hold = 1; -xi]~svg
} sG{hUsPa
temp = 3 - (height % 2); //第一个盘的柱号 [hU5ooB
int TotalMoves = (1 << height) - 1; VY }?Nb<&
for (i=1; i <= TotalMoves; i++) J}IHQZS
{ GY9CU=-
for (j=0 ; BitStr[j] != 0; j++) //计算要移动的盘 A
i`
{ PfKIaW<
BitStr[j] = 0; =#qf0
} f{=0-%dA
BitStr[j] = 1; Z6G>j
Disk = j+1; "_Wv,CYmNr
if (Disk == 1) =lIG#{`Q
{ 7I>@PVN
fromPole = Hold[0]; @ %LrpD
toPole = 6 - fromPole - temp; //1+2+3等于6,所以6减去其它两个,剩下那个就是要移去的柱子 0_7A
<
temp = fromPole; //保存上一次从哪个柱子移动过来的
h"<-^=b
} 5"1kfB3v
else G2Zr(b')
{ cnfjOg'\{
fromPole = Hold[Disk-1]; J)R;NYl
toPole = 6 - Hold[0] - Hold[Disk-1]; 0&!,+
} __Ei;%cV
cout << "Move disk " << Disk << " from " << Place[fromPole-1] #P8R
<< " to " << Place[toPole-1] << endl; m4FT^^3yE
Hold[Disk-1] = toPole; fN4d^0&
} 9\F:<Bf$#
} *^cJn*QeL
bnS"@^M
I@x^`^+l
l_
/q/8-l
go^?F-
dZ
int main(int argc, char *argv[]) at_~b Ox6X
{ Na8%TT>
cout << "Towers of Hanoi: " << endl
[0v`E5
<< "moving a tower of n disks from pole A to pole B by using pole C" << endl; 7Ddo^Gtx
cout << "Input the height of the original tower: "; vvEr}G
int height; w-9FF%@<
cin >> height; R~nbJx$
hanoi(height); 4Eq$f (QJ
|fYr*8rH
system("PAUSE"); dq$H^BB+>
return EXIT_SUCCESS; P[NAO>&t