Posted on 2006-06-29 22:07
mahudu@cppblog 阅读(590)
评论(2) 编辑 收藏 引用 所属分类:
数据结构、算法
第一个是递归版本的：（没什么意思）
#include
<
iostream
>
using
namespace
std;
void
move(
char
from,
char
to)
{
cout
<<
from
<<
"
to
"
<<
to
<<
endl;
}
void
hanoi (
int
n,
char
from,
char
to,
char
bridge)
{
if
(n
==
1
)
move(from, to);
else
{
hanoi (n
-
1
, from, bridge, to);
move(from ,bridge);
hanoi (n
-
1
, bridge, from, to);
}
}
int
main()
{
int
n;
cout
<<
"
input n:\n
"
;
cin
>>
n;
hanoi (n,
'
A
'
,
'
C
'
,
'
B
'
);
return
0
;
}
第二个是递归版本的：（没有用栈，因此还比较精妙）
对不起，由于一时疏忽，把两个版本的程序贴成同一个了，十分抱歉，谢谢您的提醒，现更正如下：
#include
<
iostream
>
using
namespace
std;
void
hanoi(
int
n)
{
int
i, j, f
=
1
;
int
a
=
1
, b
=
(n
%
2
)
?
3
:
2
;
cout
<<
f
<<
"
from
"
<<
char
(
'
A
'
-
1
+
a)
<<
"
to
"
<< char('A' - 1 + b) << endl;
for(n = (1<<n) - 1, i = 1; i < n; i += 2)
{
for(f = 1, j = i; j%2; j/=2, f++);
if(f%2)
a ^= b;
b ^= a;
cout << f << " from " << char('A' - 1 + a) << " to "
<< char('A' - 1 + b) << endl;
a ^= b;
if(f%2)
b ^= a;
cout << f << " from " << char('A' - 1 + a) << " to "
<< char('A' - 1 + b) << endl;
}
}
int
main()
{
int
n;
cout
<<
"
input n:
"
;
cin
>>
n;
hanoi(n);
return
0
;
}