青蛙跳石头java_青蛙跳台阶（JAVA）与递归问题探究

迷南。 2022-10-22 14:54 170阅读 0赞

青蛙跳台阶JAVA

一只青蛙一次可以跳上一层台阶，也可以跳上两层，求该青蛙跳上n层的台阶总共有多少种跳法(先后次序不同算不同的结果)。

思考：可以看出，每次青蛙出脚都会有两种可能,一步或者两步，再次出脚也是两种可能，一步或者两步，每次出脚就是一步或者两步，那么，何时青蛙不能出脚了，很显然，是台阶走完了，所以，青蛙跳台阶每种跳法都是1和2的各种组合；先来看看层数和方法数之间规律吧！(这里用到了类似信息论中码树的方法来分析，没听过也没关系，看图就行)

![c87e77edd5d8abe58565a8e0b8330658.png][]

递归法求解

递归

在用递归之前，先来谈谈对递归的认识吧，所谓递归，可以把它分解为递+归两个过程，现在假设小明坐在教室最后一排，他的衣服放在第一排，于是他给倒数第二排的人说帮他拿一下衣服，倒数第二排的人给倒数第三排的人说给他拿一下衣服…直到第二排的人给第一排的人说帮他拿一下衣服 ，这便是递；第一排的人将衣服递给第二排的人，第二排的人把衣服递给第三排的人…倒数第二排的人把衣服给倒数第一排的人。好了目的达到了，最后一排的人获得了他的衣服这便是归。最后一排的人只用去告诉他前面的人帮他取一下衣服，而更前面的人消息怎么传，最后一排的人就不用管了，就假设消息已经送到了。但是能保证最后一排的人能拿到衣服，就必须消息到达第一排的人时，第一排的人能够把衣服递给第二排的人。(当然，你可能会说，最后一排的人直接去第一排把衣服一取不就行了，哈哈，这里我们只是为了解决问题举出这个例子，不用去在意这些细节。)

这时会发现，其实每个人重复的动作都是一样的，都是把消息传达给坐在他前面的人，然后在衣服传达到他那里时，把衣服传给坐在他后面的人，那么问题不就简单了，把倒数第二排以前的人看做一个整体，倒数第一排的人只是让倒数第二排的人帮他拿一下衣服，这样一次递，最后将衣服归回来，OVER。

![05706775273fd2b8363c68fbdafb9c46.png][]

所以，这时我们可以定义一个方法，就是向前面的人发送帮忙取衣服的请求，当这排只有两个人时，那么前面的人就把衣服给后一个人，如果一排有十个人时，就只用向第九个人发送帮忙取衣服的请求，至于第九个人怎么取，其实也是用的相同的方法。

这就是递归，下面就用青蛙跳台阶来应用吧！

代码：

//青蛙跳台阶递归法

public static void main(String\[\] args) \{

System.out.println(jumpFloor(6));

public static int jumpFloor(int n)\{

int jumpNum=0;//方法总数

if(n==0)\{

return 0;

if (n==1)\{

return 1;

if (n==2)\{

return 2;

\}else \{

jumpNum=jumpFloor(n-1)+jumpFloor(n-2);

return jumpNum;

非递归法：

先看看图一中的方法数，是不是有种似曾相识的感觉，没错，类似于斐波那契数列(斐波那契数列为1、1、2、3、5、8、13、21、34……此数列从第3项开始，每一项都等于前两项之和，递推公式为F(n)=F(n-1)+F(n-2)，n≥3，F(1)=1，F(2)=1。)这里的方法数的分布为(1、 2 、3、 5、 8、 13…),从第三项开始，每一项都等于前两项的和。

分析过程：

![d509468cb4c9fcf2c4f220d7dcffa5b4.png][]

代码：

//青蛙跳台阶非递归法

public static void main(String\[\] args) \{

System.out.println(jump(5));

//一层台阶时有f1种方法

//两层台阶时有f2种方法

public static int jump(int n) \{

int num = 0;

int f1 = 1;

int f2 = 2;

if(n==0)\{

return 0;

if(n==1)\{

return 1;

\}if (n==2)\{

return 2;

for (int i = 3; i <= n; i++) \{

num = f1 + f2;

f1 = f2;

f2 = num;

return num;

[c87e77edd5d8abe58565a8e0b8330658.png]: /images/20221022/ee5e0619b6fe42268e864b0c1292e6a2.png
[05706775273fd2b8363c68fbdafb9c46.png]: /images/20221022/7aabcbb6fb71413d937f78560a2a7380.png
[d509468cb4c9fcf2c4f220d7dcffa5b4.png]: /images/20221022/cdb485e45f1e4fe09f67a51c208ee8a8.png