利⽤Java ⼤整数类实现⾼次幂运算
利⽤Java ⼤整数类解决⾼次幂运算思路：
若N是偶数，则 X  = X  * X ；
若N是奇数，则 X  = X  * X  * X => (X ) * X。
N N/2N/2N (N-1)/2(N-1)/22(N-1)/2
/**
* 利⽤Java⼤整数类解决⾼次幂运算
* 思路：
*若N是偶数，则X^N = X^N/2 * X^N/2
*若N是奇数，则X^N = X^(N-1)/2 * X^(N-1)/2 * X => (X^2)^(N-1)/2 * X  *
*/
public class 幂运算 {
public static BigInteger o = new BigInteger("0");
public static BigInteger a = new BigInteger("1");
public static BigInteger b = new BigInteger("2");
/**
* 利⽤Java⼤整数类解决⾼次幂运算
* 时间复杂度：O(logN)
* @param x 底数
* @param n 指数
* @return x^n的结果
*/
public static BigInteger pow(BigInteger x, BigInteger n) {
if(n.equals(o)) {
return a;
}
d(b).equals("0")) {
//return pow(x * x, n / 2);
return pow(x.multiply(x), n.divide(b));
}else {
//return pow(x * x, n / 2) * x;
//return pow(x.multiply(x), n.divide(b)).multiply(x);
//return pow(x, n - 1) * x;
return pow(x, n.subtract(a)).multiply(x);
}
}
/**
* ⾮递归
* @param x 底数
* @param n 指数
* @return
*/
public static BigInteger pow3(BigInteger x, BigInteger n) {
BigInteger sum = new BigInteger("1");
while(!n.equals(o)) {
d(b).equals(a)) {
sum = sum.multiply(x);
}
时间正则表达式java
x = x.multiply(x);
n = n.divide(b);
}
return sum;
}
public class 取幂运算 {
public static void main(String[] args) {
String s = "2^2^3^2";
System.out.println(powOfpow(s));
}
/**
* 从右到左结合
* 例：2^2^3 = 2^8 = 256,⽽不是4^3 = 64
* @param s
* @return
*/
public static BigInteger powOfpow(String s) {  String regex = "\\^";//正则表达式
String[] arr = s.split(regex);
BigInteger n = new BigInteger("1");
for(int i = arr.length - 1; i >= 0; i--) {
n = 幂运算.pow2(new BigInteger(arr[i]), n);  }
return n;
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。