大整数相加与相乘（字符串模拟）

一、大整数相加模拟

思路分析：

①将两个整数翻转

1
2
3
	个位	十位	百位	千位
a	6	  5	   4	1
b	9	  8    7	0

说白了这就是翻转字符串

②相加计算，逢十进一

③反向输出

2245

程序代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package suafna;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {

			String a = sc.next();
			String b = sc.next();
			int len = a.length() > b.length() ? a.length() : b.length();

			a = new StringBuffer(a).reverse().toString();
			b = new StringBuffer(b).reverse().toString();
//      	设置保存结果的容器
			String ans = "";
//			设置保存当前位数的下一位的进位的容器
			int jinwei = 0;
			for (int i = 0; i <= len; i++) {
//				这里为啥要保留第len次循环呢？这是为了防止出现极端情况
//！！！！例如99+1时如果不进行第三位的进位运算会出现第一位被删除的现象，例如这个题会显示 00而不是100
				int num1 = i < a.length() ? a.charAt(i) - '0' : 0;
				int num2 = i < b.length() ? b.charAt(i) - '0' : 0;
				int sum = num1 + num2 + jinwei;
//		！！！	这里为啥要加if条件呢，这是为了防止出现1+3=04的情况
				if (sum != 0) {
					jinwei = 0;
//					置零操作，防止上一轮循环的进位数对本轮造成影响
					if (sum >= 10) {
//						如果本位数大于10 就进一位
						jinwei++;
//						取相加后本位小于10的数 因为已经进了一位
						sum %= 10;
					}
//					不管是否进位都会进行拼接操作，所以要放在if外面，
					ans = sum + ans;
				}
			}
			System.out.println(ans);
		}
	}
}

二、大整数相乘模拟

思路分析：

①将两个整数翻转

1
2
3
	个位	十位
a	 7	 1
b	 5	 2

②相乘计算
$$
\begin{array}{l}a_{0} * b_{0}=7 * 5=35 \ a_{0} * b_{1}=7 * 2=14 \ a_{1} * b_{0}=1 * 5=5 \ a_{1} * b_{1}=1 * 2=2\end{array}
$$
③结果存入c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c0                            c1                          c2

35                            14+5                        2


  17
*
  25
 ----- 
  5  35                     每个位数就对应的是c数组  c0表示最开头的一位，c1表示第二位，c3表示第一位
2 14                        那么对应的状态转移方程（仅仅只是感觉和一维dp有点相似，不知道是不是啊喂）
                            就是c[i+j]=c[i+j]+ai*bj   （对应就是c[1]=5+2*7）
                            （ai和bj相当于a的第i位数字*b的第j位数字）此时只是个半成品数组还需要吧每                             个数组位置上的数变成个位数
-------
c0 c1 c2

④进位计算反向输出

如果c[i]是俩位数，十位的数字附加到c[i+1] 完成初始化之后再倒序遍历即可

程序代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package suafna;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {
			String a = sc.next();
			String b = sc.next();
//			翻转字符串
			a = new StringBuffer(a).reverse().toString();
			b = new StringBuffer(b).reverse().toString();

			int[] c = new int[a.length() + b.length()];
//					开始构建模拟乘法的数组了c1，c2，.....	
			for (int i = 0; i < a.length(); i++) {
//				ai为其中一个乘数某一位的数值
				int ai = a.charAt(i) - '0';
				for (int j = 0; j < b.length(); j++) {
					int bj = b.charAt(j) - '0';
//				bj为其中一个乘数某一位的数值
//				
//				这一步详细看上面思路，模拟乘法的一个方案
					c[i + j] += ai * bj;
				}
			}
//			对半成品数组进行一个进位操作
			for (int i = 0; i < c.length - 1; i++) {
				int jinwei = c[i] / 10;
				c[i] = c[i] % 10;
				c[i + 1] += jinwei;
			}
//			倒着打印表，值得学习这种写法
			int pos = c.length;
//			定义pos指针
//			找到啥时候开始不是0的，也就是说最高的一位绝不可能是0
			while (c[--pos] == 0)
				;
			while (pos >= 0)
				System.out.print(c[pos--]);
		}
	}
}