汉诺塔非递归算法.我只是将盘子的数量等于2,3的情况代到网上别人给的算法中验证了一下,没有错。并没有证明算法的正确性。算法是否有效,有待大家证明。 7Q,<h8N\5
E,ooD3$h
include <iostream> i+lq:St
#include <stdlib.h> G;USVF-'K
0T0I<t
#ifdef _WIN32 K1-RJj\L
using namespace std; -iFFXESVX
#endif *z_`$Y
o,xy'
static void hanoi(int height) ZVit]3hd
{ ~{N#JOY}Z
int fromPole, toPole, Disk; h]IoH0/
int *BitStr = new int[height], //用来计算移动的盘的号码 U.ZA%De
*Hold = new int[height]; //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 JV+Uy$P!
char Place[] = {'A', 'C', 'B'}; JIc9csr:b
int i, j, temp; v
"[<pFj^
aJc>"#+
o
for (i=0; i < height; i++) X7gB.=\X
{ >y!O_@>z
BitStr = 0; m |.0$+=
Hold = 1; ISTAJ8"
D
} $"#M:V@
temp = 3 - (height % 2); //第一个盘的柱号 +aqQa~}r
int TotalMoves = (1 << height) - 1; [$fB]7A
for (i=1; i <= TotalMoves; i++) =PnNett}a
{ !~j9Oc^
for (j=0 ; BitStr[j] != 0; j++) //计算要移动的盘 {96NtR0Z
{ PTTUI
BitStr[j] = 0; QD1&"T<.d.
} IWwOP{ <ZQ
BitStr[j] = 1; t{B6W)q
Disk = j+1; F>E_d<m
if (Disk == 1) brLu~]I
{ {n S(B
fromPole = Hold[0]; i?)bF!J
toPole = 6 - fromPole - temp; //1+2+3等于6,所以6减去其它两个,剩下那个就是要移去的柱子 ?*<1B
temp = fromPole; //保存上一次从哪个柱子移动过来的 w2^s}NO
} 6.a>7-K}%
else ^{NN-
{ 0XE(v c!
fromPole = Hold[Disk-1]; x_l8&RIB*
toPole = 6 - Hold[0] - Hold[Disk-1]; nppSrj?
} R/6
v#9m7
cout << "Move disk " << Disk << " from " << Place[fromPole-1] A}3E)Qo=G
<< " to " << Place[toPole-1] << endl; 715J1~aRNr
Hold[Disk-1] = toPole; "kucFf f
} 'z+Pa^)v
} v~p?YYOm<
ONc#d'-L
8zwH^q[`r
f,BJb+0
.li)k[] ts
int main(int argc, char *argv[]) #X6=`Xe#
{ U)3?&9H
cout << "Towers of Hanoi: " << endl ;zWiPnX}
<< "moving a tower of n disks from pole A to pole B by using pole C" << endl; -7 EwZRS@9
cout << "Input the height of the original tower: "; 64:p 4N
int height; sr~VvciIy
cin >> height; C3 m_sv#e
hanoi(height); DG3Mcf@5
G)""^YB-
system("PAUSE"); l
5f'R
return EXIT_SUCCESS; U1kW1L}B
} nYj7r*e[
q@4Cw&AI+
FE06,i\{
N0ZD+
问题描述:有三个柱子A, B, C. A柱子上叠放有n个盘子,每个盘子都比它下面的盘子要小一点,可以从上 :rvBx"
-{yG+1
到下用1, 2, ..., n编号。要求借助柱子C,把柱子A上的所有的盘子移动到柱子B上。移动条件为:1、一 T{BGg
A\ tBmL_s
次只能移一个盘子;2、移动过程中大盘子不能放在小盘子上,只能小盘子放在大盘子上。 ZV07;`I
y cWY.HD
算法要点有二: u#->?
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次,设m为n位的二进制数,则m的取值范 q z!^<
M
lDs C>L-F
围为0~2^n -1。让m每次递增1,可以发现,m中最低一位的刚刚由0变为1的位置的位置编号,和即将要移 swhtlc@@
CT|H1Ry2T
动的盘子编号有确定关系。 UZgrSX {
V{rQ@7SE
2、这个盘子往哪个柱子上移。 kioIyV\=
a.第一次需要移动1号盘,n为奇数时,1号盘首先移动到柱子B,为偶数时首先移动到柱子C。 -BsZw.
7P
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子,因为移动的盘子 nH[>Sff$
HaOSFltf#
不能叠放到1号盘上,所以该盘可以移动的位置就是没有1号盘的那个柱子。 Z,F1n/7
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的,因为移动的 r&XxF>
:vC+}.{p
顺序(顺时针或逆时针)一旦确定,就不会更改,所以排除from的那个柱子后,移动方向也就唯一了。