汉诺塔（Tower of Hanoi）--------递归思路_汉诺塔递归-程序员宅基地

技术标签： 算法  C语言  c语言  

汉诺塔问题简介：

有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移到柱子C上，并且每次移动，同一根柱子上都只能是大盘子在下，小盘子在上，请问至少需要多少次移动？

汉诺塔问题分析：

1.     若只有1个圆盘，就只需要移动 1 次，即 A → C;

2.     若有两个圆盘，则需要移动 3 次，即 A→B,A→C,B→C;

 3.    若有三个圆盘，则需要移动 7 次，即 A→ C,A→ B,C→ B,A→ C,B→ A,B→ C,A→ C

依此类推.......

汉诺塔问题的递归思路：

将 n 个圆盘分为 n-1 （即除最低层的圆盘）与 1 （即最底层的圆盘），将n-1个圆盘移动到中转位置，将1移动到目的位置，再将 n-1 分为 （n-1）- 1 与 1，将（n-1）- 1 移动到中转位置，将1移动到目的位置，依次类推......

代码如下:

#include<stdio.h>
//打印每一步的操作
void move(char a, char b)
{
	printf(" %c -> %c ", a, b);
}
//n:有几个盘子
//a:起始位置
//b:中转位置
//c:目的位置
void hbt(int n, char a, char b, char c)
{
	if (n == 1)
		move(a, c);
	else//n>=2时
	{
		hbt(n - 1, a, c, b);
        //此时n-1的起始位置是a,中转位置是c,目的位置是b
		move(a, c);
        //将 1 从起始位置 a 移动到目的位置 c
		hbt(n - 1, b, a, c);
        //将 n-1 从起始位置 b,通过中转位置a,移动到目的位置 c
	}

}
int main()
{
	hbt(3, 'A', 'B', 'C');
    //3就代表有3个盘子，可修改
	return 0;
}

 图示如下：

 注意：这里的起始位置，中转位置和目的位置是相对的，最终是要将圆盘从A移到C！！！！！！
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/m0_74859835/article/details/128708887

智能推荐

前端开发之vue-grid-layout的使用和实例-程序员宅基地

文章浏览阅读1.1w次，点赞7次，收藏34次。vue-grid-layout的使用、实例、遇到的问题和解决方案_vue-grid-layout

Power Apps-上传附件控件_powerapps点击按钮上传附件-程序员宅基地

文章浏览阅读218次。然后连接一个数据源，就会在下面自动产生一个添加附件的组件。把这个控件复制粘贴到页面里，就可以单独使用来上传了。插入一个“编辑”窗体。_powerapps点击按钮上传附件

C++ 面向对象（Object-Oriented）的特征 & 构造函数& 析构函数_"object(cnofd[\"ofdrender\"])十条"-程序员宅基地

文章浏览阅读264次。(1) Abstraction (抽象)(2) Polymorphism (多态)(3) Inheritance (继承)(4) Encapsulation (封装)_"object(cnofd[\"ofdrender\"])十条"

修改node_modules源码，并保存，使用patch-package打补丁，git提交代码后，所有人可以用到修改后的_修改 node_modules-程序员宅基地

文章浏览阅读133次。删除node_modules，重新npm install看是否成功。在 package.json 文件中的 scripts 中加入。修改你的第三方库的bug等。然后目录会多出一个目录文件。_修改 node_modules

【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure-程序员宅基地

文章浏览阅读883次。【代码】【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure

整理5个优秀的微信小程序开源项目_微信小程序开源模板-程序员宅基地

文章浏览阅读1w次，点赞13次，收藏97次。整理5个优秀的微信小程序开源项目。收集了微信小程序开发过程中会使用到的资料、问题以及第三方组件库。_微信小程序开源模板

随便推点

Centos7最简搭建NFS服务器_centos7 搭建nfs server-程序员宅基地

文章浏览阅读128次。Centos7最简搭建NFS服务器_centos7 搭建nfs server

Springboot整合Mybatis-Plus使用总结(mybatis 坑补充)_mybaitis-plus ruledataobjectattributemapper' and '-程序员宅基地

文章浏览阅读1.2k次，点赞2次，收藏3次。前言mybatis在持久层框架中还是比较火的，一般项目都是基于ssm。虽然mybatis可以直接在xml中通过SQL语句操作数据库，很是灵活。但正其操作都要通过SQL语句进行，就必须写大量的xml文件，很是麻烦。mybatis-plus就很好的解决了这个问题。..._mybaitis-plus ruledataobjectattributemapper' and 'com.picc.rule.management.d

EECE 1080C / Programming for ECESummer 2022 Laboratory 4: Global Functions Practice_eece1080c-程序员宅基地

文章浏览阅读325次。EECE 1080C / Programming for ECESummer 2022Laboratory 4: Global Functions PracticePlagiarism will not be tolerated:Topics covered:function creation and call statements (emphasis on global functions)Objective:To practice program development b_eece1080c

洛谷p4777 【模板】扩展中国剩余定理-程序员宅基地

文章浏览阅读53次。被同机房早就1年前就学过的东西我现在才学，wtcl。设要求的数为\(x\)。设当前处理到第\(k\)个同余式，设\(M = LCM ^ {k - 1} _ {i - 1}\) ，前\(k - 1\)个的通解就是\(x + i * M\)。那么其实第\(k\)个来说，其实就是求一个\(y\)使得\(x + y * M ≡ a_k(mod b_k)\)转化一下就是\(y * M ...

android 退出应用没有走ondestory方法,[Android基础论]为何Activity退出之后，系统没有调用onDestroy方法？...-程序员宅基地

文章浏览阅读1.3k次。首先，问题是如何出现的？晚上复查代码，发现一个activity没有调用自己的ondestroy方法我表示非常的费解，于是我检查了下代码。发现再finish代码之后接了如下代码finish();System.exit(0);//这就是罪魁祸首为什么这样写会出现问题System.exit(0);////看一下函数的原型public static void exit (int code)//Added ..._android 手动杀死app,activity不执行ondestroy

SylixOS快问快答_select函数 导致堆栈溢出 sylixos-程序员宅基地

文章浏览阅读894次。Q: SylixOS 版权是什么形式, 是否分为<开发版税>和<运行时版税>.A: SylixOS 是开源并免费的操作系统, 支持 BSD/GPL 协议(GPL 版本暂未确定). 没有任何的运行时版税. 您可以用她来做任何 您喜欢做的项目. 也可以修改 SylixOS 的源代码, 不需要支付任何费用. 当然笔者希望您可以将使用 SylixOS 开发的项目 (不需要开源)或对 SylixOS 源码的修改及时告知笔者.需要指出: SylixOS 本身仅是笔者用来提升自己水平而开发的_select函数 导致堆栈溢出 sylixos

推荐文章

热门文章

相关标签