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))
}

引用声明

该题目引用自
牛客网