首页 > 代码库 > 【每日算法】高速幂

【每日算法】高速幂

数值的整数次方

实现函数

double Power(double base, int n) 

求base的n次方,不得使用库函数。同一时候不须要考虑大数问题。

Tips

问题本身非常直观,可是越简单的题越须要细心思考。包含边界问题和效率问题。假设不能考虑到以下3点,就无法给出令人惬意的答案:

  1. 考虑n为负数的情况;
  2. 考虑base为0的情况。
  3. 当n较大时,怎样保证效率?

分析

针对上面3个问题,我们逐一解答:

1.在计算的时候。我们统一计算base的 abs(n)次方,最后假设是负数。答案应该取倒数;

2.假设base为0。则它不能做分母。此时若n<0。则我们应该返回错误信息。

关于返回错误信息,一般有以下方法:

  • 通过返回值;
  • 通过全局变量。
  • 抛出异常。

在这里,我们注意到返回值本身能够取随意值,所以不能单纯靠返回值;假设仅设置全局变量,那么每次计算之后都有检查,比較麻烦;我们能够选择返回值+全局变量的形式来返回错误:

假设有错,返回0,且设置全局变量。

3.当n较大时。可使用高速幂:

若n为偶数, base^n = base^(n/2) * base^(n/2);
若n为奇数。 base^n = base * base^((n-1)/2) * base^((n-1)/2);

解答

以下是Power函数:

bool error = false;
double Power(double base, int n)
{
    error = false;
    if (equal(base, 0.0) && n < 0)
    {
        error = true;
        return 0.0;
    }
    unsigned int absN = (unsigned int)n;
    if (n < 0)
        absN = (unsigned int)(-n);
    double result = PowerWithUnsignedN(base, absN);
    if (n < 0)
        result  = 1.0/result;
    return result;
}

Notice:对于小数,推断是否相等不能直接用 == ,而应该计算两者的差值在一个精度范围内:

bool equal(int num1, int num2)
{
    if ((num1-num2) > -0.0000001 && (num1-num2) < 0.0000001)
        return true;
    else
        return false;
}

以下是核心的高速幂的递归版本号:

double PowerWithUnsignedN(double base, unsigned int n)
{
    if (0 == n) return 1;
    if (1 == n) return base;
    double res = PowerWithUnsignedN(base, n>>1);
    res *= res;
    if (n & 1) //n为奇数
        res *= base;
    return res;
}

普通情况下,以上代码已经非常完美了~

只是假设你更加追求效率,想必递归版本号并不能满足你。那么能够试一试以下的非递归版本号:

double PowerWithUnsignedN(double base, unsigned int n)
{
    double res = 1.0;
    while (n > 0)
    {
        if (n & 1)
            res *= base;
        base *= base;
        n >>= 1;
    }
    return res;
}

关于高速幂,我们经常常使用来做高速幂取模等,略微复杂一点,我们能够用它来做矩阵的高速幂。原理是一样的,仅仅是操作的对象是一个矩阵而不是一个数(矩阵高速幂以求斐波那契数列较为著名。此处暂不展开。后面会开专题写斐波那契数列。有兴趣的读者能够先自行查找相关资料)。

每天进步一点点,Come on!
(●’?’●)


本人水平有限。如文章内容有错漏之处,敬请各位读者指出。谢谢!

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

【每日算法】高速幂