剑指offer 数值的整数次方

Posted on |

数值的整数次方

题目

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

方法

方法1：斐波那契数列方法

需要注意的地方:
当指数为负数的时候
当底数为零且指数为负数的情况
在判断底数base是不是等于0的时候,不能直接写base==0, 因为计算机内表示小数时有误差,只能判断他们的差的绝对值是不是在一个很小的范围内

当n为偶数, $a^n = a^(n/2) a^(n/2)$
当n为奇数, $a^n = a^((n-1)/2) a^((n-1)/2)) * a$

  • 利用右移一位运算代替除以2
  • 利用位与运算代替了求余运算法%来判断一个数是奇数还是偶数
    优化代码速度
    1
    2
    if (num & 0x1)==0:
        print('偶数')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        if exponent==0:
            return 1
        if exponent==1:
            return base
        if exponent==-1:
            return 1/base
        result=self.Power(base, exponent>>1)
        result*=result
        if (exponent & 0x1)!=0:
            result*=base
        return result

方法2

需要注意的地方:
当指数为负数的时候
当底数为零且指数为负数的情况
在判断底数base是不是等于0的时候,不能直接写base==0, 因为计算机内表示小数时有误差,只能判断他们的差的绝对值是不是在一个很小的范围内

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        if exponent==0:
            return 1
        exp=abs(exponent)
        res=1.0
        for i in range(exp):
            res*=base
        if exponent>0:
            return res
        else:
            return 1/res
  • 需要了解位运算