C语言递归：汉诺塔问题分析

2024-07-30 22:08:08

问题背景

汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：

每次只能移动柱子最顶端的一个圆盘；每个柱子上，小圆盘永远要位于大圆盘之上；

游戏体验

汉诺塔移动次数规律

个数	移动次数f(n)	规律
1	1	2^1-1
2	3	2^2-1
3	7	2^3-164-1
4	15	2
...	...	...
n	2^n-1	2^n-1

由上述分析可以得到f(n)与f(n-1)的关系:

所以：f(n)=2^n-1 ; f(n-1)=2^(n-1)-1

f(n)=2^n-1=2^1*(2^(n-1)-1)+1=2*f(n-1)+1

移动过程的深层解读

汉诺塔问题的三步过程归纳

（我们是把n-1个圆盘看成一个整体去分析的）

一.把n-1个圆盘从A（经过C）移到B

二. 把A上第n个圆盘移到C

三: 把B上的（n-1）个圆盘（经过A）移到C

重点！！！！

中间的一步是把最大的一个盘子由A移到C上去；A->C
（1）中间一步之前可以看成把A上n-1个盘子通过借助C塔移到了B上，A->B
（2）中间一步之后可以看成把B上n-1个盘子通过借助A塔移到了C上；B->C

图解：

阶数	步骤
1	A->C
2	A->B，A->C，B->C
3	A->C，A->B，C->B，A->C，B->A，B->C，A->C
4	A->B，A->C，B->C，A->B，C->A，C->B，A->B，A->C，B->C，B->A，C->A，B->C，A->B，A->C，B->C
...	...
奇数	第一步A->C
偶数	第一步A->B

发现：

奇数个圆盘第一步永远为A–>C

偶数个圆盘第一步永远为A–>B

代码实现1

仅打印移动次数

#include<stdio.h>
int Tower(int num)
{
if(num==1)
return 1;
else
return 2*Tower(num-1)+1;
}
int main()
{
int num=0;
int ret=0;
printf("请输入层数：");
scanf("%d",&num);
ret=Tower(num);
printf("需要%d次完成\n",ret);
return 0;
}

关键步骤

if(num==1)
return 1;
else
return 2*Tower(num-1)+1;

代码实现2

打印移动的具体过程

#include <stdio.h>
void Move(char A,char C)
{
printf("%c --> %c\n",A,C);
}
void tower(int a,char A,char B,char C)//汉诺塔函数实施主体,A为初始柱,B为经由柱,C为目的柱
{
if (a==1)
{
Move(A,C);
}
else
{
tower(a-1,A,C,B);//把n-1个圆盘从A（经过C）移到B
Move(A,C);
tower(a-1,B,A,C);//把B杆上的（n-1）个圆盘（经过A）移到C
}
}
int Tower(int num)
{
if (num==1)
return 1;
else
return 2*Tower(num-1)+1;
}
int main()
{
int a = 0;
int Num=0;
printf("请输入层数:");
scanf("%d",&a);
Num = Tower(a);
printf("%d层需要移动%d步\n", a, Num);
tower(a, 'A', 'B', 'C');//进入递归
return 0;
}

补充

进阶题：移动盘子的过程中只能够相邻柱间移动，结论：移动次数：f(n)=3^n-1

到此这篇关于C语言递归：汉诺塔问题分析的文章就介绍到这了,更多相关递归：汉诺塔问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

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

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

代码如下所示: 复制代码代码如下: // 递归实现字符串反转 char *reverse(char *str) { if( !str ) { return NULL; } int len = strlen(str); if( len > 1 ) { char ctemp =str[0]; str[0] = str[len-1]; str[len-1] = '/0';// 最后一
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语言中递归算法的深入解析

许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的<C语言程序设计>一书中就是从阶乘的计算开始的函数递归.导致读过这本经书的同学们,看到阶乘计算第一个想法就是递归.但是在阶乘的计算里,递归并没有提供任何优越之处.在菲波那契数列中,它的效率更是低的非常恐怖. 这里有一个简单的程序,可用于说明递归.程序的目的是把一个整数从二进制形式转换为可打印的字符形式.例如:给出一个值4267,我们需要依次产生字符'4','2','6',和'7'.就如在printf函数中使用
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.C语言函数可以递归调用. 2.可以通过直接或间接两种方式调用.目前只讨论直接递归调用. 二.递归条件采用递归方法来解决问题,必须符合以下三个条件: 1.可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减. 说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用. 2
C语言程序中递归算法的使用实例教程

1.问题:计算n! 数学上的计算公式为: n!=n×(n-1)×(n-2)--2×1 使用递归的方式,可以定义为: 以递归的方式计算4! F(4)=4×F(3) 递归阶段 F(3)=3×F(2) F(2)=2×F(1) F(1)=1 终止条件 F(2)=(2)×(1) 回归阶段 F(3)=(3)×(2) F(4)=(4)×(6) 24 递归完成以递归方式实现阶乘函数的实现: int fact(int n) { if(n < 0) return 0; else if (n == 0 || n =
C语言递归：汉诺塔问题分析

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

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

hano.go package main import ( "bufio" "fmt" "os" "strconv" ) func main() { fmt.Print("输入要移动的盘子数:") reader := bufio.NewReader(os.Stdin) lool: data, _, _ := reader.ReadLine() n, err := strconv.Atoi(string(da
C语言递归之汉诺塔和青蛙跳台阶问题

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

目录 1.汉诺塔是如何实现的 2.汉诺塔问题画图详解 3.汉诺塔问题代码解释总结 1.汉诺塔是如何实现的下面是有三个盘子的示例: 从左到右一次是 A柱 B柱 C柱 A柱:起始位置 B柱:目标位置 C柱:过度位置汉诺塔为题即是,将A柱上的所有盘子移动到B柱上,且每次只能移动一个盘子,并且小盘子必须在大盘子上面 2.汉诺塔问题画图详解下面的例子是以A柱为起始位置,B柱为中间位置,C柱为目标位置的如果初始状态下:A柱只有一个盘子:A->C A柱有两个盘子:A->B A->C B-&g
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->
Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

本文实例讲述了Java基于栈方式解决汉诺塔问题.分享给大家供大家参考,具体如下: /** * 栈方式非递归汉诺塔 * @author zy * */ public class StackHanoi { /** * @param args */ public static void main(String[] args) { System.out.println("我们测试结果:"); System.out.println("递归方式:"); hanoiNormal(
手把手带你用java搞定汉诺塔

目录什么是汉诺塔问题剖析 n=1 n=2 n=3 小结 Java代码实现代码讲解 move函数 hanoiTower函数附:C语言实现汉诺塔总结什么是汉诺塔汉诺塔问题是一个经典的问题.汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说. 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移