亲宝软件园·资讯

展开

Java 青蛙跳台阶

K稳重 人气:0

1.问题描述

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

2.画图分析 

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

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.代码设计思路

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

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

唯一的不同就是斐波那契数列的前两个项都是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));
 
    }
}

打印结果:

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

6.代码升级

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

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

画图分析:

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

给大家解释一下上图: 

开始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 = 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(frogJump2(4));
        System.out.println(frogJump2(5));
        System.out.println(frogJump2(45));
 
    }
}

运行结果:

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAS-WqvuKAjQ==,size_20,color_FFFFFF,t_70,g_se,x_16

加载全部内容

相关教程
猜你喜欢
用户评论