2019-08-04-青蛙跳台阶问题

问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？

分析

• 如果只有一个台阶，那显然只有一种跳法
• 俩阶的话，有俩种
• 三阶的话就是1+2种
• 依次类推，我们发现当次的跳法，是前俩次的和

这不就是斐波那契数列吗，上面问题的解就是斐波那契数列第n个位置的值

1，斐波那契数列

/**
 * 青蛙跳台阶，一次跳一个或者俩个台阶，共有多少种跳法
 * @param idx
 * @return
 */
public static int fibonacci(int idx) {
    if(idx == 1) {
        return 1;
    } else if(idx == 2) {
        return 2;
    }
    //return sum(idx - 1) + sum(idx - 2);
    int one = 1;
    int two = 2;
    int sum = 0;
    for (int i = 2; i < idx; i++) {
        sum = one + two;
        one = two;
        two = sum;
    }
    return sum;
}

2，构建一个完整的斐波那契数列

private static int[] getFbArray(int n) {
    int[] result = new int[n];
    for (int i = 1; i < n; i++) {
        result[i] = fibonacci(i);
    }
    return result;
}

3, 求斐波那契数列的和

private static int sumFb(int n) {
    int result = 0;
    for (int i = 1; i < n; i++) {
        result += fibonacci(i);
        System.out.println("n = [" + result + "]");
    }
    return result;
}

4，求斐波那契数列中俩个元素之间的数值的和

/**
 * 求斐波那契数列数组中start到end之间的数字的和
 * @param start
 * @param end
 * @return
 */
public static int diff(int start, int end) {
    int count = 0;
    for (int i = start; i < end; i++) {
        count += fibonacci(i);
    }
    return count;
}