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

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

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

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

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

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

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

我思故我行

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

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

1 、超长整数该如何表示

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

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

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

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

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

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

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

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

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

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

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

l 列竖式，个位对齐；

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

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

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

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

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

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

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

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

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

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

来源：Felven