Posted on 2006-06-29 22:07
mahudu@cppblog 閱讀(600)
評論(2) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結構、算法
第一個是遞歸版本的：（沒什么意思）
?
#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
;?
}
?
?
?
第二個是遞歸版本的：（沒有用棧，因此還比較精妙）
對不起，由于一時疏忽，把兩個版本的程序貼成同一個了，十分抱歉，謝謝您的提醒，現(xiàn)更正如下：
#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
;
}
?