每周一道算法题(三十九)

本周题目难度级别"Medium"，使用语言C

题目：本周题目又是造轮子，求x的n次方，即pow(x,n).

思路：这题还要思路？就是一数学题，直接上代码：

double myPow(double x, int n) {
    //剪枝，提高效率
    if (x == 1.0 || x == 0.0) return x;
    if (x == -1.0 && ((n % 2) == 0)) return -x;
    if (x == -1.0 && ((n % 2) != 0)) return x;
    //处理n为负数
    if (n < 0) {
        x = 1/x;
        n = -n;
    }
    //剪枝，如果是小数，超过999999次方的都是0
    if (x < 1 && x > 0) {
        if (n - 999999 >= 0) {
            return 0;
        }
    }
    
    double result = 1;
    //for循环求解
    for (int i = 0; i < n; i++) {
        result *= x;
        //剪枝，小于0.00001就不用继续循环了。
        if (result < 0.00001 && result >0) {
            result = 0;
            break;
        }
    }
    return result;
}

上面的代码是我自己写的，效率一般，然后让大家看看效率高的，如下代码（此代码不是我写的，是目前效率最高的，没有署名所以只能感谢不知名的作者了，因为不是我写的，我就不注释了，二分法迭代都能看懂）：

double fastpow(double x, int n) {
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    double t = fastpow(x, n / 2);
    if (n % 2)
        return t * t * x;
    return t * t;
}

double myPow(double x, int n) {
    if (n < 0) 
        return 1 / fastpow(x, -n);
    return fastpow(x, n);
}

这周题目都写完了，上周的题还没做出来/(ㄒoㄒ)/~~。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!