算法

快速幂算法

Posted by Meng Cao on 2019-06-19

Leetcode 50. Pow(x, n)

Example 1:
Input: 2.00000, 10
Output: 1024.00000

Example 2:
Input: 2.10000, 3
Output: 9.26100

Log(n)的时间复杂度

递归写法：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    double myPow(double x, int n) {
        return n >= 0 ? myPowImp(x,n) : 1.0 / myPowImp(x,n);
    }
private:
    double myPowImp(double x, int n) {
        if(n == 0) return 1.0;
        return myPowImp(x*x, n/2) * (n%2 ? x : 1);
    }
};

迭代写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    double myPow(double x, int n) {
        double res  = 1.0;
        for (int i=n; i != 0; i/=2) {
            if (i%2) res *= x;
            x *= x;
        }
        return n < 0 ? 1 / res : res;
    }
};
/*
x = 2.0, n = 10;

i = 10 : x = (2.0)^2 = 4;
i = 5 : res = 1*4 = (2.0)^2 ; x = 4 * 4 = (2.0) ^ 4;
i = 2 :  x = (2.0) ^ 8;
i = 1 : res = (2.0)^2 * (2.0)^8;  
i = 0
*/

372. Super Pow

Example 1:

Input: a = 2, b = [3]
Output: 8
Example 2:

Input: a = 2, b = [1,0]
Output: 1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int superPow(int a, vector<int>& b) {
        long long res = 1;
        for(int i=0; i<b.size(); ++i)
            res = pow(res, 10) * pow(a, b[i]) % 1337;
        return res;
    }
    
private:
    long pow(int x, int n) {
        if(n == 0) return 1;
        return pow((x%1337)*(x%1337), n/2) * (n%2 ? x%1337 : 1);
    }
};

斐波那契数列求第n项的快速求法

所以问题转化成求矩阵的n次幂，同求整数的n次幂算法一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import numpy as np

def Fibonacci_matrix(n):
    '''
    def power(x, n):
        if n == 1:
            return x
        ans = power(np.dot(x,x), n/2)
        if n % 2:
            ans = np.dot(x, ans)
        return ans
     '''
    def power(x, n):
        if n == 1:
            return x
        res = np.eye(2)
        while n != 0:
             if n % 2:
                 res = np.dot(x, res)
             x = np.dot(x, x)
             n /= 2
        return res


    if n == 0:
        return 0
    if n == 1:
        return 1
    q = ((1,1), (1,0))
    return power(q, n-1)[0][0]

if __name__ == '__main__':
    a = Fibonacci_matrix(5)
    print (a)
FEATURED TAGS
算法
FRIENDS