递归经典问题讲解

发布时间:2024年01月24日

小乐乐走台阶问题

题目链接

思路讲解

? ? ? ? 这里我们假设由n阶台阶,设函数F(n)为总共的走法,即有n台阶的时候我们有F(n)种走法,我们往上递推一下,如果我们上一步是走了一阶台阶的话,就会剩下n-1台阶,就有F(n-1)种走法;如果我们上一步是走了两阶台阶的话,就会剩下n-1台阶,就有F(n-2)种走法;这样我们就得到了F(n) = F(n-1) + F(n-2)
? ? ? ?我们继续递推验证一下,F(n-1)时,有n-1个台阶,上一步要么走了一步要么走了两步,即F(n-1)=F(n-2)+F(n-3); F(n-2)时,有n-2个台阶,要么走了一步要么两步,即F(n-2)=F(n-3)+F(n-4); 以此类推…
? ? ? ?接下来要思考递归停止条件,避免出现死递归现象,所以我们来考虑递归到最后,其实就会剩下一个台阶,对应一种走法,或者剩下两个台阶,就是一步一步或二步这两种走法,所以这就是递归结束条件,递推到最后F(3)=F(1)+F(2);之后进行回归操作。


代码示例

#include  <stdio.h>
  
int  sum(int  n)
{
 if(n==1)
 return  1;
 if(n==2)
 return  2;
 return  sum(n-1)+sum(n-2);
}
  
int  main()
{
 int n;
 scanf("%d",&n);
 int ret = sum(n);
 printf("%d",ret);
 return  0;
}

汉诺塔问题

汉诺塔问题是一个经典的递归问题,最初由法国数学家Edouard Lucas提出。问题描述如下:有三根柱子A、B、C,开始时柱子A上有n个盘子,盘子从上到下按照从小到大的顺序摆放。现在要将这n个盘子从柱子A移动到柱子C,期间可以借助柱子B,但要满足以下规则:

  1. 每次只能移动一个盘子;
  2. 大盘子不能放在小盘子上面。

问题如下:给定n个盘子,请问有怎么把这些盘子移动到大盘子里。
输入实例如下
input:1
output:A->C

input:2
output:A->B A->C B->C

input:3
output:A->C A->B C->B A->C B->A B->C A->C

在这里插入图片描述

思路讲解

? ? ? ?我们从最简单的下手,如果只有一个盘子的时候,我们直接将这个盘子从A移动到C
? ? ? ?如果有两个的时候,我们需要将最上面的小盘子放在B上,然后将A剩下的大盘子放在C中,将B上的盘子放在C中就可以了。
? ? ? ?如果视频看不到,出现数据不存在的情况,重新加载或刷新一下即可。

1月23日

? ? ? ?如果有三个盘子,我们就有需要将上面两个先放在B柱子上,这样A柱上最后一个盘子就可以放在C柱子上,B柱上的两个盘子便要借助A柱子依次移动到C柱上,大家可以看一下下面的移动视频:
? ? ? ?如果视频看不到,出现数据不存在的情况,重新加载或刷新一下即可。

1月23日(1)

? ? ? ?根据上面的推演,我们可以将汉诺塔问题抽象成1和n-1的问题,也就是说我们需要将除了A柱上最大的盘子之外,将上面的n-1个盘子先移动到B柱上,然后这一个最大的盘子就可以移动到C柱上,在B柱上最大的盘子不动,其上面的n-2个盘子需要移动到A盘上,最后将B柱上这个盘子移动到C盘上,以此类推…
大家可以看一下抽象出来的视频:
? ? ? ?如果视频看不到,出现数据不存在的情况,重新加载或刷新一下即可。

1月23日(2)

代码示例

#include <stdio.h>

void move(char p1, char p2)
{
	printf("%c->%c  ", p1, p2);
}

void HanNuoTa(int n,char p1,char p2,char p3)
{
	if (n == 1)
		printf("%c->%c ", p1, p3);
	else
	{
		HanNuoTa(n - 1, p1, p3, p2);
		move(p1, p3);
		HanNuoTa(n - 1, p2, p1, p3);
	}
}

int main()
{
	int n;
	while (scanf("%d", &n) != EOF)
	{
		HanNuoTa(n, 'A', 'B', 'C');
	}
	return 0;
}
文章来源:https://blog.csdn.net/liwuqianhzc/article/details/135791866
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。