《2023年算法竞赛入门经典作者刘汝佳》由会员分享，可在线阅读，更多相关《2023年算法竞赛入门经典作者刘汝佳（23页珍藏版）》请在金锄头文库上搜索。
1、算法竞赛-入门经典-作者刘汝佳.doc第1部分 语 言 篇第1章 程序设计入门学习目的 熟悉C语言程序的编译和运营 学会编程计算并输出常见的算术表达式的结果 掌握整数和浮点数的含义和输出方法 掌握数学函数的使用方法 初步了解变量的含义 掌握整数和浮点数变量的声明方法 掌握整数和浮点数变量的读入方法 掌握变量互换的三变量法 理解算法竞赛中的程序三步曲：输入、计算、输出 记住算法竞赛的目的及其对程序的规定计算机速度快，很适合做计算和逻辑判断工作。本章一方面介绍顺序结构程序设计，其基本思绪是：把需要计算机完毕的工作提成若干个环节，然后依次让计算机执行。注意这里的“依次”二字环节之间是有先后顺序的。这
2、部分的重点在于计算。接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读 本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图 快假如没有足够的时间用来实践，那么学得快，忘得也快。（为帮助没有分值的朋友能下载，特此修改文档，以免上传不了）1.1 算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。程序1-1 计算并输出1+2的值#includeint main() printf(%dn, 1+2); retu
3、rn 0;这是一段简朴的程序，用于计算1+2的值，并把结果输出到屏幕。假如你不知道如何编译并运营这段程序，可阅读附录或向指导教师求助。即使你不明白上述程序除了“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;注意，百分号后面是个小数点，然后是数字1，再然后是小写字母l
5、，最后是小写字母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的答案就很难简朴解释了真正因素涉及整数和浮点数编码，相信多数初学者对此都不感爱好。因素并不重要，重要的是规范：根据规范做事情，则一切尽在掌握中。提醒1-1：整数值用%d输出，实数用%lf输出 从真
6、正的语言规范来说，这个说法也有一点小问题，但是在算法竞赛中可以完全忽略。这里的“整数值”指的是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;相信读者不难把它翻译成数学表达式：。尽管如此，读者也许还是有一些疑惑：5-0.1的值是什么？“整数-浮点数”是整数还是浮点数？此外，多余来的#include是做什么用的？第1个问题相信读者可以“猜到”结果：整数-浮点数=浮点数。但其实这个说法并不准确。确切的说法是：整数先“变”成浮点数，然后浮点数-浮点数=浮点数。第2个问题的答案是：由于程序1-3中用到了数学函数sqrt。数学函数sq
8、rt(x)的作用是计算x的算术平方根（若不信，可输出sqrt(9.0)的值试试）。一般来说，只要在程序中用到了数学函数，就需要在程序最开始的地方包含头文献math.h，并在编译时连接数学库。假如你不知道如何编译并运营这段程序，可阅读附录或向指导教师求助。1.2 变量及其输入1.1节的程序虽好，但有一个遗憾：计算的数据是事先拟定的。为了计算1+2和2+3，我们不得不编写两个程序。可不可以让程序读取键盘输入，并根据输入内容计算结果呢？答案是肯定的。程序如下：程序1-4 A+B问题#includeint main() int a, b; scanf(%d%d, &a, &b); printf(%dn
9、, a+b); return 0;该程序比1.1节的复杂了许多。简朴地说，第一条语句“int a, b”声明了两个整型（即整数类型）变量a和b，然后读取键盘输入，并放到a和b中。注意a和b前面的&符号千万不要漏掉，不信可以试试 在学习编程时，“明知故犯”是有益的：起码你知道了错误时的现象。这样，当你真的不小心犯错时，可以通过现象猜测到也许的因素。现在，你的程序已经读入了两个整数，可以在表达式中自由使用它们，就好比使用12、597这样的常数。这样，表达式a+b就不难理解了。提醒1-3：scanf中的占位符和变量的数据类型应一一相应，且每个变量前需要&符号。可以暂时把变量理解成“存放值的场合”，或
10、者形象地认为每个变量都是一个盒子、瓶子或箱子。在C语言中，变量有自己的数据类型，例如int型变量存放整数值，而double型变量存放浮点数值（专业的说法是“双精度”浮点数）。假如硬要把浮点数值塞给一个int型变量，将会丢失部分信息我们不推荐这样做。下面来看一个复杂一点的例子。例题1-1 圆柱体的表面积输入底面半径r和高h，输出圆柱体的表面积，保存3位小数，格式见样例。样例输入：3.5 9样例输出：Area = 274.889【分析】圆柱体的表面积由3部分组成：上底面积、下底面积和侧面积。由于上下底面积相等，完整的公式可以写成：表面积=底面积2+侧面积。根据平面几何知识，底面积=，侧面积=。不难
11、写出完整程序：程序1-5 圆柱体的表面积#include#includeint main() const double pi = 4.0 * atan(1.0); double r, h, s1, s2, s; scanf(%lf%lf, &r, &h); s1 = pi*r*r; s2 = 2*pi*r*h; s = s1*2.0 + s2; printf(Area = %.3lfn, s) return 0;这是本书中第一个完整的“竞赛题目”，由于和正规比赛同样，题目中包含着输入输出格式规定，尚有样例数据。大多数的算法竞赛包含如下一些相同的“游戏规则”。一方面，选手程序的执行是自动完毕的，
12、没有人工干预。不要在用户输入之前打印提醒信息（例如“Please input n:”），这不仅不会为程序赢得更高的“界面和谐分”，反而会让程序丢掉大量的（甚至所有的）分数这些提醒信息会被当作输出数据的一部分。例如刚才的程序假如加上了“和谐提醒”，输出信息将变成：Please input n:Area = 274.889比标准答案多了整整一行！另一方面，不要让程序“按任意键退出”（例如调用system(“pause”)，或者加一个多余的getchar()），由于不会有人来“按任意键”的。不少初期的C语言教材会建议在程序的最后加这样一条语句来“观测输出结果”，但注意千万不要在算法竞赛中这样做。提醒
13、1-4：在算法竞赛中，输入前不要打印提醒信息。输出完毕后应立即终止程序，不要等待用户按键，由于输入输出过程都是自动的，没有人工干预。在一般情况下，你的程序不能直接读取键盘和控制屏幕：不要在算法竞赛中使用getch()、getche()、gotoxy()、clrscr()（初期的教材中也许会介绍这些函数）。提醒1-5：在算法竞赛中不要使用头文献conio.h，涉及getch()、clrscr()等函数。最后，最容易忽略的是输出的格式：在很多情况下，输出格式是非常严格的多一个或者少一个字符都是不可以的！提醒1-6：在算法竞赛中，每行输出均应以回车符结束，涉及最后一行。除非特别说明，每行的行首不应有
14、空格，但行末通常可以有多余空格。此外，输出的每两个数或者字符串之间应以单个空格隔开。总结一下，算法竞赛的程序应当只做3件事情：读入数据、计算结果、打印输出。不要打印提醒信息，不要在打印输出后“暂停程序”，更不要尝试画图、访问网络等与算法无关的任务。回到刚才的程序，它多了几个新东西。一方面是“const double pi = 4.0 * atan(1.0);”。这里也声明了一个叫pi的“符号”，但是const关键字表白它的值是不可以改变的pi是一个真正的数学常数 有的读者也许会用math.h中定义的常量M_PI，但其实这个常数不是ANSI C标准的。不信的话用gcc-ansi编译试试。提醒1-
15、7：尽量用const关键字声明常数。接下来是s1 = pi * r * r。这条语句应当如何理解呢？“s1等于pi*r*r”吗？并不是这样的。不信，你把它换成“pi * r * r = s1”试试，编译器会给犯错误信息：invalid lvalue in assignment。假如这条语句真的是“两者相等”的意思，为什么不允许反着写呢？事实上，这条语句的学术说法是赋值（assignment），它不是一个描述，而是一个动作。它的确切含义是：先把“等号”右边的值算出来，然后塞到左边的变量中。注意，变量是“喜新厌旧”的，即新的值将覆盖本来的值，一旦被赋了新的值，变量中本来的值就丢失了。提醒1-8：赋值是个动作，先计算右边的值，再赋给左边的变量，覆盖它本来的值。最后是那个“Area = %.3lfn”，它的用法很容易被猜到：只有以%开头的部分
