C++实现汉诺塔问题(递归实例)

这篇具有很好参考价值的文章主要介绍了C++实现汉诺塔问题(递归实例)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

汉诺塔的由来

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

汉诺塔的规则:

1、有三根相邻的柱子,标号为A,B,C。

2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。

3、现在把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。

算法过程原理:

  • n个盘子时:
    • 把n-1个圆盘从A经过C移到B上
    • 把第n个圆盘从A移到C上
    • 把n-1个小圆盘经过A从B移到C上                

c++汉诺塔,c++,数据结构,算法,学习

图片来自:汉诺塔三层图解,汉诺塔6层步骤,汉诺塔图片_大山谷图库 (dashangu.com)http://www.dashangu.com/postimg_17430370.html 

 算法实现:

#include<iostream>
using namespace std;
//汉诺塔问题 
int sum;//设置常变量  总共需要走的步数sum 
void hanoi(int n,char x,char y,char z){
	void move(char X,int N,char Y);
	if(n==1)
	move(x,1,z);//直接从x移到z上 
	else 
	{
		hanoi(n-1,x,z,y);// 把上面的n-1个圆盘,从A经过C移动到B
		move(x,n,z);// 把第n个圆盘从A移动到C
		hanoi(n-1,y,x,z);// 把那n-1块个圆盘,从B经过A移动到C
	}
}
void move(char X,int N,char Y){
	cout<<N<<"从"<<X<<"->"<<Y<<endl;
	sum++;//每移动一次sum加一 
}
int main(){
	int n=0;
	char A,B,C;
	cout<<"请为n赋值:"; 
	cin>>n;
	hanoi(n,'A','B','C');//实参盘子数n 柱子A,B,C 
	cout<<"总共需要走的步数为:"<<sum<<endl; 
	return 0;
}

 当圆盘数为3时的结果: 

c++汉诺塔,c++,数据结构,算法,学习文章来源地址https://www.toymoban.com/news/detail-722565.html

到了这里,关于C++实现汉诺塔问题(递归实例)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C语言】函数递归:汉诺塔问题

    汉诺塔问题是一道经典的计算机科学中的递归算法题,通过解决汉诺塔问题以更好的理解递归。 函数递归:函数自己调用自己。 函数递归的两个必要条件: 1.函数自身的调用要有限制条件,如果没有限制条件,就会无限的自己调用自己而导致栈溢出(stack overflow)(关于栈溢

    2024年02月03日
    浏览(37)
  • 递归——汉诺塔问题(结合代码理解,终于懂了)

    问题 汉诺塔问题是一个经典的递归问题,汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子, 在一根柱子上从下往上按照大小顺序摞着 64 片圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一 根柱

    2024年02月04日
    浏览(40)
  • 递归详解,斐波那契数列、二叉树遍历、汉诺塔问题的递归代码

    一、递归详解 [1] 递归是一种编程技巧,通过函数调用自身来解决问题。递归中包含三个要素:递归定义、递归出口和递归调用。 [2] 递归定义指的是问题可以被分解为同类且更小规模的子问题。在递归过程中,问题会不断被分解为规模更小的子问题,直到达到一个基本情况,

    2024年02月08日
    浏览(38)
  • 数据结构——迷宫问题(顺序栈、C++)

     讲解: 一、采用二维数组和srand函数随机生成只有0和1的迷宫。 二、求解迷宫大概思路:先将入口处的坐标即方向d入栈,然后当栈不为空时,取出栈顶(即当前节点)的数据。遍历当前节点的四个方向,找到可行的下一个节点,并将其入栈;如没有可行的下一个节点,则将

    2024年02月13日
    浏览(33)
  • 汉诺塔——递归算法(c语言实现)

    每日一题   文章目录   汉诺塔 问题 : 一、递归算法 二、解决汉诺塔问题 1.找规律,确定思路 2.代码实现 总结          1.有三根杆(编号A、B、C)      2. 在A杆自下而上、由大到小按顺序放置n个金盘      3.把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。 操作规则

    2024年02月10日
    浏览(43)
  • C语言实现汉诺塔详细步骤(递归与非递归)及代码

    C语言汉诺塔问题是一个经典的问题,在学习编程的初学者中非常流行。它涉及到了递归的思想,能够帮助我们理解递归的基本原理。 首先,我们来了解一下汉诺塔的问题。汉诺塔问题是指:有三根柱子A,B,C,A柱子上有n个盘子,盘子大小不等,且从下到上由小到大排列,现在

    2023年04月08日
    浏览(38)
  • C# 使用递归方法实现汉诺塔步数计算

    举一个例子:计算从 1 到 x 的总和 有三个石柱,在最左侧的石柱上从小到大摆放 N 层盘片,需要从最左侧的石柱移动到最右侧的石柱上,中间的石柱作为缓冲,一次只能移动一个盘片,且无论何时较小的盘片始终在较大的盘片上面。 这个问题求解这过程中搬运的次数 创建一

    2024年02月11日
    浏览(47)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见:Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢,每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号,而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(61)
  • 数据结构——栈(C++实现)

    今天我们来看一个新的数据结构—— 栈 。 栈是一种基础且重要的数据结构,它在计算机科学和编程中扮演着核心角色。栈的名称源于现实生活中的概念,如一叠书或一摞盘子,新添加的物品总是放在顶部,而取出物品时也总是从顶部开始。这种后进先出(Last In, First Out, L

    2024年04月29日
    浏览(42)
  • 数据结构——队列(C++实现)

    目录 队列的概念及结构  队列的实现 队列的代码实现 完整的源文件代码 总结 推荐题目巩固知识 队列:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,队列最重要的特性是 先进先出 (First In First Out) 入队列:进行插入操作的一端称为 队尾 出队列

    2024年02月07日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包