第一道ACM练习题
说来惭愧，今天才真正做过一道ACM练习题。自从上个月发现我的母校上有ACM的在线测试站点，我就下决心好好潜心做题，一来提高一下自己解决问题的能力，一方面也想在算法方面多实践实践，而且每天都花一定时间写程序还可以锻炼自己的思维能力。总而言之，由于项目繁忙以至直到今天才开始做第一道ACM练习题，做题的过程’坎坷不平’，让我印象深刻亚!^_^
有人会说：’ACM’中的题都是不实用的，没有实际意义。我之前也曾经是这么想的。不过今天的作题过程让我完全推翻了以前的想法，我发现ACM的习题是很能锻炼个人的思维能力、编程能力的。就拿今天我做的这道看似简单的问题，实际上其背后也蕴含着很多基础理论，如果没有很好的理论基础做后盾，我相信很多人都会在这道题上’碰个头破血流’。
在看题之前我不能不说母校的那套ACM在线测试系统，你只需要做一个简单的注册，即可使用该系统，目前系统支持C/C++良种语言的提交代码，系统会自动对你的源码进行编译、运行和测试，并在你提交代码后大约5分钟内给出你结果。系统提供一个’Problem Set’供大家解决，目前这个’Problem Set’中有超过1000个题目，有兴趣的人大可以去试试，没有什么奖励，就是兴趣而已，特别是像我们这些已经毕业的人更不可能以参加ACM竞赛为目标了^_^。该站点还提供一个论坛，供解决问题者交流心得。
解决ACM练习题不同于开发商业软件，所有的题都有明确的’输入范围’，所以在程序里无需’断言’等’Precondition Check’，对异常的处理也无需太过考虑。ACM主要锻炼的是你的思考过程、算法设计能力以及快速解决问题的能力。要想达到一个很高的层次，需经过大量的训练才可以。
大多数人在解决’Problem Set’中的问题时都是从Problems Volume I开始，我也不例外。Volume I的第一道题1001我觉得是个举例，没必要对它进行过多研究。看完1001后，进入1002，这也是本文想说的一个实例。
1002问题的题目为’A+B+C’，具体内容描述如下：
"For each pair of integers A B and C ( -2^31 <= A, B, C<= 2^31-1 ), Output the result of A+B+C on a single line. "
Sample Input
1 2 3
3 4 3
Sample Output
6
10
题目看起来很简单，不细心的人很可能把1001的解决方案直接拿过来套用，这样当然是错的了。那么这道题到底需要什么知识呢？我们大致来分析一下：这道题其实就是一个加法题，唯一让大家担心的就是几个输入数据的范围照比1001的[1, 10]要扩大了，扩大到无符号整型范围，这样就导致我们必须考虑一个问题：那就是’溢出’问题。很多人都能想到这，那么如何解决这一问题呢？
首先拿出一个方案看看可行不：
[方案一]
#include <stdio.h>
int main(void) {
int a;
int b;
int c;
while (scanf("%d %d %d", &a, &b, &c) == 3) {
printf("%d\n", a + b + c);
}
return 0;
}
首先将a, b, c定义为int(一般系统的实现都把int默认为unsigned int)可以满足输入需求，但是a + b + c显然可能会溢出，导致结果不正确。
[方案2]
既然直接使用a + b + c，并使用%d输出会溢出，那么我们用一个更大的数据类型来存储相加后的结果呢，这样可行么？不妨看看。
#include <stdio.h>
int main(void) {
int a;
int b;
int c;
long long rv;
while (scanf("%d %d %d", &a, &b, &c) == 3) {
rv = a + b + c;
printf("%lld\n", rv);
}
return 0;
}
我们用2147483647 1 1测试后发现结果为-2147483647。显然这一方案也不成，不过我们得知道为什么不成才能继续给出新的方案。这个方案就在于rv = a + b + c这条语句上，这里有一个原则我们必须先明了，那就是ANSI C在’一般算术运算’的时候采用’值保留’的原则，这区别于K&R C的’无符号保留’原则，我们下面具体分析一下：
a = 2147483647(d) = 0x7FFFFFFF;
b = 1(d) = 0×00000001;
c = 1(d) = 0×00000001;
a + b + c = 0×80000001;
那么0×80000001转为为十进制整型值是多少呢？这里有人认为是-1(d)，这当然不对，我们该如何通过这个0×80000001找到其对应的十进制值呢？我们知道采用二进制补码方式正整数d对应的-d的计算方法为：-d = (~d + 1); 所以我们通过-d求d就可以这样做：
0×80000001 – 1(d) = 0×80000001 – 0×00000001 = 0×80000000;
0×80000000逐位取反得到0x7FFFFFFF, 而0x7FFFFFFF = 2147483647(d)，所以我们得出0×80000001 = -2147483647(d)。
这样rv = a + b + c就变成了rv = -2147483647(d)，同样是’值保留’，那么一个long long类型的rv转换为-2147483647(d)后的’位模式’该是什么样子的呢？其计算方法为(~2147483647(d) + 1)，即(~0x000000007FFFFFFF + 1)，即0xFFFFFFFF80000001，这是个负数，我们要得到其真实值，还得需像上面的计算方式计算：
0xFFFFFFFF80000001 – 1(d) = 0xFFFFFFFF80000001 – 0×0000000000000001 = 0xFFFFFFFF80000000;
0xFFFFFFFF80000000逐位取反得到0x000000007FFFFFFF, 而0x000000007FFFFFFF = 2147483647(d)，所以rv = -2147483647(d)
[方案三]
我们知道上面的问题是由于在不同类型间依照’值保留’原则转型造成的，那么我们大可这么做：
int main(void) {
long long a;
long long b;
long long c;
while (scanf("%lld %lld %lld", &a, &b, &c) == 3) {
printf("%lld\n", a + b + c);
}
return 0;
}
在在线测试系统提交后，状态’Accepted’，至此问题解决，当然问题的解决方法可以有很多种，我想这种是最简单的方法之一了。
怎么样，其实每道ACM题的背后都会有一些’基础理论’在支撑，所以多多做ACM的练习是大有裨益的，上面的数制转换我以前也是很糊涂，就是因为在此题上的思考才让我’豁然开朗’^_^。
评论