前面的话（ 2006 年 3 月 19 日）：

三次上机过程中，我在机房中转了好多圈，走马观花中由于没有什么人问问题所以就自己主动观察了不少同学是如何编写程序的，居然发现，有一些同学就是坐在机器前，看见我过来了马上动动键盘，“做出”正在编程的样子，于是我也注意以下他的屏幕，看看编写了多少行，再过一会儿，我又转过来了，看看同学还是做出编程的样子，但屏幕上的程序没有什么变化。看见装样子的同学，我到先不好意思了，于是同几个同学聊天，问问他们编写程序的思路是什么，几句话之后明白了，他们对问题没有什么思路，也不知道该如何设计算法。

几次上机之后明白了，同学们拿到一个稍微复杂的问题之后，不知道该如何思考！

我当时的感觉是非常悲哀。首先是教师的悲哀，没有教好，只给了学生“鱼”，而没有给学生“渔”。然后是学生的悲哀，已经被灌输到“不会”、懒得独立思考的地步。

思考的过程还真难于表现，要想讲明白也确实不容易。作为老师给出结果最简单，但要讲明思考和探索的过程也同样困难，于是我试图通过记录自己完成一个程序的主要过程，来反映自己思考问题的过程，是如何从已知出发设计出适当的算法，编写出适当的程序，通过调试。

以下就是星期六从晚上 10 点开始边看电视、边记录思考过程、边编写程序的过程记录。前五步用了 6 个小时，第六步（程序优化）是星期天上午用了 2 个小时完成的。哈哈，效率是低了一点。后来又用了 1 小时看了全部文字，修改了明显的文字错误，但没有在文字中加什么修饰，也没有修正思考过程中后来证明是错误的东西，最后加上这段文字。

写到这里，我想起我的一位大学老师在谈到学生在大学应该学什么的时候，曾经说过的一句话：“学会生活，学会学习，学会思考”。大学是人生最幸福的四年，让我们不负这美好的春光。这样我最后为下面的文字写下如此的题目——

我思故我行

求不超过 500 位的两个整数相加（减）

首先想到的是：一定不能使用常规的运算。要解决这个问题的关键是：

1 、超长整数该如何表示？

2 、在设计的数据结构上，该如何进行加减法操作？

第一步：设计数据结构和程序的基本结构

显然要首先设计数据结构：

最直接的表示是采用数组，数据类型可以采用 int 或 char 。

l 如果采用 char 型，用数组中的一个元素保存整数中的一位，则在中间运算过程要进行 char 类型向 int 类型的数据转换。

l 如果采用 int ，用数组中的一个元素保存整数中的一位，则在中间运算过程不需要进行数据类型转换，但在进行超长整数输入 / 输出时需要进行整数转换。

综合考虑，我们决定采用 char 保存整型数据。于是在输入的时候可以简单采用语句：

char string[1024];
scanf(”%s”, string);
数组 string 中保存的数据格式字符串“ 12345+678 ”。
在确定数据结构之后，进行算法设计。程序的基本结构如下：
{ 输入表达式；
将整数 1 => 数组 a ；
运算符号 => operator ；
将整数 2 => 数组 b ；
if ( operator==’+’ )
add( a, b, c) ； // 假设运算结果放入字符数组 c 中
else
sub( a, b, c) ；
输出结果数组 c ；
}

这样就形成了两个函数 add 和 sub ，分别完成加 / 减运算。

这样我们需要至少 4 个数组：

char string[1024];
char a[512], b[512], c[512] ； // c = a op b

第二步：设计核心算法——加法 add

在这里，核心算法有两个，我们首先设计加法 add 。对于加法运算我们大家最熟悉的就是从小学就会的方法，于是我们来研究在小学学习的加法过程，然后用程序进行模拟。手工进行加法的过程是：

l 列竖式，个位对齐；

l 从个位开始依次向高位按位相加，

l 如果出现进位，则进位要参与上一高的运算。

如果用程序模拟这个过程，则首先要对齐两个整数的个位。可以设计出 add 算法一如下：

add1 ( char a[ ], char b[ ], char c[ ] )
{ 对齐整数的个位；
从个位开始向高位逐位进行按位相加；
}

我们来考虑“对齐整数个位”的算法。由于数据输入进入数组 string 的时候是最高位在数组的前面（整数的最高位在数组的 a[0] ），所以应该将最低位放在数组的最前面（最低位放入 a[0] ），这个算法实际就是一个串反向。

我们来加细前面提出的 add 算法二如下：

add2 ( char a[ ], char b[ ], char c[ ] )
{ 将数组 a 串反向； // 可以使用库函数 strrev 进行串反向
将数组 b 串反向； // 对齐整数的个位，最低位在数组下标位 0 的位置
从个位开始向高位逐位进行按位相加，结果放入数组 c 中；
将数组 c 串反向； // 再将数组 c 中的高位放在数组下标 0 的位置
}

下面对中间的相加的过程进行逐步加细，得到算法三：

add3 ( char a[ ], char b[ ], char c[ ] )
{ 将数组 a 串反向； // 可以使用库函数 strrev 进行串反向
将数组 b 串反向； // 对齐整数的个位，最低位在数组下标位 0 的位置
// 从个位开始向高位逐位进行按位相加，结果放入数组 c 中；
i = 0 ；
while （ 不是最高位 ） {
a[i] 和 b[i] 对应位和前面的进位相加 => c[i] ；
i++ ；
}
将数组 c 串反向； // 再将数组 c 中的高位放在数组下标 0 的位置
}

由于进位的问题，则需要引进一个标志进位的变量 carry ，初始值为 0 。算法 3 可以进一步加细为算法 4 。我们顺手可以将其中部分改写为程序或伪程序了。

add4 ( char a[], char b[], char c[] )
{ int i, carry=0; // carry 位进位
strrev(a); // 将数组 a 串反向
strrev(b); // 将数组 b 串反向
// 从个位开始向高位逐位进行按位相加，结果放入数组 c 中；
i = 0 ；
while （ 不是最高位 ） {
if ( carry + a[i]+b[i] >= 10 ) {
carry = 1;
c[i] = a[i] + b[i] -10; // 这里需要完成 char 向 int 的转换
}
else {
carry = 0;
c[i] = a[i] + b[i]; // 这里需要完成 char 向 int 的转换
}
i++ ；
}
strrev(c); // 将数组 c 串方向
}

在思考中间的 while 循环的时候，我又想到一个问题，那就是如果出现两个相加的整数步等长的情况该怎么办？显然加到后来就不是两个对应位相加了。再考虑一种特殊的情况“ 9999+1 ”，从十位开始，个位产生的进位就会不断向前再产生进位，一直到使得结果多出一位。因此，算法 4 的中间部分只适合两个整数等长的情况，不适合不等长的情况。因此要进一步修改，得到算法 5 。

add5 ( char a[ ], char b[ ], char c[ ] )
{ int i, carry=0;
strrev(a); // 将数组 a 串反向
strrev(b); // 将数组 b 串反向
// 从个位开始向高位逐位进行按位相加，结果放入数组 c 中；
i = 0 ；
while （ 串 a 和串 b 都没有结束 ） {
if ( carry + a[i] + b[i] >= 10 ) {
carry = 1;
c[i] = a[i] + b[i] -10; // 这里需要完成 char 向 int 的转换
}
else {
carry = 0;
c[i] = a[i] + b[i]; // 这里需要完成 char 向 int 的转换
}
i++ ；
}
if （ 串 a 没有结束 ）
处理串 a 余下的高位部分 // 可以调一个函数 addcarry(a,c, int carry)
else
处理串 b 余下的高位部分 // 可以调一个函数 addcarry(b,c, int carry)
strrev(c); // 将数组 c 串反向
}

对于新产生的函数 addcarry ，要处理余下的高位部分，则还要将前面的相加得到的进位带上，而且如果在加数最高位处理结束后，还产生了新的进位，则在结果中要增加一位新的位作为结果的最高位。因此可以得到 addcarry 的算法。

addcarry (char a[ ], char c[ ], int carry )
{ while ( 串 a 没有结束 ) {
if ( carry + a[i] >= 10 ) {
carry = 1;
c[i] = a[i] -10; // 这里需要完成 char 向 int 的转换
}
else { // 无进位，则可以不再处理
carry = 0;
c[i] = a[i];
}
i++;
}
if ( carry != 0 ) { // 处理最后一个进位
c[i] = carry;
c[i+1] = ‘/0’;
else c[i] = ‘/0’;
}

对算法 add 进行整理，尽量采用 C 语言的语句进行描述。得到 add 函数。

add ( char a[ ], char b[ ], char c[ ] )
{ int i, carry=0;
strrev(a); // 将数组 a 串反向
strrev(b); // 将数组 b 串反向
// 从个位开始向高位逐位进行按位相加，结果放入数组 c 中；
i = 0 ；
while （ a[i]!=’/0’ && b[i]!=’/0’ ） { // 串 a 和串 b 都没有结束
if ( carry + a[i]-’0’ + b[i]-’0’ >= 10 ) {
carry = 1;
c[i] = a[i] + b[i]-’0’-10;
}
else {
carry = 0;
c[i] = a[i] + b[i]-’0’;
}
i++ ；
}
if （ a[i]!=’/0’ ） // 处理串 a 余下的高位部分
addcarry(a,c, int carry);
else if ( b[i]!=’/0’ ) // 处理串 b 余下的高位部分
addcarry(b,c, int carry);
strrev(c); // 将数组 c 串反向
}

对算法 addcarry 进行整理，尽量采用 C 语言的语句进行描述。得到 addcarry 函数。

addcarry (char a[], char c[], int carry )
{ int i=0;
while ( a[i]!=’/0’ ) {
if ( carry + a[i] > ’9’ ) {
carry = 1;
c[i] = ’0’;
}
else { // 无进位，则可以不再处理
carry = 0;
c[i] = a[i];
}
i++;
}
if ( carry != 0 ) { // 处理最后一个进位
c[i] = carry;
c[i+1] = ‘/0’;
else c[i] = ‘/0’;
}

第三步：进行数据输入之后的准备工作

在第一步已经完成表达式输入工作，下面要进行的是整数的拆分和运算符的识别。这个算法比较简单了，只要逐个处理字符就可以了，我们可以简单写出如下处理程序段：

char string[1024], a[512], b[512], c[512], operator;
int i;
scanf(”%s”, string);
i=0;
while ( ‘0’<=string[i] && string[i]<=’9’ ) { // 将整数 1 => 数组 a ；
a[i] = string[i];
i++;
}
operator = string[i] ；
while ( ‘0’<=string[i] && string[i]<=’9’ ) { // 将整数 2 => 数组 b ；
b[i] = string[i];
i++;
}

第四步：设计核心算法—— sub 函数

略。

第五步：合成整个 main 程序，完成加法运算

int main ()
{ char string[1024], a[512], b[512], c[512], operator;
int i;
scanf(”%s”, string);
i=0;
while ( ‘0’<=string[i] && string[i]<=’9’ ) { // 将整数 1 => 数组 a ；
a[i] = string[i];
i++;
}
operator = string[i] ；
while ( ‘0’<=string[i] && string[i]<=’9’ ) { // 将整数 2 => 数组 b ；
b[i] = string[i];
i++;
}
if ( operator==’+’ )
add( a, b, c); // 假设运算结果放入字符数组 c 中
else
sub( a, b, c);
printf （ ”%s” ， c ） ;
}

第五步：调试

将 sub 函数写为：

sub ()
{ return;
}

1. 通过编译，保证没有语法错误。初始的程序至少有 22 个错误。增加了变量 j 。

2. 开始运行程序，输入： 123+12 ，程序运行结束，但显示的结果为乱码。这样的结果非常正常，因为我们不是神仙，编出的程序不可能马上一点错误都没有。

3. 单步开始运行，跟踪程序中数组 a 、 b 、 c 的变化过程。发现在设计算法的时候没有考虑到当两个整数长度相等是应该如何处理最后的进位，于是打上一个小些“补丁”。得到运行正确的运行结果。

4. 初步错误排除后，看是系统运行测试用例。

l 12+1234 // 测试不等长情况没有任何进位的情况

l 1234+12 // 同样

l 1234+2341 // 测试等长无进位情况

l 1089+8011 // 测试等长中间有进位的情况

l 1+9 // 测试最简单的有进位、结果增加 1 位情况

l 99999+1 // 测试最常见的极限情况

l 11+99999 // 同上

l 0+88

l 88888+0

说明：在这个过程中没有使用任意的太长的数据，因为测试数据应该是事先可以预知运行结果的，如果不能预知运行结果，那面对实际的运行结果，就无法判断出程序结果对错，也就失去了运行测试用例的意义。

通过调试，我们可以发现程序中的 N 多错误，通过跟踪程序中变量的值，可以改正错误，得到正确的程序如下。

#include <stdio.h>
int main ()
{ char string[1024], a[512], b[512], c[512], operator;
int i, j;
scanf("%s", string);
i=0;
while ( '0'<=string[i] && string[i]<='9' ) {
a[i] = string[i];
i++;
}
a[i]='/0';
operator = string[i];
i++;
j=0;
while ( '0'<=string[i] && string[i]<='9' ) {
b[j] = string[i];
i++;
j++;
}
b[j]='/0';
if ( operator=='+' )
add( a, b, c);
else
sub( a, b, c);
printf("%s/n", c);
return 0;
}
add ( char a[], char b[], char c[] )
{ int i, carry=0;
strrev(a);
strrev(b);
i = 0;
while ( a[i]!='/0' && b[i]!='/0' ) {
if ( carry + a[i]-'0' + b[i]-'0' >= 10 ) {
c[i] = carry + a[i] + b[i]-'0'-10;
carry = 1;
}
else {
c[i] = carry + a[i] + b[i]-'0';
carry = 0;
}
i++;
}
if ( a[i]!='/0' )
addcarry( &a[i], &c[i], carry);
else if ( b[i]!='/0' )
addcarry( &b[i], &c[i], carry);
else if ( carry!=0 ) {
c[i] = carry+'0';
c[i+1]='/0';
}
else c[i]='/0';
strrev(c);
}
addcarry (char a[ ], char c[ ], int carry )
{ int i=0;
while ( a[i]!='/0' ) {
if ( carry + a[i] > '9' ) {
carry = 1;
c[i] = '0';
}
else {
carry = 0;
c[i] = a[i];
}
i++;
}
if ( carry != 0 ) {
c[i] = carry+'0';
c[i+1] = '/0';
}
else c[i] = '/0';
}
sub ()
{ return;
}

第六步：优化程序

显然这个程序不是优化的程序，应该进行优化。

可以进行的优化包括：

1. 可以消去数组 a 和数组 b 。利用 string 空间就可以。

2. 在 add 过程中，可以免去串 a 和串 b 的反向过程。

3. 可以使用指针完成串操作。

4. 在处理最后进位的地方 add 过程与 addcarry 有重复的地方。

优化后的程序如下：

#include <stdio.h>
int main ()
{ char string[1024], c[512], operator;
int i;
scanf("%s", string);
i=0;
for ( i=0; '0'<=string[i] && string[i]<='9'; i++ ) ;
operator = string[i];
string[i++]='/0';
if ( operator=='+' )
add( string, &string[i], c);
else
sub( string, &string[i], c);
printf("%s/n", c);
return 0;
}
add ( char *a, char *b, char *c )
{ int i, carry=0;
char *p, *q, *r, *s ,*end;
for ( p=a+strlen(a)-1,q=b+strlen(b)-1,r=c; a<=p && b<=q; p--,q--,r++ ) {
*r = carry + *p + *q - '0';
if ( *r > '9' ) {
*r = *r - 10;
carry = 1;
}
else carry = 0;
}
s = (a>p) ? q : p;
end = (a>p) ? b : a;
for ( ; s >= end; s--, r++ ) {
*r = *s + carry;
if ( *r > '9' ) {
carry = 1;
*r = '0';
}
else carry = 0;
}
if ( carry != 0 )
*r++ = carry+'0';
*r = '/0';
strrev(c);
}
sub ()
{ return;
}

重新运行前面的测试用例，保证测试用例完全正确。

此时，这个程序有点像专业人员编写的 C 语言程序了。

第七步：对程序的再优化

其实这个程序在数组空间使用上是非常浪费的，因为数组的一个元素只保存了一个数字，效率非常低。我们完全可以采用 int 型的数组来保存数据，而且也可以采用整型的表示方法。这样需要重新设计新的算法。

新的加法算法请参见《 C 语言程序设计习题集（第二版）》中的 10.17 题和 10.18 题。