精选文章 n阶Hanoi塔问题(递归)

n阶Hanoi塔问题(递归)

作者:梦安魂九霄 时间: 2020-08-05 10:22:49
梦安魂九霄 2020-08-05 10:22:49

描述

假设有三个分别命名为X、Y和Z的塔座,在塔座X上插有n个直径大小各不相同、依小到大编号为1,2,...,n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排,圆盘移动时必须遵循下列规则:

1)每次只能移动一个圆盘;

2)圆盘可以插在X、Y和Z中的任一塔座上;

3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。

如何实现移动圆盘的操作呢?当n=1时,问题比较简单,只要将编号为1的圆盘从塔座X直接移至塔座Z上即可;当n>1时,需利用塔座Y作辅助塔座,若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X(依照上述法则)移至塔座Y上,则可先将编号为n的圆盘从塔座X移至塔座Z上,然后再将塔座Y上的n-1个圆盘(依照上述法则)移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题,只是问题的规模小1,因此可以用同样的方法求解。

输入

输入数据有多组,每组1个整数n,表示Hanoi塔的阶数。

输出

将每次移动(move)按照以下格式输出:%2d. Move disk %d from %c to %c\n
上述格式中第一个整数表示第几次移动,第二个整数表示移动第几个圆盘,后两个字符表示将圆盘从哪个塔座移至哪个塔座上。每组输出后面输出一个空行。

输入样例 1 

1
2
3

输出样例 1

 1. Move disk 1 from X to Z

 1. Move disk 1 from X to Y
 2. Move disk 2 from X to Z
 3. Move disk 1 from Y to Z

 1. Move disk 1 from X to Z
 2. Move disk 2 from X to Y
 3. Move disk 1 from Z to Y
 4. Move disk 3 from X to Z
 5. Move disk 1 from Y to X
 6. Move disk 2 from Y to Z
 7. Move disk 1 from X to Z

提示:

1、算法描述中输出使用的是%i,实际上就是使用%d。

2、输出时移动次数是两位的,我们保证输入量不会太大。

3、如果使用全局变量来记录移动的次数,注意每次在进行一个新的一组测试时,需要将这个全局计数变量设为0。

代码

#include 
using namespace std;
int m=1;  
void  Move (char x,int n,char y){
    printf("%2d. Move disk %d from %c to %c\n",m,n,x,y);
    m++;
}

void hanoi (int n,char x,char y,char z){
    if (n==1){Move(x,1,z);}
    else {
        hanoi (n-1,x,z,y);
        Move (x,n,z);
        hanoi (n-1,y,x,z);
    }
}

int main()
{
    int n;
    while (cin>>n){
    hanoi(n,'X','Y','Z');
    m=1;
    cout<

 

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:202006-3 CCF CSP认证 Markdown渲染器 (可查看渲染后文本-详解大模拟)

下一篇:MongoDB入门培训 | 8周入门NoSQL No.1数据库

您可能感兴趣

  • 各大公司面试题集锦

    百度一面 1、给定一个字符串比如“abcdef”,要求写个函数编程“defabc”,位数是可变的。这个比较简单,我用的是strcpy和memcpy,然后他问有什么优化的办法,我就不知道了。 2、socket过程就是socket的server和client整个流程写下来,这个还是没啥问题的。 3、数据结构二叉树的遍历,给了个二叉树,前序、中序、后序写出来,这个没什么难度。 http://blo...

  • java入门到秃路线导航,元芳你怎么看?【教学视频+博客+书籍整理】

    目录 一、Java基础 二、关于JavaWeb基础 三、关于数据库 四、关于ssm框架 五、关于数据结构与算法 六、关于开发工具idea 七、关于项目管理工具Mawen、Git、SVN、Gradle.... 八、关于计算机网络原理 九、关于设计模式 十、关于中间件Shiro、Lucene、Solr...

  • 线性表2019-10-27

    顺序表的特点: 1、表中各个元素存放在连续的存储空间中; 2、表中各个元素的存储顺序与线性表中逻辑顺序相同。 插入元素时间复杂度为O(N),移动数据元素n-i次 删除元素时间复杂度为O(N),移动数据元素n-i-1次 顺序表优点:存储结构和逻辑结构一致。结构简单。 缺点:需要足够的空间,插入和删除效率低。 栈: 后进先出 一个指针top指向栈顶,一个指针bottom指向栈底。 双栈: 0-1...

  • 数据结构--递归

    一场游戏一场空,最终 最初都由我掌控,好像一身从容,不曾有狼狈伤痛,可深夜一个人该如何相拥? 递归总的来说就两步: (1)判断出口--递归结束 (2)写函数体--递归求解情况 我们所用的链表就是基于递归算法设计的。 记录一个经典的递归例题:汉诺塔问题(简单版),这里会写出递归版本和非递归版本 递归版本: #include #include #include #include #inc...

  • 深度学习中的一些基础干货

    作者:HarleysZhang 来源:2019_algorithm_intern_information @ GitHub,谢谢原作者的分享 卷积输出大小计算 CNN中术语解释 CNN网络的主要参数有下面这么几个: 卷积核Kernal(在Tensorflow中称为filter); 填充Padding; 滑动步长Strides; 池化核Kernal(在Tensorflow中称为filter);...

  • 【连载】人类唯一的出路:变成人工智能(二)脑机接口

    在一个由人工智能和“其他所有生物”组成的未来, 人类只有一条出路:“变成人工智能。” 本长文作者是Tim Urban,之前火热的文章《为什么有很多名人让人们警惕人工智能》也是出自他手,英文原文刊载于waitbutwhy.com,点击文末的阅读原文可以跳转到原文链接。 本翻译版本由谢熊猫君提供,全文共六万字。两百余张图片,分成六个章节,将分成五篇推送完成。 第一章:人类巨灵 (约7000字)简...

  • 面试刷题10-14

    头条三面面经 编程题: 1. 实现hashMap,主要是put和delete操作 2. 实现除法,1/2 = 0.5, 1/3 = 0.(3) 循环部分用括号包裹 3. 数组的度,leetcode原题 Redis的String和hash的具体实现 hash的复制过程。 字节三面面经,一面和二面面完有点久了,记录的不完整 一面 1、熟悉的软件测试的方法 2、写一个快排 3、软件测试的流程 4、...

  • NJU-高级算法-汉诺塔

    Description 汉诺塔问题中限制不能将一层塔直接从最左侧移动到最右侧,也不能直接从最右侧移动到最左侧,而是必须经过中间。求当有N层塔的时候移动步数。 Input 输入第一行为用例个数, 每个测试用例输入的第一行为N。 Output 移动步数。 Sample Input 1 1 2 Sample Output 1 8 思路 思路一:递归 倒着看这个问题,把前n-1个盘子看作一个整体,则...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。