带你理解C语言中的汉诺塔公式

2024-10-02 17:31:12

汉诺塔公式

汉诺塔问题在数学层面的公式：

不用说，你看到这个公式一定一脸懵逼，我现在来讲解这个公式的作用。

先来回想一下大象放冰箱要几步，三步吧，打开冰箱，放进去，关上门就行了，我们先不要去思考一些细碎的步骤，将一个复杂的问题先简单化，再慢慢去分析。

那汉诺塔问题也是同样的简单三步：（假设有n个盘子）

一、把最大的盘子留在A柱，然后将其他的盘子全放在B柱。

二、把最大的盘子放到C柱。

三、然后将B柱上的所有盘子放到C柱。

这就是汉诺塔的流程，汉诺塔的精髓就是上面三句话。

n层汉诺塔有（2^n-1）次移动，来将盘子全部从A盘到C盘.

C语言递归公式

相应我们可以写出对应的C语言递归公式：（n就是盘子的个数，xyz就是柱子的名字）

相信你肯定有很多疑问，我们现在先来举几个例子再解释问题吧。

一个盘子就不说了，因为最大的盘子就是他，所以他直接就去C盘了。

两层汉诺塔

共三步：把最大盘上面的全部放到B，然后最大盘去C，再把剩余的盘全部放到C就行了。

这是两个盘，共移动三次就移动完了，那三个盘呢？

三层汉诺塔

把全部过程堪称一个整体，最大盘上面的所有盘全部看成一个整体，我们也只用执行三个步骤，我们要利用把大事化小的观点，不要一上来就思考具体是怎么移动的，这样看不清问题的本质。

我们再来具体分析三步具体要怎么移动.

第一步中，我们要移动三次，分别是A->C、是A->B、C->B这就是一大次完整的移动，在这一步中，我们套用了上一次的汉诺塔公式进行使用，这就是汉诺塔的难点，接下来我给大家看个图，希望大家能理解，（n是层数，X,Y,Z则是函数参数)

汉诺塔的内部其实就像一个金字塔一样，其实每一次调用自己，就是按照上面所说精髓的公式调用自己，让自己的参数发生了变化。我希望大家能够自己去照着画一下流程，

第二步：将A到C，这就是将上图的第二步那写上第四次移动：A->C。

第三步，将B柱上的全部盘子借助A放到C

第七步完成后就会发现没有要执行的语句了，汉诺塔函数就结束返回到main函数了，自此求解汉诺塔函数的步骤就完成了。

好的，这样，我们移动三层汉诺塔的过程的就完成了，三次汉诺塔完成就算是解决了这个问题，因为即使盘子再多也就是一样的公式套用而已，明白两层和三层汉诺塔的运行原理就可以了，再多层的塔也是相同的流程。不难发现，递归就是让数学公式在C语言中体现了出来，让问题变的十分”简单“。

剩下就是了程序的主函数部分了，这个问题的主函数就很简单，主函数只用传来盘子的数量和三个柱子的名字就行了；代码如下

#include <stdio.h>
void change (char x,char y)     //打印盘子移动轨迹的函数
{
    printf("%c->%c\n", x, y);
}
void f(n, x, y, z)              //汉诺塔函数
{
    if (n == 1)
    {
        change(x, z);
    }
    else
    {
        f(n - 1, x, z, y);      //公式一：将A柱最大盘外的盘子借助C柱移到B柱
            change(x, z);       //公式二：将A上最大盘移动到C柱
        f(n - 1, y, x, z);      //公式三：将B柱上的盘借助A全部放到C柱
    }
}
int main()
{
    int m;
    scanf("%d", &m);
    f(m, 'A', 'B', 'C');
}

总结

到此这篇关于带你理解C语言中的汉诺塔公式的文章就介绍到这了,更多相关C语言汉诺塔公式内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言编写汉诺塔游戏

目录汉诺塔的游戏规则: 当A只有一个环的时候: 当A只有两个环的时候: 当A只有三个环的时候: 思路: 当n=1时: 当n=2时: 当n=3时: 当n=4时: 见代码运行截图总结汉诺塔的游戏规则: 有三根金刚石柱子A.B.C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环.大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环. 即将A柱子上全部的环通过C柱子(C柱子作为中介)移动到B柱子
C语言实现汉诺塔(图文详解)

目录思路: 当n=1时: 当n=2时: 当n=3时: 当n=4时: 见代码运行截图总结汉诺塔的游戏规则: 有三根金刚石柱子A.B.C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环.大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环. 即将A柱子上全部的环通过中间柱子B(B柱子作为中介)移动到C柱子上当A只有一个环的时候: A->C 当A只有两个环的时候: A->B A->C
C语言汉诺塔的简单了解

汉诺塔详解以4层为例以下为我的拙见,还希望大佬雅正要把汉诺塔移动到c 需要把1,2,3层移到b 把4移动到c 在吧123移动到b 但是一次只能动一块所以我们目前要做的就是把上面三块移动到b 那就需要把1 2移动到c 由此我们可以推出要把1,2移动到c,只需要把1移动到b 这里我们发现有很多重复的自相似动作我们就可以设计递归递归需要1,递归体 2 出口. 递归体移动n-1个盘子和1个盘子和n个盘子过程都是相似的但是每次放入的杆子不一样. 出口 n=1时只剩一个盘子,直接移动到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
C语言递归之汉诺塔和青蛙跳台阶问题

递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题.汉诺塔问题等,在研究递归问题时我们要注意三点: 1.递归的结束条件 2.递归在每次进行过程中,都得离条件越来越近 3.相邻两次递归调用之间的关联关系汉诺塔问题: 有三根杆子A, B, C.A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆: 1.每次只能移动一个圆盘: 2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆,
c语言汉诺塔算法代码

复制代码代码如下: #include<stdio.h> void move(char a,char b) { printf("%c->%c\n",a,b); } void han(int n,char a,char b,char c) { if(n>0) { han(n-1,a,c,b); move(a,b); han(n-1,c,b,a); } } int main() {
C语言编程递归算法实现汉诺塔

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

目录汉诺塔公式汉诺塔问题在数学层面的公式: C语言递归公式两层汉诺塔三层汉诺塔总结汉诺塔公式汉诺塔问题在数学层面的公式: 不用说,你看到这个公式一定一脸懵逼,我现在来讲解这个公式的作用. 先来回想一下大象放冰箱要几步,三步吧,打开冰箱,放进去,关上门就行了,我们先不要去思考一些细碎的步骤,将一个复杂的问题先简单化,再慢慢去分析. 那汉诺塔问题也是同样的简单三步:(假设有n个盘子) 一.把最大的盘子留在A柱,然后将其他的盘子全放在B柱. 二.把最大的盘子放到C柱. 三.然后将B柱上的
C语言递归函数与汉诺塔问题简明理解

目录递归函数 Hanio(汉诺塔)问题递归函数直接或者间接调用函数本身.“自己调用自己” 什么情况下面可以使用递归呢? 解决一个问题时,解决思路化成与问题本身类似的问题时,“递归” 是不是所有的递归问题,C语言都能支持呢? 不是的 C语言能够解决的递归问题,必须要满足两个条件: (1) 问题本身一个递归问题. (2) 递归不能是无限递归适合那些递归到一定程度时,答案是显而易见的. 一定需要有一个“跳出无限递归的条件”. C语言是如何支持递归呢? int age(int n) //从425
C语言递归：汉诺塔问题分析

目录问题背景游戏体验汉诺塔移动次数规律移动过程的深层解读汉诺塔问题的三步过程归纳图解: 发现: 代码实现1 仅打印移动次数代码实现2 打印移动的具体过程补充问题背景汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱,其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘.梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上,移动过程中必须遵守以下规则: 每次只能移动柱子最顶端的一个圆盘:每个柱子上,小圆盘永远要位于大圆盘之上: 游戏
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柱子中
python实现汉诺塔递归算法经典案例

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

目录基本概念示例一:取整函数基本测试示例二:Fail()函数示例三:FailNow函数实例四:Log和Fetal函数基本概念上一节提到,代码完成的标准之一还包含了单元测试,这部分也是很多开发流程中不规范的地方.写过单元测试的开发人员应该理解,单元测试最核心的价值是为了证明:为什么我写的代码是正确的?也就是从逻辑角度帮你检查你的代码.但是另外一方面,如果从单元测试覆盖率角度来看,单元测试也是非常耗时的,几乎是三倍于你代码的开发时间,所以在很多迭代速度非常快的项目中,单元测试就几乎没人
一文带你了解Go语言中的指针和结构体

目录前言指针指针的定义获取和修改指针所指向变量的值结构体结构体定义结构体的创建方式小结前言前面的两篇文章对 Go 语言的基础语法和基本数据类型以及几个复合数据类型进行介绍,本文将对 Go 里面的指针和结构体进行介绍,也为后续文章做铺垫. 指针在 Go 语言中,指针可以简单理解是一个地址,指针类型是依托于某一个类型而存在的,例如 Go 里面的基本数据类型 int.float64.string 等,它们所对应的指针类型为 *int.*float64.*string等. 指针的定
深入理解 Go 语言中的 Context

Hi,大家好,我是明哥. 在自己学习 Golang 的这段时间里,我写了详细的学习笔记放在我的个人微信公众号 <Go编程时光>,对于 Go 语言,我也算是个初学者,因此写的东西应该会比较适合刚接触的同学,如果你也是刚学习 Go 语言,不防关注一下,一起学习,一起成长. 我的在线博客:http://golang.iswbm.com 我的 Github:github.com/iswbm/GolangCodingTime 1. 什么是 Context? 在 Go 1.7 版本之前,context 还