汉诺塔非递归算法.我只是将盘子的数量等于2,3的情况代到网上别人给的算法中验证了一下,没有错。并没有证明算法的正确性。算法是否有效,有待大家证明。 90D.G_45
vu >@_hv
include <iostream> a
:AcCd)
#include <stdlib.h> -ouL4
Ggjb86v\
#ifdef _WIN32 |.nWy"L
using namespace std; o7B+f
#endif OZ9j3Q;a$
)dDmq
static void hanoi(int height) (:]iHg3
{ WTN!2b
int fromPole, toPole, Disk; f\w4F'^tj
int *BitStr = new int[height], //用来计算移动的盘的号码 -bQvJ`iF
*Hold = new int[height]; //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 cu|q&
char Place[] = {'A', 'C', 'B'}; 'Q,<_L"
int i, j, temp; 8Wp1L0$B
`o'sp9_3
for (i=0; i < height; i++) nwH|Hs riU
{ [/]3:|
BitStr = 0; !Xce iQu
Hold = 1; J1MnkxJmpQ
} jZyh
temp = 3 - (height % 2); //第一个盘的柱号 Z6pDQ^Ii
int TotalMoves = (1 << height) - 1; f89<o#bm7h
for (i=1; i <= TotalMoves; i++) 36UWoo
{ Yb/^Qk59
for (j=0 ; BitStr[j] != 0; j++) //计算要移动的盘 ||NCVGJG
{ C.p*mO&N
BitStr[j] = 0; w=2X[V}
} Hb4rpAeP
BitStr[j] = 1; (b!DJ;(O9
Disk = j+1; BtZm_SeA
if (Disk == 1) -ZJ:<
{ gRSG[GMV
fromPole = Hold[0]; H-lRgJdc
toPole = 6 - fromPole - temp; //1+2+3等于6,所以6减去其它两个,剩下那个就是要移去的柱子 \/zS@fz
temp = fromPole; //保存上一次从哪个柱子移动过来的 B)*%d7=x
} NYRNop( N#
else UkQocZdZ
{ 1-<Xi-=^{t
fromPole = Hold[Disk-1]; qILr+zH
toPole = 6 - Hold[0] - Hold[Disk-1]; F@3,>~[%I
} oaE3Aa
cout << "Move disk " << Disk << " from " << Place[fromPole-1] JOk`emle
<< " to " << Place[toPole-1] << endl; _:
x$"i
Hold[Disk-1] = toPole; e&nw&9vo
} ),|bP`V
} IC~D?c0H:
#k, kpL<a
6 , ~aV
VtFh1FDI\
cMAfW3j: ;
int main(int argc, char *argv[]) E ..[F<5
{ g`8|jg0]`I
cout << "Towers of Hanoi: " << endl SNFz#*
<< "moving a tower of n disks from pole A to pole B by using pole C" << endl; beoMLHp
cout << "Input the height of the original tower: "; &*~
WK
int height; `dhK$jYD
cin >> height; h#9)M
hanoi(height); {D8IA3w
CPG %*E*
system("PAUSE"); g?wogCs5
return EXIT_SUCCESS; _>l,%n
} A 78{b^0*
zvWQ&?&o2
=?hlgQ
#'oKkrl
问题描述:有三个柱子A, B, C. A柱子上叠放有n个盘子,每个盘子都比它下面的盘子要小一点,可以从上 NeP1 #
7)#/I
到下用1, 2, ..., n编号。要求借助柱子C,把柱子A上的所有的盘子移动到柱子B上。移动条件为:1、一 u@Lu.t!],
@hv]
[(<
次只能移一个盘子;2、移动过程中大盘子不能放在小盘子上,只能小盘子放在大盘子上。 -Zh+5;8g
f5v|}gMAX
算法要点有二: *']RYu?X
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次,设m为n位的二进制数,则m的取值范 @ck2j3J/
C+j+q648>
围为0~2^n -1。让m每次递增1,可以发现,m中最低一位的刚刚由0变为1的位置的位置编号,和即将要移 LV0{~g(!%
ufOaD7
动的盘子编号有确定关系。 <j'#mUzd
`P~RG.HO
2、这个盘子往哪个柱子上移。 nq;)!Wry
a.第一次需要移动1号盘,n为奇数时,1号盘首先移动到柱子B,为偶数时首先移动到柱子C。 U_?RN)>j
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子,因为移动的盘子 49D*U5o
B~IOM
不能叠放到1号盘上,所以该盘可以移动的位置就是没有1号盘的那个柱子。 wv$=0zF
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的,因为移动的 E}u\{uY
B#}RMFIj
顺序(顺时针或逆时针)一旦确定,就不会更改,所以排除from的那个柱子后,移动方向也就唯一了。