C/C++之数据结构与算法2：高精度计算-减法

一、熟悉的开场白

上回书说到高精度加法这个奇怪的东西。高精度加法的本质是什么？模拟竖式计算。所以，我们能够总结出：高精度运算的本质就是模拟竖式。
抱着这样的结论，我们来处理一下减法吧！

二、算法分析

类似于加法，我们也可以使用竖式来计算减法，这里上文也有所提及。在做减法的时候，需要注意的就是被减数必须比减数大，并且还要处理进位的问题。

三、步履踉跄的写代码

1.准备工作

首先，我们要创建一个文件 将输入的被减数和减数保存。样例代码如下：

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	gets(a);
	gets(b);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

在将数字保存到char类型的数组之中后，我们就该把它们转换进int类型的数组里了。注意，这里每个int类型的下标内都只存一个个位数，也就是我们的每一位元素。

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	int a_int[1024],b_int[1024];
	gets(a);
	gets(b);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

接着，我们应该考虑到一个问题：符号。如果被减数比减数小，那么我们就要手动添加一个负号，并且交换减数和被减数才可以。这是一点值得注意的。
那么，如何判断被减数和减数的大小情况？首先，我们能肯定，我们是要对char类型的变量做判断，而并非int类型的数组。
判断的条件是什么？第一，如果被减数的长度小于减数的长度，那么肯定就是被减数小于减数的。写成代码，如下：

strlen(a) < strlen(b)
1

第二，就是要判断如果被减数和减数的长度相等的情况了。我们只需要用到strcmp函数来判断一下即可了。我们如果把这一点写成代码的话如下：

strlen(a) == strlen(b) && strcmp(a,b) < 0
1

我们将之前的所有代码一整合，我们能够得到了判断正负性的代码了。

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	int a_int[1024],b_int[1024];
	gets(a);
	gets(b);
	if(strlen(a)<strlen(b) || (strlen(a)==strlen(b) && strcmp(a,b)<0))
	{ 
		cout<<"-";
		char c[1024];
		strcpy(c,a);
		strcpy(a,b);
		strcpy(b,c);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里又出现了一个新的函数：strcpy。这个函数的作用其实看代码就可以大致猜出来，就是将后一个参数里的值传给前一个参数。所以我们说c这个数组只不过是个工具人罢了。
接下来，就是一个简单易懂的部分了：将char类型的数组传给int类型。随着这一步的结束，准备工作也算是告一段落了。

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	int a_int[1024],b_int[1024];
	gets(a);
	gets(b);
	if(strlen(a)<strlen(b) || (strlen(a)==strlen(b) && strcmp(a,b)<0))
	{ 
		cout<<"-";
		char c[1024];
		strcpy(c,a);
		strcpy(a,b);
		strcpy(b,c);
	}
	for(int i=0;i<=strlen(a)-1;i++)
		a_int[strlen(a)-i] = (int)(a[i]-'0');
	for(int j=0;j<=strlen(b)-1;j++)
		b_int[strlen(b)-j] = (int)(b[j]-'0');
	return 0;
}

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

2.劲爆的算法部分

做完准备工作以后，主函数的核心来喽~
至少，我们可以确定一点：在做计算的时候，我们肯定是需要循环来解决的。所以，我们要先确定循环的一些条件才行。
循环的开始要从第一位开始遍历，即i = 1。边界条件我们设置为i的值小于减数或被减数的长度，即i<=strlen(a) || i<=strlen(b)。最后，每次i往后一位继续进行减法，即i++。
综合一下，这代码不就出来了吗？

for(int i=1;i<=strlen(a) || i<=strlen(b);i++)
1

循环的内部，才是最难思考的部分。
首先，考虑进位的问题。如果需要进位，那么a_int[i]的值就要加10，并且a_int[i+1]的值减1。
接着，做减法，即c[i]=a_int[i]-b_int[i]。(这里的c数组还没定义呢~)。
这样，主要的部分我们就写完了。我们在整合一下，便能够得出：

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	int a_int[1024],b_int[1024];
	gets(a);
	gets(b);
	if(strlen(a)<strlen(b) || (strlen(a)==strlen(b) && strcmp(a,b)<0))
	{ 
		cout<<"-";
		char c[1024];
		strcpy(c,a);
		strcpy(a,b);
		strcpy(b,c);
	}
	for(int i=0;i<=strlen(a)-1;i++)
		a_int[strlen(a)-i] = (int)(a[i]-'0');
	for(int j=0;j<=strlen(b)-1;j++)
		b_int[strlen(b)-j] = (int)(b[j]-'0');
	int c[1024]; // 用来存储结果 
	int i;
	for(i=1;i<=strlen(a) || i<=strlen(b);i++)
	{
		if(a_int[i]<b_int[i])
		{
			a[i]+=10;
			a[i+1]--;
		}
		c[i]=a_int[i]-b_int[i];
	}
	return 0;
}
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

3.程序完善

正当我们心满意足的准备开始输出的时候，我们不妨在思考一个问题：前导0。烦人的东西阴魂不散，我们是否一一定义一个变量lenc，用来记录从哪位开始输出？明显是可行的。我们说干就干。

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	int a_int[1024],b_int[1024];
	gets(a);
	gets(b);
	if(strlen(a)<strlen(b) || (strlen(a)==strlen(b) && strcmp(a,b)<0))
	{ 
		cout<<"-";
		char c[1024];
		strcpy(c,a);
		strcpy(a,b);
		strcpy(b,c);
	}
	for(int i=0;i<=strlen(a)-1;i++)
		a_int[strlen(a)-i] = (int)(a[i]-'0');
	for(int j=0;j<=strlen(b)-1;j++)
		b_int[strlen(b)-j] = (int)(b[j]-'0');
	int c[1024]; // 用来存储结果 
	int i;
	for(i=1;i<=strlen(a) || i<=strlen(b);i++)
	{
		if(a_int[i]<b_int[i])
		{
			a[i]+=10;
			a[i+1]--;
		}
		c[i]=a_int[i]-b_int[i];
	}
	int lenc = i;
	while(c[lenc] == 0 && lenc>1)
		lenc--;
	return 0;
}

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

最后，我们就来给程序收个尾吧~输出咯！
注意一下：这里要倒序输出！这里要倒序输出！这里要倒序输出！

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	int a_int[1024],b_int[1024];
	gets(a);
	gets(b);
	if(strlen(a)<strlen(b) || (strlen(a)==strlen(b) && strcmp(a,b)<0))
	{ 
		cout<<"-";
		char c[1024];
		strcpy(c,a);
		strcpy(a,b);
		strcpy(b,c);
	}
	for(int i=0;i<=strlen(a)-1;i++)
		a_int[strlen(a)-i] = (int)(a[i]-'0');
	for(int j=0;j<=strlen(b)-1;j++)
		b_int[strlen(b)-j] = (int)(b[j]-'0');
	int c[1024]; // 用来存储结果 
	int i;
	for(i=1;i<=strlen(a) || i<=strlen(b);i++)
	{
		if(a_int[i]<b_int[i])
		{
			a[i]+=10;
			a[i+1]--;
		}
		c[i]=a_int[i]-b_int[i];
	}
	int lenc = i;
	while(c[lenc] == 0 && lenc>1)
		lenc--;
	for(int i=lenc;i>=1;i--)
	{
		cout<<c[i];
	}
	return 0;
}
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

4.程序优化

或许有人说：“啊，整个程序还有啥可优化的 ？都挺好的啊！”
啊不不不，这里还是有一处可以优化的。问题就出在主要的部分：

for(i=1;i<=strlen(a) || i<=strlen(b);i++)
{
	if(a_int[i]<b_int[i])
	{
		a[i]+=10;
		a[i+1]--;
	}
	c[i]=a_int[i]-b_int[i];
}
1
2
3
4
5
6
7
8
9

不知道大家有没有敏锐的捕捉到：这里的i的边界条件有问题。刚刚明明已经确定被减数的长度是大于等于减数的长度了，所以我们这里的边界可以把i <= strlen(b)给去掉。
附上亲爱的优化代码：

#include 
#include 
#include 

using namespace std;

int main()
{
	char a[1024],b[1024];
	int a_int[1024],b_int[1024];
	gets(a);
	gets(b);
	if(strlen(a)<strlen(b) || (strlen(a)==strlen(b) && strcmp(a,b)<0))
	{ 
		cout<<"-";
		char c[1024];
		strcpy(c,a);
		strcpy(a,b);
		strcpy(b,c);
	}
	for(int i=0;i<=strlen(a)-1;i++)
		a_int[strlen(a)-i] = (int)(a[i]-'0');
	for(int j=0;j<=strlen(b)-1;j++)
		b_int[strlen(b)-j] = (int)(b[j]-'0');
	int c[1024]; // 用来存储结果 
	int i;
	for(i=1;i<=strlen(a);i++)
	{
		if(a_int[i]<b_int[i])
		{
			a[i]+=10;
			a[i+1]--;
		}
		c[i]=a_int[i]-b_int[i];
	}
	int lenc = i;
	while(c[lenc] == 0 && lenc>1)
		lenc--;
	for(int i=lenc;i>=1;i--)
	{
		cout<<c[i];
	}
	return 0;
}

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

三、尴尬的结束语

额。。。
那今天就先到这里吧，我是Wanghs0716，我们下期不见不散！

彩蛋：额，这个markdown编译器，我是打死都不会用了！！！