汉诺塔问题(C++版)
2024-08-30 14:20:21
题目描述 Description
约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面。 这是一个著名的问题,几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘,且不允许大盘放在小盘上面,所以64个盘的移动次数是:18,446,744,073,709,551,615 这是一个天文数字,若每一微秒可能计算(并不输出)一次移动,那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔,但很难用计算机解决64层的汉诺塔。
假定圆盘从小到大编号为1, 2, ...
输入描述 Input Description
第一行为一个正整数表示盘子的数量。
后面三行,每行一个字母,表示三个杆子从左到右的编号。
输出描述 Output Description
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如 a->3->b 的形式,即把编号为3的盘子从a杆移至b杆。
样例输入 Sample Input
2
a
b
c
样例输出 Sample Output
a->1->c
a->2->b
c->1->b
参考答案(C++版) Reference answer (C++ version) :
#include<bits/stdc++.h>
using namespace std;
void move(int n,char a,char b)
{
//将编号为n的盘子从a杆移动到b杆
cout<<a<<"->"<<n<<"->"<<b<<endl;
}
void f(int n,char a,char b,char c)
{
//将前n个盘子从a杆移动到b杆上,c杆作为辅助杆
if(n==)return;
f(n-,a,c,b);//将n-1个盘子从a杆移动到c杆,b作为辅助杆
move(n,a,b);
f(n-,c,b,a);//将c杆上的n-1个盘子移动到b杆上,a作为辅助杆
}
int main()
{
int n;
char a,b,c;
cin>>n>>a>>b>>c;
f(n,a,b,c);
}
最新文章
- 数据结构和算法 &ndash; 9.二叉树和二叉查找树
- WPF PRISM开发入门二(Unity依赖注入容器使用)
- mybatis配置优化
- linux配置文件的一些调优
- 【Android】首次进入应用时加载引导界面
- Android 随想录之 Android 系统架构
- Java Day 16
- Fitnesse+RestFixture:Web服务回归测试利器
- java中setDate(Date date)方法和String与Date之间的转换
- Android之 compileSdkVersion, minSdkVersion, and targetSdkVersion
- let 和 const
- C语言第五次博客作业
- 【反编译系列】一、反编译代码(dex2jar + jd-gui)和反编译资源(apktool)
- B-食物链-经典并查集
- 一个需求认识CSS3 的transform-origin属性
- springcloud(六):配置中心git示例
- REUSE_ALV_FIELDCATALOG_MERGE
- go语言之进阶篇 channel介绍
- Spark Streaming updateStateByKey案例实战和内幕源码解密
- window7下karma 报 The header content contains invalid characters BUG
热门文章
- php-生成数据库设计文档
- 我们在地址栏中输入一个网址,比如百度(www.baidu.com)后浏览器做了哪些事
- Basic4android v3.80 beta 发布
- CentOS7下安装配置Nginx
- MySQL的NO_BACKSLASH_ESCAPES
- (网络流)ACM Computer Factory --POJ --3436
- Codeforces807 B. T-Shirt Hunt 2017-05-08 23:23 175人阅读 评论(0) 收藏
- node API assert
- 后台返回的json数据传到前端页面并在页面的表格中填充
- delphi中如何控制listview的每行的颜色