算法理解——大数相乘问题
发布时间:2020-12-14 03:57:01 所属栏目:大数据 来源:网络整理
导读:腾讯今年校招的一道附加题,就是“大数相乘”问题。所谓大数相乘,就是指数字比较大,相乘的结果超出了基本类型的表示范围,所以这样的数不能够直接做乘法运算。 其实乘法运算可以分拆为两步:第一步,是将乘数与被乘数逐位相乘;第二步,将逐位相乘得到的结
腾讯今年校招的一道附加题,就是“大数相乘”问题。所谓大数相乘,就是指数字比较大,相乘的结果超出了基本类型的表示范围,所以这样的数不能够直接做乘法运算。 其实乘法运算可以分拆为两步:第一步,是将乘数与被乘数逐位相乘;第二步,将逐位相乘得到的结果,对应相加起来。这有点类似小学数学中,计算乘法时通常采用的“竖式运算”。 这里唯一要注意的便是进位问题,我们可以先不考虑进位,当所有位对应相加,产生结果之后,再考虑如果该位的数字大于10,那么我们用取余运算,在该位上只保留取余运算的结果,而将进位(通过模运算得到)累加到下一位便可。 用java简单实现了这个算法,代码如下: public class BigNumberMulti { public static void main(String[] args) { String num1Str = "24566"; String num2Str = "452053"; int[] num1 = new int[num1Str.length()]; int[] num2 = new int[num2Str.length()]; //将字符串转换为整数数组,注意,24566应转化成{6,6,5,4,2} for(int i = 0; i < num1Str.length();i++) { num1[num1Str.length() -1- i] = num1Str.charAt(i)-'0'; } for(int i = 0; i < num2Str.length();i++) { num2[num2Str.length() -1- i] = num2Str.charAt(i)-'0'; } int[] result = multiply(num1,num2); for(int i = result.length-1; i>=0;i--){ System.out.print(result[i]); } } public static int[] multiply(int[] num1,int[] num2) { int lengthOfNum1 = num1.length; int lengthOfNum2 = num2.length; // 分配一个空间,用来存储运算的结果,n1长的数* n2长的数,结果不会超过n1+n2长 int[] result = new int[lengthOfNum1 + lengthOfNum2]; // 先不考虑进位问题,根据小学竖式的乘法运算,n1的第i位与n2的第j位相乘,结果应该存放在结果的第i+j位上 for (int i = 0; i < lengthOfNum1; i++) { for (int j = 0; j < lengthOfNum2; j++) { result[i + j] += num1[i] * num2[j]; } } // 单独处理进位问题 for (int i = 0; i < lengthOfNum1 + lengthOfNum2 -1; i++) { if (result[i] > 10) { result[i + 1] += result[i] / 10; result[i] %= 10; } } return result; } }output:11105133998,经验证,与计算器得出的结果一致。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |