青蛙跳台阶

1. 题目描述

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

2. 思路分析

跳到 n 阶假设有 f(n)种方法。

往前倒退，如果青蛙最后一次是跳了 2 阶，那么之前有 f(n-2)种跳法; 如果最后一次跳了 1 阶，那么之前有 f(n-1)种跳法。

所以：f(n) = f(n-1) + f(n-2)。就是斐波那契数列。

3. 代码

这里利用缓存模式（又称备忘录模式）实现了代码。

const fibonacci = (() => {
    let mem = new Map();
    mem.set(1, 1);
    mem.set(2, 1);

    const _fibonacci = (n) => {
        if (n <= 0) {
            throw new Error("Unvalid param");
        }

        if (mem.has(n)) {
            return mem.get(n);
        }

        mem.set(n, _fibonacci(n - 1) + _fibonacci(n - 2));
        return mem.get(n);
    };

    return _fibonacci;
})();

/**
 * 测试代码
 */

let start = new Date().getTime(),
    end = null;

fibonacci(8000);
end = new Date().getTime();
console.log(`耗时为${end - start}ms`);

start = end;
fibonacci(8000);
end = new Date().getTime();
console.log(`耗时为${end - start}ms`);

数值的整次方

1. 题目描述

题目：实现函数 double Power（double base, intexponent），求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题

2. 思路分析

简单思路：最简单的做法是循环，但是要考虑异常值的检验。比如指数是负数，底数为 0。

优化思路：书上提供了一种复杂度为 $O(logN)$ 的做法。比如我们要求 32 次方，那么只要求出 16 次方再平方即可。依次类推，是递归函数的结构。

递推公式如下：

$$ a^n=\left\{ \begin{aligned} a^{n/2}*a^{n/2} ; n为偶数\\ a^{(n - 1)/2}*a^{(n - 1)/2} ; n为奇数 \end{aligned} \right. $$

需要注意的是，如果幂是奇数，例如 5 次方，可以先计算 2 次方，结果平方后（4 次方），再乘以自身（5 次方）。按照此思路处理。