C语言递归之汉诺塔和青蛙跳台阶问题

递归就是一个函数执行过程中调用自己，在c语言中有很多关于递归的经典问题，例如：斐波那契数列问题、汉诺塔问题等，在研究递归问题时我们要注意三点：
1.递归的结束条件
2.递归在每次进行过程中，都得离条件越来越近
3.相邻两次递归调用之间的关联关系

汉诺塔问题：

有三根杆子A, B, C。A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆：
1.每次只能移动一个圆盘；
2.大盘不能叠在小盘上面，可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆, 但都必须尊循上述两条规则。求移动的过程。

int step = 0; //设置全局变量step记录步数
void move(int i,char form,char to){
	printf("第%d步，将第%d个盘子从%c移动到%c\n", ++step,i,form, to);
}
void Hanio(int n,char a,char b,char c){
	if (n == 0)
	{
		return;
	}
	Hanio(n - 1,a,c,b); //第n-1个A柱上的盘子通过C柱移动到B柱
	move(n, a, c);  //将A柱上编号为n的盘子移动到C柱
	Hanio(n - 1, b, a, c); //再将B柱上的第n-1个盘子通过A柱移动到C柱
}
int main(){
	    int n;
		printf("请输入汉诺塔中有多少个圆盘：\n");
		scanf("%d", &n);
		Hanio(n, 'A', 'B', 'C'); //将n个圆盘从A柱通过B柱移动到C柱
		system("pause");
		return 0;
}

运行结果：

青蛙跳台阶问题：

一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
当n = 1，只有1中跳法；当n = 2时，有两种跳法；当n = 3 时，有3种跳法；当n = 4时，有5种跳法；当n = 5时，有8种跳法。可以总结为f(n)=f(n-1)+f(n-2)，本质上与斐波那契数列相同。

int Frog(int n){
	if (n <= 2 && n >= 0)
	{
		return n;
	}
	else if (n < 0)
	{
		printf("您的输入错误\n");
		return n;
	}else
	{
		return Frog(n - 1) + Frog(n - 2);
	}
}
int main(){
		int n;
		printf("请输入有几级台阶：\n");
		scanf("%d", &n);
		int result = Frog(n);
		if(n >= 0){
			printf("青蛙有%d种跳法\n", result);
		}
		system("pause");
		return 0;
}

运行结果

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

赞 (0)

相关推荐

  • C语言程序中递归算法的使用实例教程

    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语言实现汉诺塔游戏

    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语言 汉诺塔算法代码

    复制代码 代码如下: #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语言的递归思想,分享给大家供大家参考之用.具体方法如下: 通俗点来说,递归就是自己调用自己. 递归的难点一是理解递归的执行调用过程,二是设置一个合理的递归结束条件. 下面来看一段摘自书中的简单程序: #include <STDIO.H> long fact(int n); long rfact(int n); int main(void) { int num; printf("This program calculates factorials.\n"); p

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • C语言递归之汉诺塔和青蛙跳台阶问题

    C语言递归之汉诺塔和青蛙跳台阶问题

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

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

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

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

    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语言中的汉诺塔公式

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

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

  • C语言递归函数与汉诺塔问题简明理解

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

  • PHP递归实现汉诺塔问题的方法示例

    本文实例讲述了PHP递归实现汉诺塔问题的方法.分享给大家供大家参考,具体如下: 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘.简而言之,有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子B上,

  • Python递归实现汉诺塔算法示例

    本文实例讲述了Python递归实现汉诺塔算法.分享给大家供大家参考,具体如下: 最近面试题,面试官让我5分钟实现汉诺塔算法(已然忘记汉诺塔是啥). 痛定思痛,回来查了一下汉诺塔的题目和算法.题干与实现如下: A基座有64个盘子,大在下小在上,每次移动一个盘子,每次都需要大在下小在上,全部移动到B基座,C基座为辅助基座. # -*- coding:utf-8 -*- # 汉诺塔回溯递归实现 # 假设参数中初始杆为a,借助杆为c,阶段终止杆为b # 第一步,a状态借助b移动到c # 第二步,a移动到

  • java递归实现汉诺塔步骤介绍

    java递归实现汉诺塔步骤介绍

    汉诺塔的规则是:一共三根柱子,一根柱子从上到下套着有小到大的若干个圆盘,要将所有圆盘按照这个排放顺序移动到第三根柱子上,并且每次只能移动一个圆盘. 可以将整个过程分为三个步骤来看: 第一步:将除最大圆盘外的n-1个圆盘移动辅助柱子上 第二步:将最大的圆盘移动到目标柱子 第三步:将n-1个圆盘从辅助柱子移动到目标柱子 其中第一步又可以拆成一模一样的三步,可以看成一个n-1层的塔要移动到目标柱子,只不过目标柱子换了一个: 第三步也可以拆分成一模一样的三步: 多拆几次就会发现规律:第一步和第三步无论如

  • Java与C++分别用递归实现汉诺塔详解

    Java与C++分别用递归实现汉诺塔详解

    目录 1.汉诺塔介绍 2.解塔步骤 3.C++实现(递归结果及显示步骤) (1)递归结果 (2)显示步骤 4.Java实现(递归结果及显示步骤) (1)递归结果 (2)显示步骤 1.汉诺塔介绍 汉诺塔规则 1.有三根杆子A,B,C.A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上 经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片: 如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C 2.解塔步骤 圆盘:1

  • JavaSE递归求解汉诺塔问题的思路与方法

    JavaSE递归求解汉诺塔问题的思路与方法

    目录 1. 汉诺塔的介绍和玩法 2. 汉诺塔问题的思路 3. 用递归的代码实现 总结 1. 汉诺塔的介绍和玩法 汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具. 一共有3根柱子(A.B.C),A柱子由下到上放着由大到小的盘子,我们需要将A柱子上的盘子移到C柱子上,每次只能移动一个盘子,且在任意一次移动中,大盘子都必须处于小盘子下方. 2. 汉诺塔问题的思路 若A柱子上只有1个盘子,只需要移动1步:A->C 若A柱子上有2个盘子,需要移动3步:A->B,A-

随机推荐