跳台阶

8.1 跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解题思路

对于本题,前提只有 一次 1阶或者2阶的跳法。

1. 如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
2. 假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
3. 由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
4. 然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
5. 可以发现最终得出的是一个斐波那契数列：

        | 1     (n==1)
   f(n) =  | 2     (n==2)
        | f(n-1)+f(n-2)     (n>=3)

代码实现

java 代码

    /**
     * 递归实现
     * @param n
     * @return
     */
    public int jumpFloor(int n) {
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else {
            return jumpFloor(n-1)+jumpFloor(n-2);
        }
    }

    /**
     * 迭代实现
     * @param n
     * @return
     */
    public int jumpFloorFor(int n) {
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else {
            int a = 1,b=2,c=0;
            for(int i=3;i<=n;i++){
                c = a+b;
                a = b;
                b = c;
            }
            return c;
        }
    }

    public static void main(String[] args){
        System.out.println(jumpFloor(8));
        System.out.println(jumpFloorFor(8));
    }

Kotlin 代码

     /**
     * 递归实现
     * @param n
     * @return
     */
    fun jumpFloor(n: Int): Int {
        return when (n) {
            1 -> {
                1
            }
            2 -> {
                2
            }
            else -> {
                jumpFloor(n - 1) + jumpFloor(n - 2)
            }
        }
    }

    /**
     * 迭代实现
     * @param n
     * @return
     */
    fun jumpFloorFor(n: Int): Int {
        return when (n) {
            1 -> {
                1
            }
            2 -> {
                2
            }
            else -> {
                var a = 1
                var b = 2
                var c = 0
                for (i in 3..n) {
                    c = a + b
                    a = b
                    b = c
                }
                c
            }
        }
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        println(jumpFloor(8))
        println(jumpFloorFor(8))
    }

引用声明

该题目引用自
牛客网