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

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

汉诺塔问题

题述：

设有三根柱子分别时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)都是这个分支