java 大整数加法 |
您所在的位置：网站首页 › java输入两行整数 › java 大整数加法 |
java 大整数加法
|
描述 求两个不超过200位的非负整数的和。 输入 有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。 输出 一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。 样例输入 22222222222222222222 33333333333333333333 样例输出 55555555555555555555 一：在讲思路前我要先讲一下样例输入存在的坑： 1.输入可能有很多个前导零 2.可能两行输入都是0 3.输入数据的长度可能不一致，相加时短的一方会越界 4.相加后的结果可能要进位 这里举两个例子： 1.有前导零，长度不一，存在进位 样例输入： 000666666 0777 样例输出： 667443
2.全零输入，长短不一 样例输入： 000000 000 样例输出： 0
注意：数据输入时，存放时，相加时，输出时的次序及下标变化 1.数据输入时：最前面的数字会最先输入，数字的个位是最后被输入的 2.存放时：输入数字的个位，放进数组的最低位i=0，数组的第0位就是数字的个位，往高位方向依次表示十，百，千分位… 3.相加时：两数组先进行相加，将对应位相加的结果放进结果数组arradd[i]=arr1[i]+arr2[i] 小技巧：结果数组的下标默认index=0，考虑输入有000 0000的情况,相加完后，在扫描前导零时，if内的语句一直不被执行，直接输出结果数组的第0位，正好也是0。这样就省去了扫描前导零时，还需额外判断结果数组的最后一位是否仍然为0。 将结果数组进行前导零扫描(从数组最高位开始往数组的低位遍历，直到某位上的数值！=0，用index记录该下标) 4.输出时：输出的起点为结果数组的index~最低位，第一个不为零的数开始依次往个位数方向进行输出for(int i=index;i>=0;i–) ，最先输入的是数字的高分位，最后被输出的是数字的个位，和输入同理 方法： 1.先以字符串的形式接收数字，再以减ascii码的方式转成某一位上原本的数字，存进整型数组中（字符数字-字符’0’=字符数字原本的值）。arr1[i]=String1.charAt(len1-1-i)-‘0’; 2.数组的第一位（下标为0）是输入字符串数字的最后一位（个位），数组最低位做个位，依次升位，方便进位计算和去除前导零 注：可能输入的两行长度不一，则在相加时，短的一方会出现越界，所以初始化两数组长度时不能只是获取其对应字符串长度，而要取两字符串中最长的int len=Math.max(len1, len2); 3.数存到整数数组里，其没有被赋值的位（多出的位）默认值为0（这里利用了全局变量默认值是 0）。 4.进位处理：为防止相加进位而产生越界所以结果数组的长度要为原两数组的最长长度+1（int lenmax=len+1;） 从结果数组的最低位（数字的个位开始进行进位处理）,最高分为不用遍历，它是相加结果最后被进到的那一位 for(int i=0;i public static void main(String[] args) { Scanner sc=new Scanner(System.in); //以字符串形式接收数字，使的高精度数字得以存在 String String1,String2; int len1,len2; String1=sc.next(); String2=sc.next(); len1=String1.length(); len2=String2.length(); //可能输入的两行长度不一，则在相加时，短的一方会出现越界，所以初始化两数组长度时不能只是获取其对应字符串长度，而要取两字符串中最长的 int len=Math.max(len1, len2); int arr1[]=new int[len]; int arr2[]=new int[len]; System.out.println("第一行获取的字符串为:"+String1); System.out.println("第一行字符串长度为:"+len1); System.out.println("第二行获取的字符串为:"+String2); System.out.println("第二行字符串长度为:"+len2); System.out.println("------------------"); //使得字符形式的数用ascii码的方式还原成原数字，存放进整型数组 //字符减字符得到的结果是一个整数 for(int i=0;i arr2[i]=String2.charAt(len2-1-i)-'0'; } System.out.println("此时arr2储存的数据为:"+Arrays.toString(arr2)); //为防止相加进位而产生越界所以结果数组的长度=len+1 int lenmax=len+1; int arradd[]=new int[lenmax]; System.out.println("结果数组arradd的长度为:"+lenmax); System.out.println("-----------------"); //对应位开始进行相加计算，从最低位（数字中的个位）开始 for(int i=0;i arradd[i+1]=arradd[i+1]+arradd[i]/10; arradd[i]=arradd[i]%10; } System.out.println("进位结束后的结果数组为:"+Arrays.toString(arradd)); System.out.println("-----------------"); //对结果数组去掉前导零,碰到前导零就continue。直到第一个不为零的数则记录该下标index //默认=0，如果为全零相加，则index不会被赋值，结果数组全为0，直接输出第0位，刚好就输出了一个零 int index=0; for(int i=arradd.length-1;i>=0;i--) { System.out.println("当前数组高位数字为"+arradd[i]); if(arradd[i]==0) { continue; } if(arradd[i]!=0) { index=i; System.out.println("找到第一个不为零的数,其下标为:"+index); break; } } //将储存在arradd中的数从index位到最低位（个位）依次进行输出 System.out.println("从下标"+index+"到第0位进行输出"); for(int i=index;i>=0;i--) { System.out.print(arradd[i]); } }}然后是纯代码版本，ac就靠它了ww import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String String1,String2; int len1,len2; String1=sc.next(); String2=sc.next(); len1=String1.length(); len2=String2.length(); int len=Math.max(len1, len2); int arr1[]=new int[len]; int arr2[]=new int[len]; for(int i=0;i arr2[i]=String2.charAt(len2-1-i)-'0'; } int lenmax=len+1; int arradd[]=new int[lenmax]; for(int i=0;i arradd[i+1]=arradd[i+1]+arradd[i]/10; arradd[i]=arradd[i]%10; } int index=0; for(int i=arradd.length-1;i>=0;i--) { if(arradd[i]==0) { continue; } if(arradd[i]!=0) { index=i; break; } } for(int i=index;i>=0;i--) { System.out.print(arradd[i]); } }} |
二：坑讲完了开始讲思路和方法 思路： 1.首先java中好像不支持超长整数直接进行运算（python可以），同时这道题属于一维数组题类。可见这道题的解法需要依靠数组 2.每一行输入的数字过长所以要以字符串的形式进行接收，然后巧妙的运用字符的ASCII码将字符数字转换成原本的数字存放进整型数组中 3.创建一个结果数组，用来存放两数组相加后的结果 4.最后对结果数组进行进位操作，并且结果数组中也存在前导零，这时就要进行前导零的扫描，直到扫到数字高位上不为零的那个下标，从该下标往数字的个位（数组的低位）方向进行输出【本文地址】