汉诺塔非递归算法.我只是将盘子的数量等于2,3的情况代到网上别人给的算法中验证了一下,没有错。并没有证明算法的正确性。算法是否有效,有待大家证明。 (BJs6":BFe
p1Els/|
include <iostream> -O ej6sILO
#include <stdlib.h> <5nz:B/
V8c&2rNa
#ifdef _WIN32 `InS8PLr
using namespace std; N~a?0x
#endif +VTMa9d
nY6^DE2f
static void hanoi(int height) @P%&Dha
{ <%|2yPb]
int fromPole, toPole, Disk; kQYX[e7n
int *BitStr = new int[height], //用来计算移动的盘的号码 9XS'5AXN
*Hold = new int[height]; //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 .~Td/o7
char Place[] = {'A', 'C', 'B'}; VG)kPKoi
int i, j, temp; "6.kZ$`%
Peb;XI
for (i=0; i < height; i++) )4DF9 JpD
{ *c xYB
BitStr = 0; f 1]1ZOb
Hold = 1; OJ&~uV >2
} h_H$+!Nzb
temp = 3 - (height % 2); //第一个盘的柱号 >d_O0a*W-
int TotalMoves = (1 << height) - 1; +Ge-!&.;A
for (i=1; i <= TotalMoves; i++) X+iUT
{ 40mgB4I
for (j=0 ; BitStr[j] != 0; j++) //计算要移动的盘 0p8 (Q
{ >8EIm
BitStr[j] = 0; - wCfwC
} lLl^2[4k5
BitStr[j] = 1; ^hLAMaR
Disk = j+1; U@DIO/C,m`
if (Disk == 1) &_G^=Nc,H
{ :H3qa2p
fromPole = Hold[0]; I)T]}et
toPole = 6 - fromPole - temp; //1+2+3等于6,所以6减去其它两个,剩下那个就是要移去的柱子 [$f
temp = fromPole; //保存上一次从哪个柱子移动过来的 R0AVAUG
} r;SA1n#
else ~^
Q`dJL
{ >}Fe9Y.o
fromPole = Hold[Disk-1]; Wu?4oF
toPole = 6 - Hold[0] - Hold[Disk-1]; ``DS?pUY
} $3w a%"
cout << "Move disk " << Disk << " from " << Place[fromPole-1] !3E33
<< " to " << Place[toPole-1] << endl; L^!E4[ ^4
Hold[Disk-1] = toPole; tWT@%(2~0
} zq _*)V
} cl/}PmYIZ
M |6l
R$sG*=a!8j
3%p^>D\
:>+}|(v
int main(int argc, char *argv[]) XcD$xFDZ
{ ha&2V=
cout << "Towers of Hanoi: " << endl EA) K"C
<< "moving a tower of n disks from pole A to pole B by using pole C" << endl; vu Vcv
cout << "Input the height of the original tower: "; `2.[8%6
int height; Y`.FSs
cin >> height; ;Hk{bz(
hanoi(height); $t}t'uJ
-T$%MX
system("PAUSE"); eEl}.W}
return EXIT_SUCCESS; nJC/yS|
} @|BaZq,g
gE;r;#Jt4
?%K7IJ%
P+K< /i
问题描述:有三个柱子A, B, C. A柱子上叠放有n个盘子,每个盘子都比它下面的盘子要小一点,可以从上 C+tB$yahO
=n7QL QU
到下用1, 2, ..., n编号。要求借助柱子C,把柱子A上的所有的盘子移动到柱子B上。移动条件为:1、一 HtFc+%=
,}?x!3
次只能移一个盘子;2、移动过程中大盘子不能放在小盘子上,只能小盘子放在大盘子上。 |soDt<y+L
aGSix}b1P
算法要点有二: 6N+ ]g/_a
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次,设m为n位的二进制数,则m的取值范 (]ToBju
qJN!L))
围为0~2^n -1。让m每次递增1,可以发现,m中最低一位的刚刚由0变为1的位置的位置编号,和即将要移 ,E
] vM&
<MdIQ;I8
动的盘子编号有确定关系。 bYt[/K,
\7]0vG
2、这个盘子往哪个柱子上移。 hc#Sy:T>
a.第一次需要移动1号盘,n为奇数时,1号盘首先移动到柱子B,为偶数时首先移动到柱子C。 tr?U/YG
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子,因为移动的盘子 x6N)T4J(
meJ%mY
不能叠放到1号盘上,所以该盘可以移动的位置就是没有1号盘的那个柱子。 ' ?tx?t
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的,因为移动的 Qze.1h
[P_@-:(O
顺序(顺时针或逆时针)一旦确定,就不会更改,所以排除from的那个柱子后,移动方向也就唯一了。