Java解決青蛙跳臺階問題流程

更新時間：2022年03月15日 14:36:28 作者：K穩(wěn)重

所謂的青蛙跳臺階問題，就是指一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。本文將用Java解決這一問題，需要的可以參考一下

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個臺階。

假設(shè)3個臺階為例：如果1次跳1個臺階，那剩下幾種跳法？我們來仔細地想一下：

跳了一個臺階之后，剩下的臺階就相當(dāng)于3 -1個臺階剩下2個臺階，2個臺階的跳法如上圖就是2種跳法。

如果一次跳2個臺階，剩下的臺階就相當(dāng)于3 - 2個臺階剩下1個臺階，1個臺階的跳法如上圖是1種跳法。那么加起來就是3種跳法。

所以說，你如果想知道n個臺階有多少種跳法，其實就是看n - 1個臺階有多少種跳法，加上n - 2個臺階有多少種跳法。

規(guī)律看懂后你就發(fā)現(xiàn)這其實就是一個變相的斐波那契數(shù)列，只不過這個數(shù)列的第一項是1，第二項是2.

4.代碼設(shè)計思路

我們再來看一下斐波那契數(shù)列的寫法：

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

唯一的不同就是斐波那契數(shù)列的前兩個項都是1

而青蛙跳臺的第一項為1，第二項為2

只要用遞歸的方法稍作改動就能求出我們青蛙跳臺階的問題

5.實現(xiàn)代碼?

public class TestDemo {
    public static int frogJump(int n){
        if(n == 1 || n == 2){   //當(dāng)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));
 
    }
}

打印結(jié)果：

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

6.代碼升級

用遞歸的方式雖然可以求解青蛙跳臺階問題，但是這其中會進行大量重復(fù)的計算。如果求的數(shù)字過大，程序運算出結(jié)果花費的時間會非常的長，所以我們并不建議在面試出現(xiàn)這樣的問題的時候用遞歸的方法求解。

這里給大家介紹一種更好的求解方式：循環(huán)(迭代）實現(xiàn)?

畫圖分析：

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

循環(huán)起來，那此時再求f3的值就是2+3=5，恰好就是我們4階臺階的5種跳法。

代碼實現(xiàn)：

第二種寫法：循環(huán)(迭代）實現(xiàn) 
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));
 
    }
}

運行結(jié)果：

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