Programming Challenges 第一章 Getting Started 读书笔记

本书配套网站

if your program is found guilty of having a wrong answer, the judge will not show you which test case it failed on, or give you any additional hints as to why it failed. This is why it is so essential to review the specifications carefully. Even when you may be sure that your program is correct, the judge may keep saying no. Perhaps you are overlooking a boundary case or assuming something which just ain’t so. Resubmitting the program without change does you absolutely no good. Read the problem again to make sure it says what you thought it did.

Each program must read the test data from the standard input and print the results to the standard output. Programs are not allowed to open files or to execute certain system calls.

比较：
// C
#include
int main() {
    long p,q,r;
    while (scanf("%ld %ld",&p,&q)!=EOF) {
        if (q>p) r=q-p;
        else r=p-q;
        printf("%ld\n",r);
    }
}
// C++
#include
void main()
{
    long long a,b,c;
    while (cin>>a>>b) {
        if (b>a)
          c=b-a;
        else
          c=a-b;
        cout << c << endl；
    }
}

在编写有关input, output的程序时，可以以他们为模板。

It is important to realize how much power there is in what you already know. In
principle, every interesting algorithm/program can be built from what you learn in a first programming course. The powerful features of modern programming languages are not really necessary to build interesting things – only to do them in cleaner, better ways.

To put it another way, one becomes a good writer not by learning additional vocabulary words but by finding something to say. After one or two programming courses, you know all the words you need to make yourself understood. The problems in this book strive to give you something interesting to say.

The sign of a mature professional is keeping the simple jobs simple. You may have recently learned about balanced binary search trees, exception handling, parallel processing, and various models of object inheritance. These are all useful and important subjects. But they are not necessarily the best way to get a correct program working for a simple job.

Be familiar with the basic primitive data types built into your programming language. 常见的三种types： arrays, multidimensional arrays, records.

对于arrays的处理，一个比较有用的技术是sentinels。参见下面的例子：
// version 1
i=n;
while ((a[i]>=x) && (i>=1)) {
    a[i] = a[i-1];
    i=i-1;
}
a[i+1] = x;

// version 2
i=n;
a[0] = - MAXINT;
while (a[i] >= x) {
    a[i] = a[i-1];
    i=i-1;
}
a[i+1] = x;
比较两个版本之间的区别，你就会发现sentinel的作用了。

这一节所讲的主要内容就是要让我们尽量使用简单的结构，如果他们可以完成我们所需的任务的话。为了说明这个问题，作者举了存储point的例子。对于point的存储，我们可以使用两种方法，一是使用array。比如array[n][2]可以用于存储n个2维的节点。另一种方法是定义一个record: struct point {int x, y;}; 当然第二种方法会比较容易理解。但是考虑我们要表示不只二维的节点。对于array这种表示法来说，我们只需将2改为m（维数），但是对于record来说，我们就需要在struct中定义m个变量。并且，考虑一下函数如果是利用struct的话，应该如何来编写:
// 计算两点间的距离。
typedef int point[DIMENSION];
double distance(point a, point b)
{
    int i;
    double d=0.0;
    for (i=0; i
        d=d+ (a[i]-b[i]) * (a[i]-b[i]);
    return( sqrt(d) );
}