第1部分 语言篇.doc

1、第 1 部分 语 言 篇第 1 章 程序设计入门学习目标 熟悉 C 语言程序的编译和运行 学会编程计算并输出常见的算术表达式的结果 掌握整数和浮点数的含义和输出方法 掌握数学函数的使用方法 初步了解变量的含义 掌握整数和浮点数变量的声明方法 掌握整数和浮点数变量的读入方法 掌握变量交换的三变量法 理解算法竞赛中的程序三步曲：输入、计算、输出 记住算法竞赛的目标及其对程序的要求计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字步骤之间是有先后顺序的。这部分的重点在于计算。接下来介

2、绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读 本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图 快如果没有足够的时间用来实践，那么学得快，忘得也快。1.1 算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。程序 1-1 计算并输出 1+2 的值#includeint main()算法竞赛入门经典2printf(“%dn“, 1+2);return 0;这是一段简单的程序，用于计算 1+2 的值，并把结果

3、输出到屏幕。如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码它们看上去工作情况良好。下面让我们做 4 个实验：实验 1：修改程序 1-1，输出 3-4 的结果实验 2：修改程序 1-1，输出 56 的结果实验 3：修改程序 1-1，输出 84 的结果实验 4：修改程序 1-1，输出 85 的结果直接把“1+2”替换成“3+4 ”即可顺利解决实验 1，但读者很快就会发现：无法在键盘上找到乘号和除号。解决方法是：用星号“*”代替乘号，而用正斜线“/”代

4、替除号。这样，4 个实验都顺利完成了。等一下！实验 4 的输出结果居然是 1，而不是正确答案 1.6。这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。在 C 语言中，8/5 的确切含义是 8 除以 5 所得商值的整数部分。同样地，（ -8）/5 的值是-1，不信可以自己试试。那么如果非要得到 85=1.6 的结果怎么办？下面是完整的程序。程序 1-2 计算并输出 8/5 的值，保留小数点后 1 位#includeint main()printf(“%.1lfn“, 8.0/5.0);return 0;注意，百分号后面是个小数点，然后是数

5、字 1，再然后是小写字母 l，最后是小写字母f，千万不能打错，包括大小写 在 C 语言中，大写和小写字母代表的含义是不同的。再来做 3 个实验：实验 5：把%.1lf 中的数字 1 改成 2，结果如何？能猜想出“1”的确切意思吗？如果把小数点和 1 都删除，%lf 的含义是什么？实验 6：字符串%.1lf 不变，把 8.0/5.0 改成原来的 8/5，结果如何？实验 7：字符串%.1lf 改成原来的%d，8.0/5.0 不变，结果如何？实验 5 并不难解决，但实验 6 和实验 7 的答案就很难简单解释了真正原因涉及整数和浮点数编码，相信多数初学者对此都不感兴趣。原因并不重要，重要的是规范：根据

6、第 1 章 程序设计入门 3规范做事情，则一切尽在掌握中。算法竞赛入门经典4提示 1-1：整数 值用%d 输出，实数用%lf 输出 1。这里的“整数值”指的是 1+2、8/5 这样“整数之间的运算”。只要运算符的两边都是整数，则运算结果也会是整数。正因为这样，8/5 的值才是 1，而不是 1.6。8.0 和 5.0 被看作是“实数”，或者说得更专业一点，叫“浮点数”。浮点数之间的运算结果是浮点数，因此 8.0/5.0=1.6 也是浮点数。注意，这里的运算符“/ ”其实是“多面手”，它既可以拿来做整数除法，又可以拿来做浮点数除法。提示 1-2：整数 /整数=整数，浮点数/ 浮点数=浮点数。这条规

7、则同样适用于加法、减法和乘法，不过没有除法这么容易出错毕竟整数乘以整数的结果本来就是整数。算术表达式可以和数学表达式一样复杂，例如：程序 1-3 复杂的表达式计算#include#includeint main()printf(“%.8lfn“, 1+2*sqrt(3)/(5-0.1);return 0;相信读者不难把它翻译成数学表达式： 。尽管如此，读者可能还是有一些疑23150.惑：5-0.1 的值是什么？“整数-浮点数”是整数还是浮点数？另外，多出来的#include是做什么用的？第 1 个问题相信读者能够“猜到”结果：整数-浮点数=浮点数。但其实这个说法并不准确。确切的说法是：整数先“

8、变”成浮点数，然后浮点数-浮点数=浮点数。第 2 个问题的答案是：因为程序 1-3 中用到了数学函数 sqrt。数学函数 sqrt(x)的作用是计算 x 的算术平方根（若不信，可输出 sqrt(9.0)的值试试）。一般来说，只要在程序中用到了数学函数，就需要在程序最开始的地方包含头文件 math.h，并在编译时连接数学库。如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。1.2 变量及其输入1.1 节的程序虽好，但有一个遗憾：计算的数据是事先确定的。为了计算 1+2 和 2+3，我们不得不编写两个程序。可不可以让程序读取键盘输入，并根据输入内容计算结果呢？答案是肯定的。程序如下：

9、1 从真正的语言规范来说，这个说法也有一点小问题，不过在算法竞赛中可以完全忽略。第 1 章 程序设计入门 5程序 1-4 A+B 问题#includeint main()int a, b;scanf(“%d%d“, printf(“%dn“, a+b);return 0;该 程 序 比 1.1 节 的 复 杂 了 许 多 。 简 单 地 说 ， 第 一 条 语 句 “int a, b”声 明 了 两 个 整 型 （ 即整 数 类 型 ） 变 量 a 和 b， 然 后 读 取 键 盘 输 入 ， 并 放 到 a 和 b 中 。 注 意 a 和 b 前 面 的 double r, h, s1, s

10、2, s;1 在学习编程时，“明知故犯”是有益的：起码你知道了错误时的现象。这样，当你真的不小心犯错时，可以通过现象猜测到可能的原因。算法竞赛入门经典6scanf(“%lf%lf“, s1 = pi*r*r;s2 = 2*pi*r*h;s = s1*2.0 + s2;printf(“Area = %.3lfn“, s)return 0;这是本书中第一个完整的“竞赛题目”，因为和正规比赛一样，题目中包含着输入输出格式规定，还有样例数据。大多数的算法竞赛包含如下一些相同的“游戏规则”。首先，选手程序的执行是自动完成的，没有人工干预。不要在用户输入之前打印提示信息（例如“Please input n

11、:”），这不仅不会为程序赢得更高的“界面友好分”，反而会让程序丢掉大量的（甚至所有的）分数这些提示信息会被当作输出数据的一部分。例如刚才的程序如果加上了“友好提示”，输出信息将变成：Please input n:Area = 274.889比标准答案多了整整一行！其次，不要让程序“按任意键退出”（例如调用 system(“pause”)，或者加一个多余的getchar()），因为不会有人来“按任意键”的。不少早期的 C 语言教材会建议在程序的最后加这样一条语句来“观察输出结果”，但注意千万不要在算法竞赛中这样做。提示 1-4：在算法 竞赛中，输入前不要打印提示信息。 输出完毕后应立即终止程序，

12、不要等待用户按键，因为输入输出过 程都是自动的，没有人工干 预 。在一般情况下，你的程序不能直接读取键盘和控制屏幕：不要在算法竞赛中使用getch()、 getche()、gotoxy() 、 clrscr()（早期的教材中可能会介绍这些函数）。提示 1-5：在算法 竞赛中不要使用头文件 conio.h，包括 getch()、clrscr()等函数。最后，最容易忽略的是输出的格式：在很多情况下，输出格式是非常严格的多一个或者少一个字符都是不可以的！提示 1-6：在算法 竞赛中，每行输出均应以回车符结束，包括最后一行。除非特别说明，每行的行首不应有空格，但行末通常可以有多余空格。另外，输出的每两

13、个数或者字符串之间应以单个空格隔开。总结一下，算法竞赛的程序应当只做 3 件事情：读入数据、计算结果、打印输出。不要打印提示信息，不要在打印输出后“暂停程序”，更不要尝试画图、访问网络等与算法无关的任务。回到刚才的程序，它多了几个新东西。首先是“const double pi = 4.0 * atan(1.0);”。这里也声明了一个叫 pi 的“符号 ”，但是 const 关键字表明它的值是不可以改变的pi 是一个真正的数学常数 1。1 有的读者可能会用 math.h 中定义的常量 M_PI，但其实这个常数不是 ANSI C 标准的。不信的话用 gcc-ansi 编译试试。第 1 章 程序设计

14、入门 7提示 1-7：尽量用 const 关键字声明常数。接下来是 s1 = pi * r * r。这条语句应该如何理解呢？ “s1 等于 pi*r*r”吗？并不是这样的。不信，你把它换成“pi * r * r = s1”试试，编译器会给出错误信息： invalid lvalue in assignment。如果这条语句真的是“二者相等”的意思，为何不允许反着写呢？事实上，这条语句的学术说法是赋值（assignment），它不是一个描述，而是一个动作。它的确切含义是：先把“等号”右边的值算出来，然后塞到左边的变量中。注意，变量是“喜 新 厌 旧 ”的 ， 即 新 的 值 将 覆 盖 原 来 的

15、 值 ， 一 旦 被 赋 了 新 的 值 ， 变 量 中 原 来 的 值 就丢 失 了 。提示 1-8：赋值 是个动作，先计算右边的值，再 赋给左边的变量，覆盖它原来的值。最后是那个“Area = %.3lfn”，它的用法很容易被猜到：只有以% 开头的部分才会被后面的值替换掉，其他部分原样输出。提示 1-9：printf 的格式字符串中可以包含其他可打印符号，打印时原样输出。1.3 顺序结构程序设计例题 1-2 三位数反转输入一个三位数，分离出它的百位、十位和个位，反转后输出。样例输入：127样例输出：721【分析】首先将三位数读入变量 n，然后进行分离。百位等于 n/100（注意这里取的是商

16、的整数部分），十位等于 n/10%10（这里的%是取余数操作），个位等于 n%10。程序如下：程序 1-6 三位数反转（1 ）#includeint main()int n;scanf(“%d“, printf(“%d%d%dn“, n%10, n/10%10, n/100);return 0;此题有一个没有说清楚的细节，即：如果个位是 0，反转后应该输出吗？例如输入是520，输出是 025 还是 25？如果在算法竞赛中遇到这样的问题，可向监考人员询问 1。但是1 如果是网络竞赛，还可以向组织者发信，在论坛中提问或者拨打热线电话。算法竞赛入门经典8在这里，两种情况的处理方法都应学会。第 1 章

17、 程序设计入门 9提示 1-10：算法竞赛的题目应当是严密的，各种情况下的输出均应有严格规定。如果在比赛中发现题目有漏洞，应向相关人 员询问，而尽量不要自己随意假定。上 面 的 程 序 输 出 025， 但 要 改 成 输 出 25 似 乎 会 比 较 麻 烦 我 们 必 须 判 断 n%10 是 不 是0， 但 目 前 还 没 有 学 到 “根 据 不 同 情 况 执 行 不 同 指 令 ”（ 分 支 结 构 程 序 设 计 是 1.4 节 的 主 题 ）。一个解决方法是在输出前把结果储存在变量 m 中。这样，直接用%d 格式输出 m，将输出 25。要输出 025 也很容易，把输出格式变为%

18、03d 即可。程序 1-7 三位数反转（2 ）#includeint main()int n, m;scanf(“%d“, m = (n%10)*100 + (n/10%10)*10 + (n/100);printf(“%03dn“, m);return 0;例题 1-3 交换变量输入两个整数 a 和 b，交换二者的值，然后输出。样例输入：824 16样例输出：16 824【分析】按照题目所说，先把输入存入变量 a 和 b，然后交换。如何交换两个变量呢？最经典的方法是三变量法：程序 1-8 变量交换（1 ）#includeint main()int a, b, t;scanf(“%d%d“,

19、t = a;a = b;b = t;printf(“%d %dn“, a, b);return 0;可以将这种方法形象地比喻成将一瓶酱油和一瓶醋借助一个空瓶子进行交换：先把酱油倒入空瓶，然后将醋倒进原来的酱油瓶中，最后把酱油从辅助的瓶子中倒入原来的醋瓶算法竞赛入门经典10子里。这样的比喻虽然形象，但是初学者应当注意它和真正的变量交换的区别。借助一个空瓶子的目的是：避免把醋直接倒入酱油瓶子直接倒进去，二者混合以后，将很难分开。在 C 语言中，如果直接进行赋值 a=b，则原来 a 的值（酱油）将会被新值（醋）覆盖，而不是混合在一起。当酱油被倒入空瓶以后，原来的酱油瓶就变空了，这样才能装醋。但在 C

20、 语言中，进行赋值 t = a 后，a 的值不变，它只是把值拷贝（即复制）给了变量 t 而已，自身并不会变化。尽 管 a 的 值 马 上 就 会 被 改 写 ， 但 是 从 原 理 上 看 ， t=a 的 过 程 和 “倒 酱 油 ”的 过 程 有 着 本质 区 别 。提示 1-11：赋值 a = b 之后，变量 a 原来的值被覆盖，而 b 的值不变。另一个方法没有借助任何变量，但是较难理解：程序 1-9 变量交换（2 ）#includeint main()int a, b;scanf(“%d%d“, a = a + b;b = a - b;a = a - b;printf(“%d %dn“,

21、 a, b);return 0;这次就不太方便用倒酱油做比喻了：硬着头皮把醋倒在酱油瓶子里，然后分离出酱油倒回醋瓶子？比较理性的方法是手工模拟这段程序，看看每条语句执行后的情况。在顺序结构程序中，程序一条一条依次执行。为了避免值和变量名混淆，假定用户输入的是 a0 和 b0，因此 scanf 语句执行完后 a = a0, b = b0。执行完 a = a+b 后：a = a0+b0, b = b0。执行完 b = a-b 后：a = a0+b0, b = a0。执行完 a = a-b 后：a = b0, b = a0。这样就不难理解两个变量是如何交换的了。这个方法看起来很好（少用一个变量），但实际上很少使用，因为它的适用范围很窄：只有定义了加减法的数据类型才能这么做 1。事实上，笔者并不推荐读者采用这样的技巧实现变量交换：三变量法已经足够好了，这个例子只是帮助读者提高程序阅读能力。提示 1-12：交换两个变量的三变量法适用范围广，推荐使用。那么是不是说，三变量法是解决本题的最佳途径了呢？答案是否定的。多数算法竞赛1 这个思想还有一个“变种”：用异或运算代替加法和减法，它还可以进一步简写成 a=b=a=b。但不建议使用。