汉诺塔非递归算法.我只是将盘子的数量等于2,3的情况代到网上别人给的算法中验证了一下,没有错。并没有证明算法的正确性。算法是否有效,有待大家证明。 jU9zCMyNF
R`3>0LrC8
include <iostream> GLcZ=6)"'
#include <stdlib.h> $vicHuX!
PQI,vr'R
#ifdef _WIN32 b42pLbpe'E
using namespace std; K]]rOF
#endif ~ !+h"%'t
^OcfM_4pN
static void hanoi(int height) `"-!UkD+
{ u9^;~i,
int fromPole, toPole, Disk; 4uVmhjT:X
int *BitStr = new int[height], //用来计算移动的盘的号码 jW0z|jr
*Hold = new int[height]; //用来存贮当前的盘的位置。hold[0]为第一个盘所在的柱号 Fea\ eB
char Place[] = {'A', 'C', 'B'}; Jn[ K0GV
int i, j, temp; $5AtI$TV_!
5pyvs ;As
for (i=0; i < height; i++) _"Ke=v_5
{ XI(@O)
BitStr = 0; h
swMy
Hold = 1; Tb6x@MorP
} "._WdY[
temp = 3 - (height % 2); //第一个盘的柱号 2o5<nGn
int TotalMoves = (1 << height) - 1; eii7pbc
for (i=1; i <= TotalMoves; i++) m%(JRh
{ `A{~}6jw
for (j=0 ; BitStr[j] != 0; j++) //计算要移动的盘 ;p"XCLHl
{ 9i)mv/i
BitStr[j] = 0; v@s`l#
} ;{7lc9uRj
BitStr[j] = 1; @"7dk.|
Disk = j+1; hG HzO
if (Disk == 1) ~u&O
{ m9 5$V&
fromPole = Hold[0]; Q&'Nr3H#tZ
toPole = 6 - fromPole - temp; //1+2+3等于6,所以6减去其它两个,剩下那个就是要移去的柱子 !!#ale&
temp = fromPole; //保存上一次从哪个柱子移动过来的 q5?mP6
} rBPxGBd4
else _qo1 GM&
{ eQIi}\`
fromPole = Hold[Disk-1]; :DpK{$eCb
toPole = 6 - Hold[0] - Hold[Disk-1]; qNVw+U;2P
} /;$ew~}
cout << "Move disk " << Disk << " from " << Place[fromPole-1] )Bvu[rUy
<< " to " << Place[toPole-1] << endl; >A "aOV>K
Hold[Disk-1] = toPole; &-Y:4.BX Z
} o%4+I>
} x=+I8Q4:
Lcb59Cs6e
({b/J0<@D
rz7b%WY
1T?%i
int main(int argc, char *argv[]) Wf w9cxGkf
{ }X:r:{r
cout << "Towers of Hanoi: " << endl phSP+/w
<< "moving a tower of n disks from pole A to pole B by using pole C" << endl; Bq8<FZr#!
cout << "Input the height of the original tower: "; % 7:
int height; |
lfPd
cin >> height; uCr
hanoi(height); ZSb+92g{L$
!_#js
system("PAUSE"); ;9sVWJJCw
return EXIT_SUCCESS; TrAUu`?#
} qz2d'OhmtH
7U0):11X#
V1qHl5"
<v^.FxId
问题描述:有三个柱子A, B, C. A柱子上叠放有n个盘子,每个盘子都比它下面的盘子要小一点,可以从上 lv&w p@
&bx,6dX
到下用1, 2, ..., n编号。要求借助柱子C,把柱子A上的所有的盘子移动到柱子B上。移动条件为:1、一 ;<