Freeman's Blog

一个菜鸡心血来潮搭建的个人博客

0%

算法题中的数学类型题归集

发表于 更新于 分类于

非科班鶸遇到数学题总是比较头疼，于是做一点整理

乘法快速幂

思想

乘法快速幂主要是用于求一个数的n次幂，使用循环的时间复杂度是$O(n)$。如果n比较大的话这个时间复杂度是不能满足要求的。使用乘法快速幂可以让计算的时间复杂度达到$O(logn)$

对于$a^n$，若$n$是偶数，则当已经求出$a^\frac{n}{2}$时，则可以通过$a^\frac{n}{2} \times a^\frac{n}{2}$求出$a^n$，而不必接着一个一个地让当前结果乘以$a$。如果$a$是奇数，则可以通过$a ^ {\lfloor \frac{n}{2} \rfloor} \times a ^ {\lfloor \frac{n}{2} \rfloor} \times a$求出$a^n$。以此类推，最终需要解决的问题是求$a^0$，而$a^0 = 1$。显然这是一个可以通过递归实现的算法。

对于非递归算法，可以考虑倍增的想法：在算出$a^1$的时候马上可以算出$a^2$，进而可以算出$a^4, a^8, … , a^{2^n}$。但是单纯的倍增可能会直接跨过$a^n$。那么我们可以考虑如何使用$a^{2^k}, k=0, 1, 2…$来凑出$a^n$。对于每个$n$，我们可以求出它的二进制形式，进而得到它的二进制分解：通过判断二进制的第$k$位是否为0而判断$n$是否包含$2^k$，进而判断在求$a^n$时是否要把$a^{2^k}$加入结果。

例题1 （剑指offer JZ12）数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0

解

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public double Power(double base, int exponent) {
        if(base == 0)
            return 0;
        double res = absPower(base, exponent);
        if(exponent >= 0)
            return res;
        else
            return 1 / res;
    }
    public double absPower(double base, int exponent) {
        if(exponent == 0) 
            return 1;
        double temp = 1;
        // exponent绝对值为奇数的时候，对2求模可能为1或-1
        // 这么表达更简洁
        if((exponent & 1) == 1) {
            temp = base;
        }
        double ret = absPower(base, exponent / 2);
        return ret * ret * temp;
    }
}

非递归版本
（Java版在鹿上了11111）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double Power(double base, int exponent) {
        // 本题是一个简单的乘法快速幂
        // 二进制分解exponent，达到log(exponent)的时间复杂度
        if(exponent == 0) return 1;
        if(base == 0) return 0;
        if(exponent < 0) exponent--;
        double res = 1;
        int length = sizeof(int) * 8;
        while(length--) {
            if((exponent & 1) && exponent > 0) {
                res *= base;
            } else if(!(exponent & 1) && exponent < 0) {
                res = res / base;
            }
            base *= base;
            exponent >>= 1;
        }
        return res;
    }
};