阿里云备案网站建设方案书,基于开源框架的网站开发,松原公司做网站,网站开发在无形资产中高效幂运算
问题描述#xff1a;假设有一机器能够存储这样一些大整数#xff08;或有一个编译程序能够模拟它#xff09;#xff0c;求一个相对大的数字#xff08;一般为400位左右#xff09;的极大幂#xff08;400位左右#xff09; 显然我们可以使用Java内置函数p…高效幂运算
问题描述假设有一机器能够存储这样一些大整数或有一个编译程序能够模拟它求一个相对大的数字一般为400位左右的极大幂400位左右 显然我们可以使用Java内置函数pow()求解但是这大概会需要进行10^400次乘法而下面这种方法在最坏的情形下只需要大约2600次乘法
拆分解法
public class Pow {public static void main(String[] args) {long x 2;int n 5;System.out.println(pow(x,n));}public static long pow(long x,int n){if( n 0 ){return 1;}if( n 1 ){return x;}//偶数 相当于每次将x^n变为x^(n/2) * x^(n/2)if( n % 2 0 ){return pow(x * x, n / 2);}else {//奇数 相当于每次将x^n变为x^((n-1)/2) * x^((n-1)/2) * x//可以写成pow(x*x,n/2) 原因(n-1)/2和n/2在Java中结果相同//可以写成pow(x,n-1)*2 原因通过提出一个x使n变为奇数return pow(x * x, (n-1) / 2) * x;}}
}二进制解法
public class Pow {public static void main(String[] args) {long x 2;int n 5;System.out.println(pow(x, n));}private static long pow(long x, int n) {long pow 1;if (n 0) {return 1;}while (n 0) {if (n % 2 1) {pow * x;}x * x;n 1;}return pow;}
}
当然Java的基本存储结构是不允许我们存放很大的一个数字的但是这种高效幂运算的算法是值得思考的
