快捷導(dǎo)航

Java解決青蛙跳臺(tái)階問(wèn)題流程

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

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

1.問(wèn)題描述

一只青蛙一次可以跳上1階臺(tái)階，也可以跳上2階臺(tái)階，求該青蛙跳上一個(gè)n階臺(tái)階總共有多少種跳法？

2.畫(huà)圖分析?

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

3.問(wèn)題講解?

一只青蛙，要么1次跳2個(gè)臺(tái)階，要么1次跳1個(gè)臺(tái)階。

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

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

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

所以說(shuō)，你如果想知道n個(gè)臺(tái)階有多少種跳法，其實(shí)就是看n - 1個(gè)臺(tái)階有多少種跳法，加上n - 2個(gè)臺(tái)階有多少種跳法。

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

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

我們?cè)賮?lái)看一下斐波那契數(shù)列的寫(xiě)法：

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

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

而青蛙跳臺(tái)的第一項(xiàng)為1，第二項(xiàng)為2

只要用遞歸的方法稍作改動(dòng)就能求出我們青蛙跳臺(tái)階的問(wèn)題

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

public class TestDemo {
    public static int frogJump(int n){
        if(n == 1 || n == 2){   //當(dāng)n為前2階臺(tái)階的時(shí)候，n是幾就是幾
            return n;
        }else{
            return frogJump(n-2)+frogJump(n-1);//求n階臺(tái)階的幾種跳法
        }
    }
 
 
    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.代碼升級(jí)

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

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

畫(huà)圖分析：

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

給大家解釋一下上圖：?

開(kāi)始f3 = 3，f2 = 2，f1 = 1，

我們先讓f3 = f1 + f2，這么沒(méi)問(wèn)題吧，1+2=3

再來(lái)我們把f2的值賦給f1，此時(shí)f1就等于2，

再把f3的值賦給f2，此時(shí)f2的值就等于3

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

代碼實(shí)現(xiàn)：

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

運(yùn)行結(jié)果：

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