大数相乘算法 List实现
发布时间:2020-12-14 01:57:59 所属栏目:大数据 来源:网络整理
导读:写在前面 周五腾讯模拟笔试(2016.03.25),出了个题,关于大数相乘的问题。这样的题以前也有,网上也有很多实现代码(笔者写完算法后搜索了一下,确有很多,并未细看,并不知道是否有和笔者相同的解决方案)。笔者将算法用java实现,写出来给各位参考一下,
写在前面周五腾讯模拟笔试(2016.03.25),出了个题,关于大数相乘的问题。这样的题以前也有,网上也有很多实现代码(笔者写完算法后搜索了一下,确有很多,并未细看,并不知道是否有和笔者相同的解决方案)。笔者将算法用java实现,写出来给各位参考一下,不足之处,请各位多多指正。 问题问题描述输入两个整数,要求输出两个整数的乘积,该乘积可能超出整型范围。 问题分析首先,依题意,肯定是不能用两个整数直接相乘,得到结果。故要考虑分解问题,即如何将两个大数的乘法,换成一系列小一点的数的运算。由此,笔者根据小学竖式,想到了不进位乘法,觉得可以用不进位乘法来解决大数相乘的问题。至此,算法已经确定,接下来就是如何处理两个整数和其乘积了。笔者自以为可以用ArrayList来存储。 算法描述基本思想:采用不进位乘法计算,然后再将结果进行转换 1 2 3 4 5 list1 5 4 3 2 1
* 1 2 3 list2 3 2 1
————————————————
3 6 9 12 15
2 4 6 8 10
1 2 3 4 5
——————————————————————
1 4 9 16 22 22 15 listres 15 22 22 16 9 4 1
转换为:
1 5 1 8 5 3 5
注意:list中,数据存储的顺序是从最低位开始,依次到最高位
算法实现具体实现代码如下: import java.util.ArrayList;
/** * @Title: 大数相乘list实现(本例中指针对大整数) * @Description: 给定两个大数,其相乘结果可能超出整数的范围, * 溢出。通过本算法实现大数相乘,并打印结果。 * @author: JerryZhou * @date:2016年3月27日 * @version:V1.0 */
public class bigNumMultiple {
/* * 基本思想:采用不进位乘法计算,然后再将结果进行转换 * 如计算12345*123 (num1*num2) * 1 2 3 4 5 list1 5 4 3 2 1 * * 1 2 3 list2 3 2 1 * ———————————————— * 3 6 9 12 15 * 2 4 6 8 10 * 1 2 3 4 5 * —————————————————————— * 1 4 9 16 22 22 15 listres 15 22 22 16 9 4 1 * 转换为: * 1 5 1 8 5 3 5 * 注意:list中,数据存储的顺序是从最低位开始,依次到最高位 */
public static void main(String[] args) {
int a =12345;
int b = 123;
Multiple(a,b);
}
/** * @Title Multiple * @Description 大数相乘,打印结果 * @param num1 * @param num2 */
public static void Multiple(int num1,int num2){
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
ArrayList<Integer> listres = new ArrayList<Integer>();
if(num1<num2){ //将较大的数放在前面
int tmp = 0;
tmp = num1;
num1 = num2;
num2 = tmp;
}
while(num1/10!=0){ //将num1,从个位开始,依次存入list1中
list1.add(num1 % 10);
num1 = num1 / 10;
}
list1.add(num1);
while(num2/10!=0){ //将num2,从个位开始,依次存入list2中
list2.add(num2 % 10);
num2 = num2 / 10;
}
list2.add(num2);
int firstlen = list1.size(); //num1的位数
int secondlen = list2.size(); //num2的位数
for(int i = 0;i < secondlen; i++){ //不进位乘法运算
for(int j = 0;j< firstlen;j++){
if(listres.size()<j+i+1){
listres.add(0);
listres.set(j+i,listres.get(j+i)+list1.get(j)*list2.get(i));
}else{
listres.set(j+i,listres.get(j+i)+list1.get(j)*list2.get(i));
}
}
}
int len = listres.size();
for(int i =0;i<len;i++){ //结果转换
if(listres.get(i)>9){
int temp = listres.get(i)/10;
listres.set(i,listres.get(i)%10);
if(listres.size()<i+2){ //考虑到最高为的进位问题,可能导致list需要开辟新空间
listres.add(0);
}
listres.set(i+1,listres.get(i+1)+temp);
}else{
continue;
}
}
while(len>0){ //打印大数相乘的最后结果
System.out.print(listres.get(len-1));
len-=1;
}
}
}
以上程序经笔者测试,确实是成功解决了大数相乘的问题,但笔者认为还有很大的优化空间。希望各位读者多多指正。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |