Posted on 2006-06-29 22:07
mahudu@cppblog 阅读(581)
评论(2) 编辑 收藏 引用 所属分类:
数据结构、算法
第一个是递归版本的:(没什么意思)
#include
<
iostream
>
using
namespace
std;
![](/Images/OutliningIndicators/None.gif)
void
move(
char
from,
char
to)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
cout
<<
from
<<
"
to
"
<<
to
<<
endl;
}
![](/Images/OutliningIndicators/None.gif)
void
hanoi (
int
n,
char
from,
char
to,
char
bridge)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
if
(n
==
1
)
move(from, to);
else
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
hanoi (n
-
1
, from, bridge, to);
move(from ,bridge);
hanoi (n
-
1
, bridge, from, to);
}
}
![](/Images/OutliningIndicators/None.gif)
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
n;
cout
<<
"
input n:\n
"
;
cin
>>
n;
hanoi (n,
'
A
'
,
'
C
'
,
'
B
'
);
return
0
;
}
第二个是递归版本的:(没有用栈,因此还比较精妙)
对不起,由于一时疏忽,把两个版本的程序贴成同一个了,十分抱歉,谢谢您的提醒,现更正如下:
#include
<
iostream
>
using
namespace
std;
![](/Images/OutliningIndicators/None.gif)
void
hanoi(
int
n)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
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)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
n;
cout
<<
"
input n:
"
;
cin
>>
n;
hanoi(n);
return
0
;
}