【剑指offer】-数值的整数次方-12/67

1. 题目描述

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

2. 题目分析

  1. 题目有两种方法

    1
    2
    1.直接使用暴力遍历来做
    2.使用一种新算法:快速幂
  2. 暴力遍历复杂度O(n),不提倡。这里主要讲解一下快速幂。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    对于快速幂:时间复杂度O(logb)
    我们已知 2^32^6,不就是 2^3 * 2^3嘛。快速幂就是这个原理。
    那有同学问了遇到奇数怎么办?2 ^ 5??
    那不就是 2 * 2 ^ 4 这不就成了嘛。
    所以这就是快速幂的基本思路求a ^ b
    1)当b是奇数时,那么有 a^b = a * a^*(b-1)
    2)当b是偶数时,那么有 a^b = a^(b/2) * a^(b/2)
    举个例子?2 ^10
    2^10 = 2^5 * 2^5
    2^5 = 2 * 2^4
    2^4 = 2^2 * 2^2
    2^2 = 2^1 * 2^1
    2^1 = 2 * 2^0

3. 快速幂的两种表现:递归和迭代

3.1 递归

1
2
3
4
5
6
7
8
9
10
11
ll binaryPow(ll a, ll b, ll m){
ll ans = 1;
while(b > 0){
if(b & 1){
ans = ans * a % m;
}
a = a * a % m;
b >>= 1;
}
return ans;
}

3.2 迭代

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll
ll binaryPow(ll a, ll b, ll m){
ll ans = 1;
while(b > 0){
if(b & 1){
ans = ans * a % m;
}
a = a * a % m;
b >>= 1;
}
return ans;
}

4. 题目代码

4.1 递归

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
public class Solution {
public double Power(double base, int exponent) {
int flag;
if (exponent > 0) {
flag = 1;
} else {
exponent = -exponent;
flag = 0;
}
if (exponent == 0) {
return 1;
} else if (exponent % 2 == 1) {
if (flag == 1) {
return base * Power(base, exponent - 1);
} else {
return 1 / (base * Power(base, exponent - 1));
}
} else {
double sum = Power(base, exponent / 2);
if (flag == 1) {
return sum * sum;
} else {
return 1 / (sum * sum);
}
}
}
}

4.2 迭代

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
public class Solution {
public double Power(double base, int exponent) {
double ans = 1;
if (exponent > 0) {
while (exponent > 0) {
if ((exponent & 1) == 1) {
ans = ans * base;
}
base = base * base;
exponent = exponent >> 1;
}
return ans;
} else if (exponent == 0) {
return 1;
} else {
exponent = -exponent;
while (exponent > 0) {
if ((exponent & 1) == 1) {
ans = ans * base;
}
base = base * base;
exponent = exponent >> 1;
}
return 1 / ans;
}
}
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信