当前位置：首页 > article >正文

汉诺塔问题和青蛙跳台阶问题（c语言）

article 2024/10/22 18:38:06

这俩道题都是利用到了函数递归的思想，其中汉诺塔问题较难理解，青蛙跳台阶则较简单

汉诺塔问题

题述：

设有三根柱子分别时A,B,C，在A柱子上放着n个盘子，每个盘子大小不一样，从下往上盘子大小依次减小，要求将A柱子上的盘子移动到C柱，且不改变盘子顺序（由大往小排序）。

规则：

1.一次只能移动一个盘子

2.盘子可以放在任意一个柱子上

3.盘子由大到小排序

图解：当n=2时，

移动顺序：A->B,A->C,B->C

当n=3时

A->C,A->B,C->B,A->C,B->A,B->C,A->C

思路：可以用函数递归来解决汉诺塔问题

代码插入

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void move(char pos1, char pos2)
{
	printf(" %c->%c ", pos1, pos2);

}
//n是汉诺塔的层数
//pos1起始位置
//pos2中转位置
//pos3目的位置

void Hanoi(int n,char pos1,char pos2,char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);
		//这个move(pos1,pos3)对应的Hanoi中的pos1，pos3
	}
	else
	{
		//将n-1杆子上的东西从A经过中转杆C移动到B上
		Hanoi(n - 1, pos1, pos3,pos2);
		//将A上的东西移动到C上
		move(pos1, pos3);
		//将B杆子上的东西通过中转杆A移动到C上。
		Hanoi(n - 1, pos2, pos1, pos3);
	}

}

int main()
{
	/*Hanoi(2, 'A', 'B', 'C');
	printf("\n");
	Hanoi(2, 'A', 'B', 'C');
	printf("\n");*/
	Hanoi(3, 'A', 'B', 'C');
	printf("\n");
	return 0;

}

函数递归图

n==2时的

注意：

上面的，Hanoi(1,A,C,B)和Hanoi(1,B,A，

C)都是这个分支👇

它是代码执行顺序执行的（仔细理解）

代码执行流程👇

先进入

然后进行函数调用

此时pos1=A,pos2=B,pos3=C

然后进入else内部

此时Hanoi(1,A,C,B)

然后这个函数进行函数调用，此时

Hanoi（1，A,B,C）,此时n==1，进入if语句里头

所以move（A->B）

这个函数Hanoi(1,A,C,B)用完后，往下进行

然后move（A->B）

然后进入到

上面的代码执行完，并没有改变n的值，所以n依旧==2

此时Hanoi(1,B,A,C)

n==1进入if语句中

然后move（B->C）.

然后程序结束

运行结果

n==3时，函数递归图

圈1代表着这个函数调用后的结果👇

中间的move到了这个代码行

圈2是这个函数调用后的结果👇

然后得到程序结果

青蛙跳台阶问题

题述：

有一只青蛙跳台阶，一次可以跳1次，也可以跳2次，问跳到了第n个台阶，可以有多少种跳法

思路：这道题与斐波那契求解差不多

n==1时，way==1

n==2时，way==2

n==3时，way==3

n==4时，way==5

此时即可找到规律，

当n>2时

f（n）=f（n-1）+f（n-2）

那么这道题就是一个典型的函数递归问题

int Way(n)
{
	if (n == 1 )
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	else
		return Way(n - 1) + Way(n - 2);
}

int main()
{

	int n = 0;
	scanf("%d", &n);
	int result = Way(n);
	printf("%d", result);

	return 0;
}

程序运行