C语言编程递归算法实现汉诺塔

汉诺塔

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

这个传说挺有意思的，这个传说是说有64片金片。但我们要讨论是只有3片或4片金片。看看网图吧。

我们以三片开始讨论。而讨论题目开始先明白，这个柱子的位置并不影响移动，只是特定的柱子才是关键。
我们来看看如果只有一个金片，要移动多少次。

很明显，只要一次就够了。
再来看看两片金片。

由于要全移动到C柱

1：
a:A->B
2:
b:A->C
3;
a:B->C

三步就可以全移动过去。
或者想要移动b片要先移动a片，将空C柱留给b片，去考虑a片的移动。
再来看看三片的移动

再来根据上面的思路，要想移动c片，得先移动a和b两片，把C柱留给c片。
要先满足这个条件

且大不能在小上面。要先移成这个样子。

且，要满足这个样子得，先这样。

总结一下

第一步

第二步

第三步

这么看下来，跟先前我们探讨只移两片，就没什么区别了。
再将c片移动到C柱。

成了这个样子。再来看看，我文章开头说的，柱子的位置不是关键，位置是可以改变，只是要移动到特定的柱子。现在这样，像不像，我们先前去移动两个金片的步骤？

看清楚，这个样子，就是移动两个金片的步骤。再按上面的方法步骤，就行了。
我们来计算一下这写步骤

第一部分：
移动两个金片到B柱。
第二部分：
移动C片到C柱
第三部分：
在移动两个金片到C柱。

总结一下
就是移两个金片的步骤，移两次，再移一次最下面的金片。总共2*3+1==7次。

再来看看四个金片的步骤。

要想移动这四个金片，必需要将这最下面的金片移动

这样来看，分两部分。

一：
移动d片到C柱
二：
移动a.b.c这仨个金片到C柱。

与上面移三片类比，、

第 一目的

第 二目的

第三目的

可以分三部完成。可见三片移法要移两次。
就是2*7+1==15次。

依此类推

当移动N片金片时，要先考虑，
一–>移动这N-1片金片。
二–>再移第N片，
三–>再移动那N-1片到目的地。
可以分这三步。
柱子的位置对移动并没有上面影响。
看代码，这是计算次数的代码。

#include <stdio.h>
int hanoi(int n)
{
	if (n >= 2)
		return 2 * hanoi(n - 1) + 1;
	return 1;
}
int main(void)
{
	printf("Problem of Hanoi\n");
	printf("please input the number for problem:>\n");
	int n;
	scanf("%d", &n);
	printf("%d",hanoi(n));
	return 0;
}

这是编译步骤的代码

#include <stdio.h>
void move(char start,char end,int n)
{
	static int count = 0;
	count++;
	printf("NO.%d step,the %d moves from %c to %c\n", count, n, start, end);
}
void hanoi(int n,char pose1,char pose2,char pose3)
{
	if (n == 1)
		move(pose1, pose3, 1);//一个是特例，不存在中间位置
	else
	{
		hanoi(n - 1, pose1, pose3, pose2);//对应第一次移动N-1个金片
		move(pose1, pose3, n);//对应移动第N个金片
		hanoi(n - 1, pose2, pose1, pose3);//最后一次移动N-1个金片
	}
}
int main(void)
{
	char pose1 = 'A';//起始位置
	char pose2 = 'B';//中间位置
	char pose3 = 'C';//结束位置
	int n;
	scanf("%d", &n);
	hanoi(n, pose1, pose2, pose3);
	return 0;
}

使用递归时，要将其理解成一个功能模块，而不是一步一步去分析。使用它的功能，同时确定终止条件并接近这个条件。
运用递归写函数，可以”轻松“计算。
只为加深自己理解，含有学生气，勿笑。
如有问题，烦请指点一二。

以上就是C语言编程递归算法实现汉诺塔的详细内容，更多关于C语言递归算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言如何与ARM汇编语言混合编程示例详解

    C语言如何与ARM汇编语言混合编程示例详解

    目录 一.ARM汇编语言简介 二.C语言调用汇编语言 1.无参数调用 2.有参数调用 三.汇编语言调用C语言 四.总结 五.参考文献 主要使用软件:keiL μVision5 一.ARM汇编语言简介 什么是汇编语言?汇编语言是任何一种适用于电子计算机.微处理器或其他可编程器件的低级语言.虽然被称为"低级语言",但是并不是说汇编语言真的"低级".特定的汇编语言和特定的机器语言指令集是一一对应的,不同平台之间不可直接移植.汇编语言主要包括传送指令.逻辑运算.移位指令.位

  • C语言编程中常见的五种错误及对应解决方案

    目录 1. 未初始化的变量 2. 数组越界 3. 字符串溢出 4. 重复释放内存 5. 使用无效的文件指针 前言: C 语言有时名声不太好,因为它不像近期的编程语言(比如 Rust)那样具有内存安全性.但是通过额外的代码,一些最常见和严重的 C 语言错误是可以避免的. 即使是最好的程序员也无法完全避免错误.这些错误可能会引入安全漏洞.导致程序崩溃或产生意外操作,具体影响要取决于程序的运行逻辑. 下文讲解了可能影响应用程序的五个错误以及避免它们的方法: 1. 未初始化的变量 程序启动时,系统会为其

  • C语言编程之初识数组线性查找和二分查找

    C语言编程之初识数组线性查找和二分查找

    目录 线性查找 二分查找 先来了解一下什么是查找, 额,好吧,这没什么可了解的, 就是查找数组中的某个元素的位置或是否存在. 就这,没了.直接了解查找算法吧. 线性查找 线性查找与二分查找有些差别. 数组内元素可以是混乱无序的,即没有按顺序储存.这方法很简单,就是从首元素开始,依此向后查找,比较.仅此而已.运用循环,依次对比. 看代码吧. #include <stdio.h> int main(void) { int arr[] = { 5,4,6,8,7,9,10,2,3,1 }; int

  • C语言编程gcc如何生成静态库.a和动态库.so示例详解

    C语言编程gcc如何生成静态库.a和动态库.so示例详解

    目录 一.什么是静态库和动态库 二.gcc生成.a静态库和.so动态库 1.生成静态库(.a) 1.1编辑生成例子程序hello.h.hello.c和main.c 1.2将hello.c编译成.o文件 1.3由.o文件创建静态库 1.4在程序中使用静态库 1.5验证静态库的特点 2.生成动态库(.so) 2.1由.o文件创建动态库文件 2.2在程序中使用动态库 三.实例 1.实例1 1.1代码 1.2 静态库.a文件的生成与使用 1.3 动态库.so文件的生成与使用 2.实例2 2.1代码 2.

  • C语言编程之三个方法实现strlen函数

    C语言编程之三个方法实现strlen函数

    strlen()函数是来源于库函数<string.h> 是用于计算字符串的长度, 且字符串需要以'\0'结尾 strlen()会计算'\0'前的字符个数. 根据MSDN的描述 size_t strlen(const char* string); size_t==unsigned int; 返回-无符号整型. 现在提供三种方法实现strlen() 一.计数器法 我们是计算字符个数,可以设置一个变量,每找到一个字符,计数器就加一. int my_strlen(const char* arr)//计

  • C语言编程计算信噪比SNR理解学习

    C语言编程计算信噪比SNR理解学习

    目录 概念 计算方法 相关认知 Taprint中的信噪比 实例 概念 这里面的信号指的是来自设备外部需要通过这台设备进行处理的电子信号,噪声是指经过该设备后产生的原信号中并不存在的无规则的额外信号(或信息),并且该种信号并不随原信号的变化而变化. 计算方法 信噪比的计量单位是dB,其计算方法是10lg(Ps/Pn),其中Ps和Pn分别代表信号与噪声的有效功率,也可以换算成电压幅值的比率关系:20Lg(Vs/Vn),Vs和Vn分别代表信号和噪声电压的"有效值". 在音频放大器中,我们希望

  • PTA刷题C语言编程顺序颠倒输出实现

    PTA刷题C语言编程顺序颠倒输出实现

    目录 这道题,是我遇见对数组元素的掌握与使用较为灵活的题目. 下面代码是我刚接触C++,刚学完类的一系列知识,连入门都没过,对C++的强大还未有多大认知,还是极具C语言的风格. 我看过一篇用C++完成的比这个简单多了. C语言也可以用栈来完成,虽然我有栈的实现函数,但我不愿去搞,就这样吧,实现也是对自己知识点掌握的加深认知. #include <iostream> #include <cstring> int main(void) { int a = 0; char ch; cha

  • C语言编程之扫雷小游戏空白展开算法优化

    C语言编程之扫雷小游戏空白展开算法优化

    目录 写代码前,扫雷需要什么 进行主函数文件的代码 game文件以及函数步骤 在主函数文件中使用game函数 布值棋盘(雷盘和玩家棋盘) 打印棋盘函数 玩家排雷 计算雷数的函数 空白递归算法 写代码前,扫雷需要什么 1,游戏需要初始选择菜单 2,需要布置两个棋盘,一个布置雷,一个展示给玩家看 3,打印棋盘 4,玩家要输入选择的坐标,并且可以多次输入游戏坐标 5,每次输入后打印棋盘,同时判断是否继续还是输赢. 6,玩家每次输入坐标,都进行一次递归展开. 进行主函数文件的代码 void option

  • C语言编程之预处理过程与define及条件编译

    C语言编程之预处理过程与define及条件编译

    目录 名示常量#define 重定义常量 在#define中使用参数 预处理器粘合剂:##运算符 变参宏:- 和_ _ VAG_ARGS_ _ 宏与函数 预处理指令 #undef指令 从C预处理器的角度看已定义 条件编译 offsetof函数 这张图描述了从源文件到可执行文件的整体步骤 这张图展示了大体上步骤. 从代码到运行环境,编译器提供了翻译环境.在一个程序中,会存在多个文件 ,而每个源文件都会单独经过编译器处理. 预编译: 1,会将#include等头文件所包含的内容,库函数全部拷贝过来

  • C语言编程递归算法实现汉诺塔

    C语言编程递归算法实现汉诺塔

    汉诺塔 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔.庙宇和众生也都将同归于尽. 这个传说挺有意思的,这个传说

  • C语言递归思想实现汉诺塔详解

    C语言递归思想实现汉诺塔详解

    目录 1.递归思想简介 2.汉诺塔问题 3.汉诺塔递归的c语言实现 总结 1.递归思想简介 在c语言中,程序调用自身的编程技巧称为递归( recursion). 递归的定义看上去似乎很抽象,使用代码描述能够让人容易理解,下面是一个函数递归的例子. /* 递归求n的阶乘 */ int factorial(int n) //定义一个求阶乘的函数叫做factorial(),需要一个整形参数,返回一个整形值 { if (n <= 1) //递归结束的条件 { return 1; } else { ret

  • C#利用递归算法解决汉诺塔问题

    C#利用递归算法解决汉诺塔问题

    目录 一.什么是递归 二.汉诺塔问题 1.汉诺塔的故事 2.解决思路 3.怎么解决汉诺塔问题 4.具体代码实现 三.完整代码 一.什么是递归 方法调用自己的行为就是递归,递归必须要有终止条件,不然它会无限递归. 1.先来看一下一个递归的例子 此程序的Fact方法从大到小地一级一级地调用自己,直到参数为1,然后就开始返回一级一级的从小到大地累乘,然后就计算出number的阶乘了. static int Fact(int num) { if (num <= 1) { return num; } el

  • C++基于递归算法解决汉诺塔问题与树的遍历功能示例

    C++基于递归算法解决汉诺塔问题与树的遍历功能示例

    本文实例讲述了C++基于递归算法解决汉诺塔问题与树的遍历功能.分享给大家供大家参考,具体如下: 递归是把问题转化为规模缩小的同类问题,然后迭代调用函数(或过程)求得问题的解.递归函数就是直接或间接调用自身的函数. 递归两要素:递归关系和递归边界(终止条件),递归关系确定了迭代的层次结构,需要深入了解并分解问题:终止条件保证了程序的有穷性. 递归的应用有很多,常见的包括:阶乘运算.斐波那契数列.汉诺塔.数的遍历,还有大名鼎鼎的快排等等.理论上,递归问题都可以由多层循环来实现.递归的每次调用都会消耗

  • java基于递归算法实现汉诺塔问题实例

    本文实例讲述了java基于递归算法实现汉诺塔问题.分享给大家供大家参考,具体如下: package test; import java.util.List; import java.util.ArrayList; import java.util.Scanner; import sun.net.www.content.audio.x_aiff; /** * @author 年浩 * */ public class test { public static void move(char x,cha

  • C语言用递归函数实现汉诺塔

    C语言用递归函数实现汉诺塔

    目录 汉诺塔(Hanoi)是什么? 那么,C语言如何实现汉诺塔呢? 汉诺塔的基本思路是: 具体代码见下(注意点在代码下面): 总结 汉诺塔(Hanoi)是什么? 一个简单的汉诺塔就如上图所示,有三个放置点,放置物必须遵循上小下大的规则,依次将1中的放置物全部放置到3中.就比如该图中有4个放置物,若将A上的放置物全部移至C上,具体的步骤是:A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->

  • c语言循环加数组实现汉诺塔问题

    目录 简介 递归的汉诺塔解法(c语言) 循环实现汉诺塔问题(c语言) 简介 汉诺塔问题是学数据结构与算法的时候会遇到的问题,相信来看本文的读者应该都对汉诺塔问题有基本的了解,理论上所有的递归都可以改成循环,常规的做法是借助堆栈,但是我一想好像用循环加数组也可以实现,于是就有了本文,实现声明,本文最后出来的算法效率不高的,比直接用递归实现还要差很多,追求算法效率的同学就不用看这个了.题目:假设有3个柱子,分别为A.B.C,A柱子上有数量为n个的空心圆盘,从上到下序号分别为1...n,要求把A柱子中

  • C语言超详细讲解递归算法汉诺塔

    C语言超详细讲解递归算法汉诺塔

    目录 题目描述 画图分析 思路总结 代码实现 总结 题目描述 汉诺塔问题起源于一个传说 汉诺塔又被称为河内塔,传说,在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针. 印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔. 不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面. 僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而

  • C语言实现汉诺塔游戏

    C语言实现汉诺塔游戏

    操作就是:A B 号码A的塔顶一层放在号码B的塔顶.如1(空格) 3 回车. 话说有人能把我这C的代码添加到QT界面框架上去么?  代码写的不好 ,维护性不够,只能玩8层的,写完以后发现很难拓展,软件工程,设计模式有待提高.... 里面提示输入等级的装B用了,没有实现,大家随便输入个个位数就可以玩了. stackfunc.c #include"STACK.h" #include<stdio.h> extern ceng CENG[SIZE]; //数据入栈 void pus

  • python实现汉诺塔递归算法经典案例

    python实现汉诺塔递归算法经典案例

    学到递归的时候有个汉诺塔的练习,汉诺塔应该是学习计算机递归算法的经典入门案例了,所以本人觉得可以写篇博客来表达一下自己的见解.这markdown编辑器还不怎么会用,可能写的有点格式有点丑啦,各位看官多多见谅. 网上找了一张汉诺塔的图片,汉诺塔就是利用用中间的柱子把最左边的柱子上的圆盘依次从大到小叠上去,说白了就是c要跟原来的a一样 废话少说,先亮代码 def move(n, a, buffer, c): if(n == 1): print(a,"->",c) return mov

随机推荐