Java解决青蛙跳台阶问题流程

Java解决青蛙跳台阶问题流程

1.问题描述

一只青蛙一次可以跳上1阶台阶，也可以跳上2阶台阶，求该青蛙跳上一个n阶台阶总共有多少种跳法？

2.画图分析

3.问题讲解

一只青蛙，要么1次跳2个台阶，要么1次跳1个台阶。

假设3个台阶为例：如果1次跳1个台阶，那剩下几种跳法？我们来仔细地想一下：

跳了一个台阶之后，剩下的台阶就相当于3 -1个台阶剩下2个台阶，2个台阶的跳法如上图就是2种跳法。

如果一次跳2个台阶，剩下的台阶就相当于3 - 2个台阶剩下1个台阶，1个台阶的跳法如上图是1种跳法。那么加起来就是3种跳法。

所以说，你如果想知道n个台阶有多少种跳法，其实就是看n - 1个台阶有多少种跳法，加上n - 2个台阶有多少种跳法。

规律看懂后你就发现这其实就是一个变相的斐波那契数列，只不过这个数列的第一项是1，第二项是2.

4.代码设计思路

我们再来看一下斐波那契数列的写法：

唯一的不同就是斐波那契数列的前两个项都是1

而青蛙跳台的第一项为1，第二项为2

只要用递归的方法稍作改动就能求出我们青蛙跳台阶的问题

5.实现代码

public class TestDemo {

public static int frogJump(int n){

if(n == 1 || n == 2){ //当n为前2阶台阶的时候，n是几就是几

return n;

}else{

return frogJump(n-2)+frogJump(n-1);//求n阶台阶的几种跳法

}

}

public static void main(String[] args) {

System.out.println(frogJump(1));

System.out.println(frogJump(2));

System.out.println(frogJump(3));

System.out.println(frogJump(4));

}

}

打印结果：

6.代码升级

用递归的方式虽然可以求解青蛙跳台阶问题，但是这其中会进行大量重复的计算。如果求的数字过大，程序运算出结果花费的时间会非常的长，所以我们并不建议在面试出现这样的问题的时候用递归的方法求解。

这里给大家介绍一种更好的求解方式：循环(迭代）实现

画图fzeIsVhdY分析：

给大家解释一下上图：

开始f3 = 3，f2 = 2，f1 = 1，

我们先让f3 = f1 + f2，这么没问题吧，1+2=3

再来我们把f2的值赋给f1，此时f1就等于2，

再把f3的值赋给f2，此时f2的值就等于3

循环起来，那此时再求f3的值就是2+3=5，恰好就是我们4阶台阶的5种跳法。

代码实现：

第二种写法：循环(迭代）实现

public class TestDemo {

public static int frogJump2(int n){

if(n == 1 || n==2){

return n;

}

int f1 = 1;

int f2 = 2;

int f3 = 0;

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

f3 = f1+f2;

f1 http://= f2;

f2 = f3;

}

return f3;

}

public static void main(String[] args) {

System.out.println(frogJump2(1));

System.out.println(frogJump2(2));

System.out.println(frogJump2(3));

System.out.println(froghttp://Jump2(4));

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

System.out.println(frogJump2(45));

}

}

运行结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。