青蛙跳臺階的相關問題

青蛙跳臺階的相關問題

問題一：青蛙一次只能跳 1 個臺階或者 2 個臺階, 計算從 0 臺階跳到 n 臺階有多少跳法，也就是的路徑種類總和，

import java.util.HashMap;

public class StepJump {
    // 當青蛙只能跳 1 個臺階或者 2 個臺階, 計算從 0 臺階跳到 n 臺階的路徑種類總和
    // 這個類似斐波那契數列 1 1 2 3 5 8 13
    // f(0)=1, f(1)=1, f(2)=f(0)+f(1),[其中f(0)表示從0階直接跳到2階] f(3)=f(1)+f(2)
    // f(3)=f(1)+f(2)的解釋：[先跳到1階的路徑種類(然后直接跳到3階)+先跳到2階的路徑種類(然后直接跳到3階)]
    private static int fun1(int n) {
        if(n < 2)
            return 1;
        // [先跳到n-1階的路徑種類(然后直接跳到n階)+先跳到n-2階的路徑種類(然后直接跳到n階)]
        return fun1(n-1)+fun1(n-2); // 遞回
    }
    // 避免重復計算，可用一個 HashMap 存盤計算過的值，防止重復計算，
    private static int fun2(int n, HashMap<Integer, Integer> map) {
        if(n < 2)
            return 1;
        // 如果map包含 n 對應的值，直接回傳
        if(map.containsKey(n))
            return map.get(n);
        // 遞回求值,和fun1()同樣道理
        int first = fun2(n-1, map);
        int second = fun2(n-2, map);
        int sum = first + second;
        // 儲存值，方便下次尋找
        map.put(n, sum);
        return sum;
    }
    // 利用回圈計算，效率更高
    private static int fun3(int n) {
        if(n < 2)
            return 1;
        int first = 1, second = 2, sum = 0;
        while(n-- > 2) {
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }
    public static void main(String[] args) {
        int  n = 40;
        long time = System.nanoTime();
        System.out.println(fun1(n));
        System.out.println("遞回時間：" + (System.nanoTime() - time));
        time = System.nanoTime();
        System.out.println(fun2(n, new HashMap<Integer, Integer>()));
        System.out.println("HashMap時間：" + (System.nanoTime() - time));
        time = System.nanoTime();
        System.out.println(fun3(n));
        System.out.println("回圈時間：" + (System.nanoTime() - time));
    }
}
/* Code Running Results:(每次結果可能不同)
 * 165580141
 * 遞回時間：347549100
 * 165580141
 * HashMap時間：114000
 * 165580141
 * 回圈時間：21000
 */

問題二：青蛙一次能跳 1 到 n 個臺階, 計算從 0 臺階跳到 n 臺階有多少跳法，也就是的路徑種類總和，

public class StepJumpTwo {
    // 青蛙一次能跳 1 到 n 個臺階, 計算從 0 臺階跳到 n 臺階的路徑種類總和
    // f(n)  = f(n-1)+f(n-2)+......+f(1)+f(0)------a式子
    // f(n-1)= f(n-2)+f(n-3)+......+f(1)+f(0)------b式子
    // (a式子)-(b式子)得  f(n)-f(n-1)=f(n-1)
    // 最終得到 f(n)=2*f(n-1)的等比數列，該等比數列為2^(n-1)
    private static int fun(int n){
        if(n < 2)
            return 1;
        return 1<<(n-1);  // 位運算，速度更快
    }
    public static void main(String [] args){
        System.out.println(fun(10));
    }
}
/* Code Running Results:
 * 512
 */

問題三：青蛙一次能跳 1 到 m 個臺階, 計算從 0 臺階跳到 n 臺階有多少跳法，也就是的路徑種類總和，

public class StepJumpThree {
    // 青蛙一次能跳 1 到 m 個臺階, 計算從 0 臺階跳到 n 臺階的路徑種類總和

    // 情況1 n <= m 時，也就回到了問題二 f(n)=2*f(n-1), 等比數列為2^(n-1)

    // 情況2 當 n-1 = m 時
    // f(n)  = f(n-1)+f(n-2)+......+f(2)+f(1) 接下所有的計算又回到情況1
    //       = 2*f(n-2)+2*f(n-3)+......+2*f(1)+f(1)
    //       = ......
    //       = 2^(n-1)-1 (f(n)=2*f(n-1)的等比數列[2^(n-1)]的前 n-1 項和[2^(n-1)-1]

    // 情況3 當 n-1 > m 時
    // f(n)  = f(n-1)+f(n-2)+......+f(n-m+1)+f(n-m)------a式子
    // f(n-1)= f(n-2)+f(n-3)+......+f(n-m)+f(n-1-m)------b式子
    // (a式子)-(b式子)得  f(n)-f(n-1)=f(n-1)-f(n-1-m)
    // 最終得到 f(n)=2*f(n-1)-f(n-1-m)

    private static int fun(int n, int m){
       if(n < 2)
           return 1;
       if(n <= m)     // 情況1
           return 1<<(n-1);
       if(n-1 == m)   // 情況2
           return (1<<(n-1))-1;
        // 情況3
       return 2*fun(n-1, m)+fun(n-1-m, m);
    }
    public static void main(String [] args){
        System.out.println(fun(1, 5));  // n < 2
        System.out.println(fun(4, 5));  // 情況1
        System.out.println(fun(6, 5));  // 情況2
        System.out.println(fun(7, 5));  // 情況3
    }
}
/* Code Running Results:
 * 1
 * 8
 * 31
 * 63
 */