汉诺塔非递归算法.我只是将盘子的数量等于2,3的情况代到网上别人给的算法中验证了一下,没有错。并没有证明算法的正确性。算法是否有效,有待大家证明。 i |^`gly
.z>." `
include <iostream> WAa1H60VkS
#include <stdlib.h> @?=)}2=|?i
R"t$N@ZFb
#ifdef _WIN32 '/*c Yv45
using namespace std; ~0'l,
#endif IIn\{*|mW
x15tQb+
static void hanoi(int height) r~2@#gTbl
{ ZznWs+
int fromPole, toPole, Disk; 7%}3Ghc%
int *BitStr = new int[height], //用来计算移动的盘的号码 DJ[#H
*Hold = new int[height]; //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 U(]5U^
char Place[] = {'A', 'C', 'B'}; ,$qs9b~
int i, j, temp; H.[&gm}p>
F}.TT=((8
for (i=0; i < height; i++) {]Iu">*
{ U`p<lxRgQ
BitStr = 0; +\oHQ=s>}\
Hold = 1; molowPI
} hJ*E"{xs
temp = 3 - (height % 2); //第一个盘的柱号 gO%i5
int TotalMoves = (1 << height) - 1; >,Bu^] C
for (i=1; i <= TotalMoves; i++) *g41"Cl
{ 5XUI7Q%
for (j=0 ; BitStr[j] != 0; j++) //计算要移动的盘 =l'_*B8
{ 6ch[B`[h,
BitStr[j] = 0; QIV~)`;
} ~JPzjE
BitStr[j] = 1; {=4:Tgw
Disk = j+1;
q8bS@\i
if (Disk == 1) 4KSN;G
{ FH21m wV
fromPole = Hold[0]; J<* Mk
toPole = 6 - fromPole - temp; //1+2+3等于6,所以6减去其它两个,剩下那个就是要移去的柱子 g):jZU]b
temp = fromPole; //保存上一次从哪个柱子移动过来的 9k^=m)yS'
} iC+H;s5<
else o5x^ "#
{ t-(7Q8(
fromPole = Hold[Disk-1]; a&VJYAB
toPole = 6 - Hold[0] - Hold[Disk-1]; ;1k0o.3
} fDHISJv
cout << "Move disk " << Disk << " from " << Place[fromPole-1] wSyu^KDz
<< " to " << Place[toPole-1] << endl; jeFl+K'1
Hold[Disk-1] = toPole; |+~2sbM
} H&IP>8Dk
} :Qp/3(g e
3A}8?
Du4#\OK
^Jc0c)*
1CVaGD^r{
int main(int argc, char *argv[]) 6yM dl~.
{ 1H
6Wrik
cout << "Towers of Hanoi: " << endl kDa#yN\
<< "moving a tower of n disks from pole A to pole B by using pole C" << endl; +r P<m
cout << "Input the height of the original tower: "; :8wF0n-'
int height; !`=?<Fl
cin >> height; 6e|5qKr
hanoi(height); $*-L8An?
:P"Gym
system("PAUSE"); rO%+)M$A
return EXIT_SUCCESS; G_mu7w
} }PL
Tic9ri
6&0a?Xu
{[~,q\M[
问题描述:有三个柱子A, B, C. A柱子上叠放有n个盘子,每个盘子都比它下面的盘子要小一点,可以从上 I|;#VejX
94@!.11
到下用1, 2, ..., n编号。要求借助柱子C,把柱子A上的所有的盘子移动到柱子B上。移动条件为:1、一 yuX0Y{:I
DP]|}8~L
次只能移一个盘子;2、移动过程中大盘子不能放在小盘子上,只能小盘子放在大盘子上。 n7uD(cL
g(H3arb&
算法要点有二: vJUB; hD
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次,设m为n位的二进制数,则m的取值范 [KJL%u|8/
:C6rN}_k
围为0~2^n -1。让m每次递增1,可以发现,m中最低一位的刚刚由0变为1的位置的位置编号,和即将要移 Z5-'|h$|
t O>qd#I
动的盘子编号有确定关系。 Lpf=VyqC
?EAqv]
2、这个盘子往哪个柱子上移。 (Z +C
a.第一次需要移动1号盘,n为奇数时,1号盘首先移动到柱子B,为偶数时首先移动到柱子C。 ,SwaDWNO
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子,因为移动的盘子 <);u]0
}TvAjLIS6
不能叠放到1号盘上,所以该盘可以移动的位置就是没有1号盘的那个柱子。 QLG,r^
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的,因为移动的 hDMp^^$
}>U03aa!
顺序(顺时针或逆时针)一旦确定,就不会更改,所以排除from的那个柱子后,移动方向也就唯一了。