4412 汉诺塔

2018-06-22 05:12:49来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

4412 汉诺塔

 

 时间限制: 2 s
 空间限制: 1000 KB
 题目等级 : 白银 Silver
 
 
 
题目描述 Description


<a href="http://www.jzxx.net/Student/ShowArticle.asp?ArticleID=15648" target="_blank">汉诺塔(又称河内塔)</a>问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。面对庞大的数字(移动圆片的次数)18446744073709551615,看来,众僧们耗尽毕生精力也不可能完成金片的移动。 后来,这个传说就演变为汉诺塔游戏:   1.有三根杆子A,B,C。A杆上有若干碟子   2.每次移动一块碟子,小的只能叠在大的上面   3.把所有碟子从A杆全部移到C杆上  经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片:  如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C   此外,汉诺塔问题也是程序设计中的经典递归问题。  算法思路:  1.如果只有一个金片,则把该金片从源移动到目标棒,结束。  2.如果有n个金片,则把前n-1个金片移动到辅助的棒,然后把自己移动到目标棒,最后再把前n-1个移动到目标棒.

 

 

输入描述 Input Description

一个整数N,表示A柱上有N个碟子。

 

输出描述 Output Description

若干行,即移动的最少步骤

 

样例输入 Sample Input

3

样例输出 Sample Output

 

A To C
A To B
C To B
A To C
B To A
B To C
A To C

<a href="http://www.jzxx.net/Student/ShowArticle.asp?ArticleID=15648" target="_blank" style="white-space: normal;"></a>

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int k=0,n;
void mov(int n,char a,char c,char b)
{
if (n==0) return;
mov(n-1,a,b,c );
cout<<a<<" "<<"To"<<" "<<c<<endl;
mov(n-1,b,c,a );
}
int main() {
cin>>n;
mov(n,'A','C','B');
return 0;
}

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<string>
 6 #include<cmath>
 7 using namespace std;
 8 int k=0,n;
 9 void mov(int n,char a,char c,char b)
10 {
11     if (n==0) return;
12     mov(n-1,a,b,c );
13     cout<<a<<" "<<"To"<<" "<<c<<endl;
14     mov(n-1,b,c,a );
15 }
16 int main() {
17     cin>>n;
18     mov(n,'A','C','B');
19     return 0;
20 }

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:php文件管理与基础功能的实现

下一篇:微信模板消息 PHP