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

傷城~ 2023-05-28 09:46 2阅读 0赞

# 题目描述 #

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

# 题目分析 #

1.  题目有两种方法

1.直接使用暴力遍历来做
    2.使用一种新算法:快速幂

1.  暴力遍历复杂度O(n)，不提倡。这里主要讲解一下快速幂。

对于快速幂：时间复杂度O（logb）
    我们已知 2^3  求 2^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

1.  快速幂的两种表现：递归和迭代

**递归**

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;
    }

**迭代**

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;
    }

# 题目代码 #

**递归**

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);
    			}
    		}
    	}
    }

**迭代**

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;
            }
      }
    }