Skip to content

Latest commit

 

History

History
83 lines (67 loc) · 4.08 KB

A-20190731-数值的整数次方.md

File metadata and controls

83 lines (67 loc) · 4.08 KB
Raw

题目描述

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

第一版解题思路：

希望利用2分法，但是指数可能不是2的幂次方，所以将指数分成2个部分相乘，一部分是2的幂次方，剩下的为另外一部分，如 $$ base^{15} = base^{8} * base^{7} $$ 幂次方的部分，用循环计算，不是幂次方的部分，也在循环中计算 $$ suppose \qquad exponent = 15 \ 第一次除以2，并求余 \qquad exponent = exponent / 2 , exponent % 2 =1 \ 此时exponent = 7 \ base^{15} = base^{7} * base^{7} * base^{1}\ （所以第一次得到的余数1 代表 base^{1},其中 1 = 2^{0}） \ 第二次除以2，并求余 \qquad exponent = exponent / 2, exponent % 2 = 1 \ 此时exponent = 3 \ base^{7} = base^{3} * base^{3} * base^{1}\ base^{15} = (base^{3} * base^{3} * base^{1}) * (base^{3} * base^{3} * base^{1}) * base^{1}\ (base^{3} * base^{3} * base^{3} * base^{3}) * (base^{1} * base^{1} ) * base^{1}\ (base^{3} * base^{3} * base^{3} * base^{3}) * base^{2} * base^{1}\ （由于base^{7}出现了2(2^{1})次，所以第二次得到的余数1 代表 base^{2},其中 2 = 2^{1} ）\ 同理，第三次除以2，并求余 \qquad exponent = exponent / 2, exponent % 2 = 1 \ 此时exponent = 1 \ base^{3} = ( base^{1} * base^{1} )* base^{1} \ base^{15} = (base^{3} * base^{3} * base^{3} * base^{3}) * (base^{2} ) * base^{1}\ = (( base^{1} * base^{1} )* base^{1}) * (( base^{1} * base^{1} )* base^{1}) * (( base^{1} * base^{1} )* base^{1}) * \ (( base^{1} * base^{1} )* base^{1}) * base^{2} * base^{1}\ = (base^{1}*base^{1})^{4} * (base^{1})^{4} * base^{2} * base^{1}\ = (base^{2})^{4} * base^{4} * base^{2} * base^{1}\ （由于base^{3}出现了4(2^{2})次，所以第三次得到的余数1 代表 base^{4},其中 2 = 2^{2}） \ 最后一次处以2，exponent =0 ,结束循环 $$

循环次数 幂次方部分计算 非幂次方部分计算
初始化 result1 = base result2 = 1
第一次 exponent/2 !=0,进入循环 exponent%2 为1
result1 *= result1 余数为1 ，所以 result2 = result1*result2
（这一步在左边的result自乘之前，所以result1= base）
即 result2 = base *1 =base
(result1赋值在result自乘之前，所以result1 = base ，
即上一步中result1的值)
第二次 exponent/2 !=0,进入循环 exponent%2 为1
result1 *= result1 余数为1 ，所以 result2 = result1 * result2
即
第三次 exponent/2 !=0,进入循环 exponent%2 为1
result1 *= result1 余数为1 ，所以 result2 = result1 * result2
即
第四次 exponent/2 ==0,结束循环

代码部分：

public class Solution {
        public double Power(double base, int exponent) {
            double result1 = base;
            double result2 = 1 ;
       		while( exponent / 2 != 0 ){
                if(exponent % 2 != 0){
                   result2 *=  result1;
            	}
            	result1 *=  result1;
            	exponent /= 2;
            }
           
        
            if (exponent > 0)
                return result1*result2;
            else if (exponent < 0)
                return 1/(result1*result2);
            else 
                return 1;
    }  

}