本文共 2652 字,大约阅读时间需要 8 分钟。
大数乘法
基本思想: 输入字符串,转成char数组,转成int数组。采用分治思想,每一位的相乘; * 公式:AB*CD = AC (BC+AD) BD * 然后从后到前满十进位,顺序如右(BD,(BC+AD),AC)。公式表示的是什么意思呢?
大家回想一下以前小学学的乘法 代码如下:package demo.test;import java.util.Scanner;/** * 大数相乘 * @author Ant * */public class BigMultiply { /** * 大数相乘基本思想,输入字符串,转成char数组,转成int数组。采用分治思想,每一位的相乘; * 公式:AB*CD = AC (BC+AD) BD , 然后从后到前满十进位(BD,(BC+AD),AC)。 * @param num1 * @param num2 */ public String multiply(String num1, String num2){ //把字符串转换成char数组 char chars1[] = num1.toCharArray(); char chars2[] = num2.toCharArray(); //声明存放结果和两个乘积的容器 int result[] = new int[chars1.length + chars2.length]; int n1[] = new int[chars1.length]; int n2[] = new int[chars2.length]; //把char转换成int数组,为什么要减去一个'0'呢?因为要减去0的ascii码得到的就是实际的数字 for(int i = 0; i < chars1.length;i++) n1[i] = chars1[i]-'0'; for(int i = 0; i < chars2.length;i++) n2[i] = chars2[i]-'0'; //逐个相乘,因为你会发现。AB*CD = AC(BC+AD)BD , 然后进位。 for(int i =0 ; i < chars1.length; i++){ for(int j =0; j < chars2.length; j++){ result[i+j]+=n1[i]*n2[j]; } } //满10进位,从后往前满十进位 for(int i =result.length-1; i > 0 ;i--){ result[i-1] += result[i] / 10; result[i] = result[i] % 10; } //转成string并返回 String resultStr = ""; for(int i = 0; i < result.length-1; i++){ if(i==0&&ret[i]==0) continue;//这里需要判断首位是否是零 resultStr+=""+result[i]; } return resultStr; } public static void main(String[] args) { BigMultiply bm = new BigMultiply(); System.out.println("-----输入两个大数------"); Scanner scanner = new Scanner(System.in); String num1 = scanner.next(); String num2 = scanner.next(); String result = bm.multiply(num1, num2); System.out.println("相乘结果为:"+result); scanner.close(); }}一个更简洁的:
链接:https://www.nowcoder.com/questionTerminal/0f0badf5f2204a6bb968b0955a82779e来源:牛客网import java.util.*;public class Main { public static void main(String[] args){ Scanner in=new Scanner(System.in); String num1=in.nextBigDecimal().toString(); String num2=in.nextBigDecimal().toString(); int[] ret=new int[num1.length()+num2.length()]; for(int i=num1.length()-1;i>=0;i--){ int x=num1.charAt(i)-'0'; for(int j=num2.length()-1;j>=0;j--){ int y=num2.charAt(j)-'0'; ret[i+j]+=(ret[i+j+1]+x*y)/10; ret[i+j+1]=(ret[i+j+1]+x*y)%10; } } String s=""; for(int i=0;i