● 如何写ACM程序 zZ - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: selahx (宿醉未散，早梦半醒), 信区: ACMICPC
标  题: 如何写ACM程序 zZ
发信站: 荔园晨风BBS站 (2005年04月23日12:32:00 星期六), 站内信件

　　直到三年前，我已经在14吋，60Hz的显示器前坐了七年，不少人想知道为什么我的视力
并没有下降，我说，这是用眼习惯的问题。我并不是ACM高手，但我写程序很快，所以，在
组队比赛中，我通常可以在前两到三个小时十分嚣张（换句话说，剩下的时间……），因为
此时是快速地将简单题目解决的时候。两件事情，同一道理，那就是养成良好的习惯。
　　余世伟说，成功人士从小就养成了成功的习惯。我说，要搞好ACM，首先要养成良好的
编程习惯。
　　下面的言论全部基于我自己对ACM编程的理解，只代表个人观点。注意，这里我只谈
“编程”，本文的内容与算法无关，仅仅关注于如何把ACM程序写好。另外一点是，我现在
说的是“ACM编程”，不是开发软件时的程序设计，尽管两者相比，我更擅长后者，但我写
此文的目的并不是讲如何写软件。
一、ACM程序的特点
　　1、没有任何用户界面，当然更没有GUI。写ACM程序的时候，你需要关注的仅仅是题目
要求的Input和Output，忘掉与用户界面相关的一切东西。
　　2、几乎是面向过程的。除非程序的结构很复杂，否则你不需要考虑从面向对象的角度
来思考程序的设计，这只会浪费掉宝贵的比赛时间。
二、定式
　　所谓定式，就是固定的程序写法。ACM编程很强调定式，从最基本的输入/输出，到二分
搜索，DFS，BFS，再到网络流、二部图匹配，一招一式都有讲究。这些都是将你的思想实现
为程序的基本元素。
　　★★★在精华区中有一些这方面的文章，请一定看看★★★。
　　“定式”在ACM中是初学者容易忽视，高手十分重视的东西。很多人问，我很快就有了
想法，但就是写不出程序，这是怎么回事呢？答案就是你没有熟悉各种定式及其变化。讲到
这里，大家很容易联想起围棋中的“星位定式”，是的，道理是一样的。
　　不少人认为，“定式”就是熟记常用的程序段。这只说对了一小半。死记程序只能记住
一堆代码，遇到原封不动的应用当然好，但这种可能性并不大。所以，熟悉定式的意思并不
是背程序，而是透彻地理解程序的“道”。可能这样说太玄了，所以我换一种通俗一些的说
法。所谓“道”，在这里就是程序的原理。
　　拿二分搜索来说，在一个有序(比如升序)的数组array里搜索的标准程序应该是这样：
// value是我们要找的值
int array[LEN];
int low = 0, high = LEN;
while (low < high)
{
    int m = (low + high) / 2;
    // 如果找到，则返回value在array中的位置
    if (array[m] == value)
        return m;
    // 当前中点的值比要找的值小，说明value的位置在m的右边
    if (array[m] < value)
        low = m;
    else
        high = m;
}
// 没找到则返回-1，或负值
return -1;
　　这个程序相信很多人都写过，即使没有写过，也看过不止一遍。二分搜索是常用的定式
之一，能够熟背这段程序并不代表已经掌握这一定式。因为“熟背”只是复制了代码，
“道”被忽略了。现在，我们一起来看看这小小的程序段里有些什么：
　　1、条件：有序序列。很多人用二分搜索的时候随便拿到一个序列就开始搜，错了也不
知道怎么回事，原因就是忽视了这一重要条件。
　　2、边界：下界和上界。边界的选择决定了搜索的正确性和效率。下界和上界过于接近
，可能搜不到结果；过于远离，可能超时（O(logN)的复杂度并不代表“永不超时”）。
　　3、过程：与中点相关的技术。这里最重要的是中点移动的方向与序列升/降序的关系。
当序列为升序时，中点的移动方向就像上面一样，但如果为降序，方向就要反过来。也许有
人又要将这个背下来了，如果是这样，你的大脑里需要装硬盘了，因为像这类需要背的东西
太多了。死背是不行的，理解才是正道。正如注释里写的那样，决定中点的移动方向是
value的位置与中点的相对位置。这里我不再多讲，因为理解这一点并不困难。
　　4、序列：广义的序列。二分搜索的对象是“序列”，这个序列是什么呢？数组当然是
序列，但更一般地，一个单调函数也是符合要求的序列，或者一本英文词典中的所有单词也
是符合要求的序列（因为这些单词是有序的）。理解序列的含义是灵活运用二分搜索的基础
。
　　5、大小：大小的比较。虽然程序里写的是“<”，但我们应该认识到它并不仅仅表示数
的比较，在广义情况下，它代表了序列中两个元素的先后顺序。比如，在“军衔”序列（显
然是一个有序序列）中，“军长”在“师长”的前面，但它们的关系并不能简单地用“<”
来表示。
　　6、终点：搜索何时终止。当下界和上界重合时，搜索终止，因为此时中点将不再移动
。
　　以上就是二分搜索中道之所在。理解以上6点，以后遇到二分搜索的应用，便能融会贯
通，同时，你也能准确地判断对于某一问题，能否用二分搜索来做，或怎样转换为二分搜索
来做。
　　遇到算法后，请先分析一下它的定式是什么，理解“道”，不要死背代码，切记，
切记。
三、擅用“高级货”
　　“高级货”是我的口头禅，大概的意思就是很方便的库、函数等。
　　scanf、printf（包括sscanf、sprintf）是十分强大的，这是我为什么一直不用
cin/cout的原因。希望大家一定要把scanf、printf支持的每一个“%”开头的定义弄清楚，
你会发现做题时十分有用。
　　STL也是高级货之一，它会给你带来很多方便。STL博大精深，专门花大量时间全部弄懂
在目前是不值得的，但你至少要会用以下的东西：vector, deque, map, set, pair（pair
是C++提供的）, sort, next_permutation。但话又说回来，如果OJ的编译器没有对STL进行
优化，对于时间要求很严格的题目最好不要用。
四、写简单的程序
　　这一点是大多数人忽视的。晦涩的程序并不代表你的编程能力很强，只表示你并不想让
我们和你自己读懂你的程序。
　　我们看看下面的例子，这是一行求a, b, c, d四个整型数中的最大值的程序：
    printf("%d\n", ((a > b ? a : b) > c ? (a > b ? a : b) : c) > d ? ((a > b ? a
: b) > c ? (a > b ? a : b) : c) : d);
    晕了吧？事实上，大家写的程序并没有这么不可读，但原理是一样的。
    复杂的程序难以调试。相对于简单的程序而言，复杂的程序往往隐藏着更加不易被发现
的错误，在短短的5个小时里，简单的程序在调试时更加有优势。
    所以，请尽量将你的程序进行“简单化拆解”。下面，我举一些“简单化拆解”的例
子：
    原程序：
    while (scanf("%d", &n), n)
    // 当n == 0时循环结束，这种用法通常用来显示编程者对逗号表达式的“深刻理解”
    拆解：
    while (true)
    {
        scanf("%d", &n);
        if (n == 0)
            break;
    }
    原程序：
    for (i = 0; i < units.size(); i++)
    // units是vector<int>，它的size方法是内联函数，但我们这里关注的不是效率，是
可读性
    拆解：
    // 引用一个变量使调试变得方便，因为你可以在for之前加上printf("%d\n", nCount
)之类的调试代码
    int nCount = units.size();
    for (i = 0; i < nCount; i++)
    相似的还有：
    char *pStr = new char[strlen(pAnotherStr) + 1];
    拆解为：
    size_t len = strlen(pAnotherStr);
    char *pStr = new char[len + 1];
    原程序：
    struct some_three
    {
        const char *pszName1;
        const char *pszName2;
    };
    struct some_two
    {
        some_three three;
    };
    struct some_one
    {
        some_two two;
    }someOne;
    if (strlen(someOne.two.three.pszName1) > strlen(someOne.two.three.pszName2))
        puts(someOne.two.three.pszName1);
    else
        puts(someOne.two.three.pszName2);
    拆解为：
    const char *p1 = someOne.two.three.pszName1, *p2 = someOne.two.three.pszName
2;
    size_t len1 = strlen(p1), len2 = strlen(p2);
    if (len1 > len2)
        puts(p1);
    else
        puts(p2);
    除了拆解之外，请不要写那种不能一眼看出行为的程序，就像这样：
    if (a + b + c > 0 ? 1 : 0) {...} // 三元运算符的第一段是什么？
    if (a || b && c || d) {...} // “&&”与“||”哪个优先级高？
    而是写成你需要的，更加明了的形式：
    if (a + b + c > 0) {...} else {...}
    if ((a || b) && (c || d)) {...}
    简单的程序并不会使你丢脸，相反，你化繁为简的能力将赢得大家的尊敬和宝贵的调试
时间。
五、注意程序版式
　　风格良好的程序使人心情愉快；风格糟糕的程序充满怨念，让人觉得窒息。在你还没有
习惯于写出版式混乱的程序之前，请尽量要求自己按照规范的版式写程序。关于程序版式的
规范，我在这里不再重复说明，请查阅相关资料。

　　写程序也有很多讲究。既然ACM比赛不仅需要思维，而且需要将思维转化为程序，那么
我们可以认为写程序是ACM比赛中十分重要的过程。养成良好的编程习惯并不容易，但请要
求自己这样做。

--

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.64.1]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.39.3.80]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店