大整数相乘
大整数相乘
题目描述
有两个用字符串表示的非常大的大整数,算出他们的乘积，
也是用字符串表示。不能用系统自带的大整数类型。
输入描述:
空格分隔的两个字符串，代表输入的两个大整数
输出描述:
输入的乘积，用字符串表示
示例1
输入
72106547548473106236 982161082972751393
输出
70820244829634538040848656466105986748
这道题是一道不算很难的题目，就是将你怎么算两个数乘积的方式
加以实现，是一道值得去思考的题目。
由平时自己计算乘积的方式加以思考。
1 2 3
* 4 5 6
------------------
7 3 8
6 1 5
4 9 2
------------------
5 6 0 8 8
通过自行计算的过程可以发现：如果把被乘数定义为A，乘数定义B。
实际上就是依次取出B的每一位数和A进行相乘，得到的数在进行“错位”累加。
所以这道题的难点在于：暂时不考虑符号不相等的情况。
1.一位数与字符串A进行相乘
1 2 3
* 6
------------------
7 3 8
// 字符串与一位数相乘------------分步验证
public static String oneMuliptyDate(String data1,char one) { // 保存运算结果的变量
String temp = "0"; // 将字符串变成字符数组
char[] charData1 = data1.toCharArray(); //首先将字符数组进行倒序，便于计算
for(int i=0;i<charData1.length/2;i++) { char midtemp = charData1[i]; charData1[i] = charData1[charData1.length-i-1]; charData1[charData1.length-i-1] = midtemp; } // 建立一个大于原来数组长度为1的字符数组
char[] newCharData1 = new char[charData1.length+1]; // 相应位置的加数
int flag = 0; // 一次取出字符数组中的数
for (int i = 0; i < charData1.length; i++) { int a = charData1[i] - '0'; int b = one - '0'; int c = a * b + flag; newCharData1[i] =(char)(c % 10 + '0'); flag = c / 10; if (i == charData1.length - 1) { if (flag > 0) { newCharData1Size +=1; newCharData1[i + 1] = (char)(flag + '0'); } } } // 将处理好的字符数组倒序回来。
for(int i=0;i<newCharData1Size/2;i++) { char midtemp = newCharData1[i]; newCharData1[i] = newCharData1[newCharData1Size - i - 1]; newCharData1[newCharData1Size - i - 1] = midtemp; } // 将字符数组转换成字符串。
temp = new String(newCharData1); return temp; }
2.两个字符串怎么进行累加。
7 3 8
6 1 5 (错位)
4 9 2 (错位) (错位)
-------------------------------------------
5 6 0 8 8
// 两个字符串相加
public static String addData(String result,String temp,int num) { // 这里要注意一下 参数i的传入表示错位的位置。 // 将result转换成字符数组，并倒序。
char[] charResult = result.toCharArray(); for(int i=0;i<charResult.length/2;i++) { char midtemp = charResult[i]; charResult[i] = charResult[charResult.length-i-1]; charResult[charResult.length-i-1] = midtemp; } // 将temp转换成字符数组,并倒序。
char[] charTemp = temp.toCharArray(); for(int i=0;i<charTemp.length/2;i++) { char midtemp = charTemp[i]; charTemp[i] = charTemp[charTemp.length-i-1]; charTemp[charTemp.length-i-1] = midtemp; } // 错位相加，通过num记录位置。两个字符串错位相加 // 创建一个新的字符数组，考虑字符数组的长度应该为多少？
int length = result.length()>(temp.length()+num)?result.length()+1:temp.length()+num+1; char[] newResult = new char[length]; // 三个变量指向三个字符串的各个下标
int indexResult=0; int indexTemp=0; int indexNewResult=0; // 相应位置的加数
int flag = 0; while(indexResult<result.length()&&indexTemp<temp.length()) { // 错位的起始位置
if(indexResult<num) { newResult[indexNewResult++] = charResult[indexResult]; } else { int a = charResult[indexResult]-'0'; int b = charTemp[indexTemp]-'0'; int c = a+b+flag; newResult[indexNewResult++] =(char)(c % 10 + '0'); flag = c/10; } indexResult++; indexTemp++; } while(indexResult<result.length()) { int a = charResult[indexResult]-'0'; int c = a+flag; newResult[indexNewResult++] =(char)(c % 10 + '0'); flag = c/10; } while(indexTemp<temp.length()) { int b = charTemp[indexTemp]-'0'; int c = b+flag; newResult[indexNewResult++] =(char)(c % 10 + '0'); flag = c/10; } if(flag>0) { newResult[indexNewResult++]=(char)(flag+'0'); flag=flag/10; } for(int i=0;i<indexNewResult/2;i++) { char midtemp = newResult[i]; newResult[i] = newResult[indexNewResult-i-1]; newResult[indexNewResult-i-1] = midtemp; } return new String(newResult); }
完整实现
import java.util.Scanner; public class DataMuliptyData { public static void main(String args[]) { // 输入两个字符串。
Scanner scn = new Scanner(System.in); String data1 = scn.next(); String data2 = scn.next(); System.out.println(muliptyData(data1,data2)); } // 计算两个字符串的乘积
public static String muliptyData(String data1,String data2) { String result = "0"; for(int i=data2.length()-1;i>=0;i--) { char one = data2.charAt(i); String temp = oneMuliptyDate(data1,one); //这里没处理号，注意要删除前后的空格问题
temp = temp.trim(); result = result.trim(); result = addData(result,temp,data2.length()-i-1); } return result; } // 两个字符串相加
public static String addData(String result,String temp,int num) { // 这里要注意一下 参数i的传入表示错位的位置。 // 将result转换成字符数组，并倒序。
char[] charResult = result.toCharArray(); for(int i=0;i<charResult.length/2;i++) { char midtemp = charResult[i]; charResult[i] = charResult[charResult.length-i-1]; charResult[charResult.length-i-1] = midtemp; } // 将temp转换成字符数组,并倒序。
char[] charTemp = temp.toCharArray(); for(int i=0;i<charTemp.length/2;i++) { char midtemp = charTemp[i]; charTemp[i] = charTemp[charTemp.length-i-1]; charTemp[charTemp.length-i-1] = midtemp; } // 错位相加，通过num记录位置。两个字符串错位相加 // 创建一个新的字符数组，考虑字符数组的长度应该为多少？
int length = result.length()>(temp.length()+num)?result.length()+1:temp.length()+num+1; char[] newResult = new char[length]; // 三个变量指向三个字符串的各个下标
int indexResult=0; int indexTemp=0; int indexNewResult=0; // 相应位置的加数
int flag = 0; while(indexResult<result.length()&&indexTemp<temp.length()) { // 错位的起始位置
if(indexResult<num) { newResult[indexNewResult++] = charResult[indexResult]; } else { int a = charResult[indexResult]-'0'; int b = charTemp[indexTemp]-'0'; int c = a+b+flag; newResult[indexNewResult++] =(char)(c % 10 + '0'); flag = c/10; } indexResult++; indexTemp++; } while(indexResult<result.length()) { int a = charResult[indexResult]-'0'; int c = a+flag; newResult[indexNewResult++] =(char)(c % 10 + '0'); flag = c/10; } while(indexTemp<temp.length()) { int b = charTemp[indexTemp]-'0'; int c = b+flag; newResult[indexNewResult++] =(char)(c % 10 + '0'); flag = c/10; } if(flag>0) { newResult[indexNewResult++]=(char)(flag+'0'); flag=flag/10; } for(int i=0;i<indexNewResult/2;i++) { char midtemp = newResult[i]; newResult[i] = newResult[indexNewResult-i-1]; newResult[indexNewResult-i-1] = midtemp; } return new String(newResult); } // 字符串与一位数相乘------------分步验证
public static String oneMuliptyDate(String data1,char one) { // 保存运算结果的变量
String temp = "0"; // 将字符串变成字符数组
char[] charData1 = data1.toCharArray(); //首先将字符数组进行倒序，便于计算
for(int i=0;i<charData1.length/2;i++) { char midtemp = charData1[i]; charData1[i] = charData1[charData1.length-i-1]; charData1[charData1.length-i-1] = midtemp; } // 建立一个大于原来数组长度为1的字符数组
char[] newCharData1 = new char[charData1.length+1]; // 相应位置的加数
int flag = 0; // 一次取出字符数组中的数
for (int i = 0; i < charData1.length; i++) { int a = charData1[i] - '0'; int b = one - '0'; int c = a * b + flag; newCharData1[i] =(char)(c % 10 + '0'); flag = c / 10; if (i == charData1.length - 1) { if (flag > 0) { newCharData1Size +=1; newCharData1[i + 1] = (char)(flag + '0'); } } } // 将处理好的字符数组倒序回来。
for(int i=0;i<newCharData1Size/2;i++) { char midtemp = newCharData1[i]; newCharData1[i] = newCharData1[newCharData1Size - i - 1]; newCharData1[newCharData1Size - i - 1] = midtemp; } // 将字符数组转换成字符串。
temp = new String(newCharData1); return temp; } }
更多精彩
