【题16 数值的整数次方】Java实现

桃扇骨 2022-03-27 10:35 54阅读 0赞

**【题16 数值的整数次方】**  
**【题目】**  
实现函数double Power（double base，int exponent）。求base的exponent次方，不得使用库函数，同时不需要考虑大数问题。  
**<自以为题目简单的解法>**  
可能存在的问题：  
如果输入的指数小于1的时候怎么办？  
**<全面的但不高效的解法>**  
（1） 如果指数为负数，可以先对指数求绝对值，算出次方的结果之后取倒数  
（2） 底数是0且指数为倒数时，不进行特殊处理会出现对0求倒数，导致程序运行出错。  
阐述三种错误处理方法的优缺点，返回值，全局变量和异常，然后决定用哪一种。  
![在这里插入图片描述][20190113094301665.png]  
（3）0的0次方，在数学上是无意义的，因此无论输出0或者1都能接受，但需要说清楚，证明考虑到了这个边界值  
**<既全面又高效的解法>**  
1.如果输入的指数是32，则函数的循环中需要做31次乘法。  
换个思路：求一个数字的32次方，如果知道16次方，那么再平方即可。。。  
即求一个数字的32次方，只需做5次乘法：先求平方，平方的基础上求4次方，4次方基础上求8次方，8次方基础上求16次方，16次方基础上求32次方。  
公式表示：  
![在这里插入图片描述][20190113094312692.png]  
为O（logn）时间求斐波那契数列递归即可实现——**改进1**  
2.用右移运算符代替除以2，用位于运算符代替了求余运算符（%）来判断一个数是否是奇数还是偶数，位运算的效率比乘除法及余运算的效率要高很多——**改进2**  
**2个细节：**  
①判断base是否等于0  
②用位运算代替乘除法及求余运算

**实现**

package ti16;
    
    public class Lianxi {
    	//自以为简单的解法
    	public double power0(double base, int exponent) {
            double result = 1.0;
            for (int i = 1; i <= exponent; i++) {
                result *= base;
            }
            return result;
        }
    	
    	//全面但不高效的解法
    	boolean invalidInput = false;       //使用全局变量处理错误
    
        public double power1(double base, int exponent){
            if(equal(base, 0.0) && exponent <= 0){
                invalidInput = true;
                return 0.0;
            }
    
            int absExponent = exponent;         //定义正指数
            if(exponent < 0)
                absExponent = -exponent;
    
            double result = powerWithExponet0(base, absExponent);
            if(exponent < 0)
                result = 1.0/result;
    
            return result;
        }
    
        public double powerWithExponet0(double base, int exponent){
            double result = 1.0;
            for (int i = 1; i <= exponent; i++) {
                result *= base;
            }
            return result;
        }
    
        //比较两个小数是否相等
        public boolean equal(double num1, double num2){
            double tmp = num1 - num2;
            if(tmp > -0.0000001 && tmp < 0.0000001)
                return true;
            else
                return false;
        }
        
         //全面又高效
        //计算指数为非负数的次方
        public double powerWithExponet(double base, int exponent){
            if(exponent == 0)
                return 1.0;
            if(exponent == 1)
                return base;
    
            //使用左移运算符，将exponent除以2
            double result = powerWithExponet(base, exponent >> 1);
            result *= result;
            if((exponent & 1) == 1){        //判断是否为奇数
                result *= base;
            }
            return result;
        }
        
        //测试
        public static void main(String[] args) {
            Lianxi test = new Lianxi();
            double result = test.power0(2.0, 4);
            System.out.println("结果是：" + result);
            System.out.println("********************");
            double result1 = test.power1(2.0, 4);
            System.out.println("是否是非法输入：" + test.invalidInput);
            System.out.println("结果是：" + result1);
            System.out.println("********************");
            double result2 = test.powerWithExponet(2.0, 4);
            System.out.println("结果是：" + result2);
        }
    }

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/weixin\_37672169/article/details/80150005][https_blog.csdn.net_weixin_37672169_article_details_80150005]

[20190113094301665.png]: /images/20220327/618e822e886d4e479709b1d05b8f9fbb.png
[20190113094312692.png]: /images/20220327/87929a103d234263b3156fe0355cede5.png
[https_blog.csdn.net_weixin_37672169_article_details_80150005]: https://blog.csdn.net/weixin_37672169/article/details/80150005