递归算法之蜜蜂路线问题
2021/9/22 22:12:28
本文主要是介绍递归算法之蜜蜂路线问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、什么是递归
首先我们来介绍一下什么是递归,递归就是程序自己调用自己的过程。我们知道一个自定义函数可以调用其余的自定义方法,当这个函数调用其自己的时候即为递归。
二、如何解决递归算法
我们已经了解了什么是递归,那么自然而然的就会想到如何解,会有什么思路来解此类问题,在此我总结了三个步骤,如下:
1.当n = 1(或n = 2)时会出现哪些情况。
2.寻找第n项与第n - 1项存在的关系。(在此不明白没有关系,下面我会利用该题具体解释)。
3.寻找边界,即特殊情况。
三、蜜蜂路线问题
【问题描述】
一只蜜蜂在如下图所示的数字蜂房上爬动,已知他能从标号小的蜂房爬到标号大的相邻蜂房,问:蜜蜂从M开始爬到蜂房N,M<N,有多少种爬行路线?
1.假设初始M = 1,那么当N = 1时即边界情况,只有1种路线。从这里可以推出,当M 与 N相等时即都只有一种路线。
2.寻找第n个与第n - 1个之间的规律,我们可以发现,假设要到达第4个蜂房,那么蜜蜂可以从“3”号蜂房和“2”号蜂房到达,存在两条路线。假设要到达第5个蜂房,那么蜜蜂可以从“3”号蜂房和“4”号蜂房到达。总结如下图:
可以发现,每一个蜂房都与前一个存在两条路径,即存在关系为:
f(n) = f(n - 1) + f(n - 2)
使用C语言编译运行:
#include<stdio.h> int HowRoad(int m,int n){ if(n - m == 1 || m == n) return 1; return HowRoad(m,n - 1) + HowRoad(m,n - 2); } int main(){ int m,n; scanf("%d %d",&m,&n); printf("从蜂房%d到蜂房%d,一共有%d种路线\n",m,n,HowRoad(m,n)); return 0; }
运行效果:
使用Java语言编译运行:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); System.out.println("从蜂房"+m+"到蜂房"+n+",一共有"+HowRoad(m,n)+"种路线"); } public static int HowRoad(int m,int n){ if(n - m == 1 || m == n){ return 1; }else{ return HowRoad(m,n - 1) + HowRoad(m,n - 2); } } }
运行效果:
至此,此题大致思路与解法已讲解完毕,如对您有帮助请留下宝贵一赞!如有问题可留言或私信。感谢您的浏览!
这篇关于递归算法之蜜蜂路线问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求