面试题11：数值的整数次方

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

自以为题目简单的解法

public double MyPow(double x, int n)
{
    var total = 1.0;
    for (var i = 0; i < n; i++)
        total *= x;
    return total;
}

上面代码没有考虑零和负数的情况，只包含了指数是整数的情况。

全面但不够高效的解法（leetcode超时了）

public double MyPow(double x, int n)
{
    if (x == 0) return 0;
    if (n == 0) return 1;
    var total = 1.0;
    var power = Math.Abs(n);
    for (var i = 0; i < power; i++)
    {
        total *= x;
    }
    if (n > 0)
        return total;
    else
        return 1 / total;
}

全面又高效的解法

微信图片_20210204215422.jpg

public double MyPow(double x, int n)
{
    if (x == 0 ||x == 1) return 1;
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n == -1) return 1 / x;
    double val = MyPow(x, n / 2);
    val = val * val;
    val = val * MyPow(x, n - n / 2 * 2);
    return val;
}

我们可以换一种思路考虑：我们的目标是求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方是8次方的平方。这样以此类推，我们求32次方只需要做5次乘法：先求平方，在平方的基础上求4次方，在4次方的基础上求8次方，在8次方的基础上求16次方，最后在16次方的基础上求32次方。