一直以来跟别人提起模拟竖式加减法都是只提一个思路,把几位放到数组里,然后怎么怎么样,但说实话还从来没实战过。
网上有很多不限位数的模拟方法,基本上都是用链表。但这样实际使用上反而会比较慢,而且其实大位数不限量也不是一个很关键的点,主要是为了突破int范围去显示。所以这次只是通过定义位数的方式去模拟。
思路就是定义一个int数组,每个数组每一个元素存储一位。代码见下:
1 #include "stdafx.h"
2 #include <iostream>
3 #include <vector>
4 #include <algorithm>
5 #include <cstdio>
6 #include <string>
7 #define MAXSIZE 100//最大位数
8 #pragma warning(disable:4996)
9
10 using namespace std;
11
12 int main()
13 {
14 int num1[MAXSIZE] = { 0 }, num2[MAXSIZE] = { 0 }, sum[MAXSIZE + 1] = { 0 };
15 int size1, size2, size3;
16 char t;
17 char s1[MAXSIZE+1], s2[MAXSIZE+1];
18 gets_s(s1);
19 gets_s(s2);
20 /*测试用例,填满最大长度9
21 memset(s1, '9', sizeof(s1));
22 s1[MAXSIZE] = '\0';
23 memset(s2, '9', sizeof(s2));
24 s2[MAXSIZE] = '\0';
25 */
26 size1 = strlen(s1);
27 size2 = strlen(s2);
28 for (int i = 0; i < size1; i++)
29 {
30 num1[size1-1-i] = s1[i] - 48;//转换字符到数字
31 }
32 for (int i = 0; i < size2; i++)
33 {
34 num2[size2 - 1 - i] = s2[i] - 48;//转换字符到数字
35 }
36 if (size1 > size2) size3 = size1;
37 else size3 = size2;
38 for (int i = 0; i < size3; i++)
39 {
40 sum[i] += num1[i] + num2[i];
41 if (sum[i] >= 10) {//如果发生进位,则舍去10,向高位进1
42 sum[i + 1] = 1;
43 sum[i] -= 10;
44 }
45 }
46 if (sum[size3] == 0) size3--;
47 for (int i = size3; i >= 0; i--)
48 {
49 cout << sum[i];
50 }
51 cout << endl;
52 system("pause");
53 return 0;
54 }
处理这个问题中还有很多问题,大概整理如下:
1.一个是输入问题,涉及到字符串到字符到数字的转换。由于确定了位数,所以我没有定义字符串,定义的是字符数组,通过gets_s函数获得字符串输入,然后再塞进字符数组。字符转数字使用ascii码-48的方式。
2.一个是输入完的字符数组转换到数字的数组,为了之后循环方便和竖式相加的时候是末尾对齐,所以这里得要做一个反循环(见代码),最后输入的数字首位被放到了数字数组的末尾。
3.一个是进位问题,基本的处理思路是,在相加的时候如果发现当前位数字大于10,减去10存储到当前位,让下一位置1。但是当前位还要考虑来自上一位的进位,所以首先给数字数组每个置0,当前位等于当前位本身的数+加数1当前位+加数2当前位。并且还要考虑到最高位发生进位,所以和的数组应该位数比加数的数组最大位+1.
4.鲁棒性问题,除了要考虑最高位溢出,还要考虑用户不正常输入,以及负数输入。基本思路就是,获取输入流之后放到一个字符串中(目前程序内已经做了),判定每一位ascii码是否符合范围。同时,如果允许负数输入,则第一位为‘-’的话,不属于异常。目前程序内没有加入。
为了方便测试边界条件,需要编写测试样例。本代码中使用的方法是通过memset对数组内元素统一置‘9’,之后通过设置末尾为‘\0’截断。经测试在全9的时候,没有发生溢出。程序符合基本要求。