算法竞赛-入门经典-作者刘汝佳

算法竞赛入门经典目录目录 (110)第1章程序设计入门 (112)1.1 算术表达式 (112)1.2 变量及其输入 (114)1.3 顺序结构程序设计 (117)1.4 分支结构程序设计 (120)1.5 小结与习题 (123)1.5.1 数据类型实验 (123)1.5.2 scanf输入格式实验 (123)1.5.3 printf语句输出实验 (123)1.5.4 测测你的实践能力 (123)1.5.5 小结 (124)1.5.6 上机练习 (124)第2章循环结构程序设计 (110)2.1 for循环 (110)2.2循环结构程序设计 (113)2.3 文件操作 (116)2.4 小结与习题 (119)2.4.1输出技巧 (119)2.4.2浮点数陷阱 (120)2.4.3 64位整数 (120)2.4.4 C++中的输入输出 (120)2.4.5小结 (121)2.4.6 上机练习 (122)第4章函数和递归 (110)4.1 数学函数 (110)4.1.1 简单函数的编写 (110)4.1.2 使用结构体的函数 (111)4.1.3应用举例 (111)4.2 地址和指针 (114)4.2.1 变量交换 (114)4.2.2 调用栈 (115)4.2.3 用指针实现变量交换 (117)4.2.4初学者易犯的错误 (118)4.3 递归 (119)4.3.1 递归定义 (119)4.3.2递归函数 (120)算法竞赛入门经典4.3.3 C语言对递归的支持 (120)4.3.4 段错误与栈溢出 (122)4.4 本章小结 (123)4.4.1 小问题集锦 (123)4.4.2小结 (124)第6章数据结构基础 (1)6.1 栈和队列 (1)6.1.1 卡片游戏 (1)6.1.2铁轨 (2)6.2 链表 (4)6.2.1 初步分析 (4)6.2.2链式结构 (6)6.2.3对比测试 (7)6.2.4随机数发生器 (8)6.3 二叉树 (9)6.3.1 小球下落 (9)6.3.2层次遍历 (10)6.3.3 二叉树重建 (14)6.4 图 (15)6.4.2走迷宫 (16)6.4.3拓扑排序 (18)6.4.4欧拉回路 (18)6.5训练参考 (19)第8章高效算法设计 (1)8.1 算法分析初步 (1)8.1.1 渐进时间复杂度 (1)8.1.2上界分析 (2)第1章程序设计入门第1部分语言篇第1章程序设计入门学习目标☑熟悉C语言程序的编译和运行☑学会编程计算并输出常见的算术表达式的结果☑掌握整数和浮点数的含义和输出方法☑掌握数学函数的使用方法☑初步了解变量的含义☑掌握整数和浮点数变量的声明方法☑掌握整数和浮点数变量的读入方法☑掌握变量交换的三变量法☑理解算法竞赛中的程序三步曲：输入、计算、输出☑记住算法竞赛的目标及其对程序的要求计算机速度快，很适合做计算和逻辑判断工作。

本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。

注意这里的“依次”二字——步骤之间是有先后顺序的。

这部分的重点在于计算。

接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。

本章内容不复杂，但是不容忽视。

注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。

千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。

1.1 算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。

程序1-1 计算并输出1+2的值#include<stdio.h>int main(){printf("%d\n", 1+2);return 0;}这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。

如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。

即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。

算法竞赛入门经典下面让我们做4个实验：实验1：修改程序1-1，输出3-4的结果实验2：修改程序1-1，输出5×6的结果实验3：修改程序1-1，输出8÷4的结果实验4：修改程序1-1，输出8÷5的结果直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。

解决方法是：用星号“*”代替乘号，而用正斜线“/”代替除号。

这样，4个实验都顺利完成了。

等一下！实验4的输出结果居然是1，而不是正确答案1.6。

这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。

在C语言中，8/5的确切含义是8除以5所得商值的整数部分。

同样地，（-8）/5的值是-1，不信可以自己试试。

那么如果非要得到8÷5=1.6的结果怎么办？下面是完整的程序。

程序1-2 计算并输出8/5的值，保留小数点后1位#include<stdio.h>int main(){printf("%.1lf\n", 8.0/5.0);return 0;}注意，百分号后面是个小数点，然后是数字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的答案就很难简单解释了——真正原因涉及整数和浮点数编码，相信多数初学者对此都不感兴趣。

原因并不重要，重要的是规范：根据规范做事情，则一切尽在掌握中。

第1章 程序设计入门提示1-1：整数值用%d 输出，实数用%lf 输出。

这里的“整数值”指的是1+2、8/5这样“整数之间的运算”。

只要运算符的两边都是整数，则运算结果也会是整数。

正因为这样，8/5的值才是1，而不是1.6。

8.0和5.0被看作是“实数”，或者说得更专业一点，叫“浮点数”。

浮点数之间的运算结果是浮点数，因此8.0/5.0=1.6也是浮点数。

注意，这里的运算符“/”其实是“多面手”，它既可以拿来做整数除法，又可以拿来做浮点数除法。

提示1-2：整数/整数=整数，浮点数/浮点数=浮点数。

这条规则同样适用于加法、减法和乘法，不过没有除法这么容易出错——毕竟整数乘以整数的结果本来就是整数。

算术表达式可以和数学表达式一样复杂，例如：程序1-3 复杂的表达式计算#include<stdio.h>#include<math.h>int main(){printf("%.8lf\n", 1+2*sqrt(3)/(5-0.1));return 0;}相信读者不难把它翻译成数学表达式：150.1+-。

尽管如此，读者可能还是有一些疑惑：5-0.1的值是什么？“整数-浮点数”是整数还是浮点数？另外，多出来的#include<math.h>是做什么用的？第1个问题相信读者能够“猜到”结果：整数-浮点数=浮点数。

但其实这个说法并不准确。

确切的说法是：整数先“变”成浮点数，然后浮点数-浮点数=浮点数。

第2个问题的答案是：因为程序1-3中用到了数学函数sqrt 。

数学函数sqrt(x )的作用是计算x 的算术平方根（若不信，可输出sqrt(9.0)的值试试）。

一般来说，只要在程序中用到了数学函数，就需要在程序最开始的地方包含头文件math.h ，并在编译时连接数学库。

如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。

1.2 变量及其输入1.1节的程序虽好，但有一个遗憾：计算的数据是事先确定的。

为了计算1+2和2+3，我们不得不编写两个程序。

可不可以让程序读取键盘输入，并根据输入内容计算结果呢？答案是肯定的。

程序如下：算法竞赛入门经典程序1-4 A+B问题#include<stdio.h>int main(){int a, b;scanf("%d%d", &a, &b);printf("%d\n", a+b);return 0;}该程序比1.1节的复杂了许多。

简单地说，第一条语句“int a, b”声明了两个整型（即整数类型）变量a和b，然后读取键盘输入，并放到a和b中。

注意a和b前面的&符号——千万不要漏掉，不信可以试试①。

现在，你的程序已经读入了两个整数，可以在表达式中自由使用它们，就好比使用12、597这样的常数。

这样，表达式a+b就不难理解了。

提示1-3：scanf中的占位符和变量的数据类型应一一对应，且每个变量前需要&符号。

可以暂时把变量理解成“存放值的场所”，或者形象地认为每个变量都是一个盒子、瓶子或箱子。

在C语言中，变量有自己的数据类型，例如int型变量存放整数值，而double型变量存放浮点数值（专业的说法是“双精度”浮点数）。

如果硬要把浮点数值塞给一个int型变量，将会丢失部分信息——我们不推荐这样做。

下面来看一个复杂一点的例子。

例题1-1 圆柱体的表面积输入底面半径r和高h，输出圆柱体的表面积，保留3位小数，格式见样例。

样例输入：3.5 9样例输出：Area = 274.889【分析】圆柱体的表面积由3部分组成：上底面积、下底面积和侧面积。

由于上下底面积相等，完整的公式可以写成：表面积=底面积×2+侧面积。

根据平面几何知识，底面积=2Rπ，侧面积=2rhπ。

不难写出完整程序：程序1-5 圆柱体的表面积#include<stdio.h>#include<math.h>int 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 = %.3lf\n", s)return 0;}这是本书中第一个完整的“竞赛题目”，因为和正规比赛一样，题目中包含着输入输出格式①在学习编程时，“明知故犯”是有益的：起码你知道了错误时的现象。