《算法竞赛入门经典》——刘汝佳

不念不忘少年蓝@ 2022-08-29 09:33 188阅读 0赞

> “构造性”和“可行性”是计算机学科的两个最根本特征。  
> 比赛的核心是算法

# \#1 语言篇 #

编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读书本，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快—如果没有足够的时间来实践，那么学的快，忘得也快！

## 1.1算数表达式 ##

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

> **提示1-1**：整数值用%d输出，实数用%f输出。  
> **提示1-2**：整数/整数=整数，浮点数/浮点数=浮点数。  
> ![复杂的表达式计算][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70]

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

## 1.2 变量及其输入 ##

> 提示1-3： scanf 中的占位符和变量的数据类型应一一对应，且每个变量前需要加“&”符号。 可以暂时把变量理解成“存放值的场所”。

![圆柱体的表面积][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 1]

> 提示1-4：  
> 在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。  
> 提示1-5：  
> 在算法竞赛中不要使用头文件conio.h, 包含getch(),clrscr()等函数。  
> 提示1-6：  
> 在算法竞赛中，每行输出均应以回车符结束，包括最后一行。除非特别说明，每行的行首不应有空格，单行末通常可以有多余空格。另外，输出的每两个数或者字符串之间应以单个空格隔开。

> 总结：算法竞赛的程序只做3件事：  
> 读入数据，计算结果，打印输出。  
> Const double pi = acos(-1.0); Const 关键字表明它的值是不可以改变的

> 提示1-7： 尽量用const 关键字声明常熟。  
> 提示1-8： 赋值是个动作，先计算右边的值，再赋给左边的变量，覆盖它原来的值。  
> 提示1-9： printf 的格式字符串中可以包含其他可打印符号，打印时原样输出。

## 1.3 顺序结构程序设计 ##

> 提示1-10：算法竞赛的题目应当是严密的，各种情况下的输出均应有严格规定。如果在比赛中发现题目有漏洞，应向相关人员询问，尽量不要自己随意假定。

![变量交换][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 2]

> 提示1-11： 赋值a=b；之后，变量a原来的值被覆盖，而b的值不变。

![变量交换][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 3]

> 提示1-12：可以通过手工模拟的方法理解程序的执行方式，重点在于记录每条语句执行之后各个变量的值。  
> 提示1-13：交换两个变量的三变量法适用范围广，推荐使用。 提示1-14： 算法竞赛是在比谁能更好地解决问题，而不是在比谁学的程序看上去更高级。

![变量交换][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 4]

## 1.4 分支结构程序设计 ##

**提示1-15**：

If语句的一般格式：
    If(条件)
         语句1；
    Else
         语句2；

在C语言中单个整数值也可以表示真假，其中0为假，其他值为真。

> 提示1-17：  
> C语言中逻辑运算符都是短路运算符。一旦能够确定整个表达式的值，就不再继续计算。  
> 提示1-18：  
> 算法竞赛的目标是编程对任意输入均得到正确的结果，而不仅是样例数据。  
> 提示1-19：  
> 如果有多个并列，情况不交叉的条件需要一一处理，可以用else if 语句。  
> 提示1-20：  
> 适当在程序中编写注释不仅能让其他用户更快地搞懂你的程序，还能帮你自己沥青思路。  
> 提示1-21：  
> 可以用花括号把若干条语句整合成一个整体。这些语句仍然按顺序执行。

## 1.5 注解与习题 ##

编译器任务：把人类可以看懂的源代码变成机器可以直接执行的命令。

建议：

> 1.  重视实验
> 2.  学会模仿

# \#2 循环结构程序设计 #

> 提示2-1：  
> for循环的格式为：for（初始化；条件；调整）循环体；  
> 提示2-2：  
> 尽管for循环反复执行相同的语句，但这些语句每次的执行效果往往不同。  
> 提示2-3：  
> 编写程序时，要特别留意“当前行”的跳转和变量的改变。  
> 提示2-4：  
> 建议尽量缩短变量的定义范围。

伪代码：不是真正程序的代码

> 提示2-5： 不拘一格地使用伪代码来思考和描述算法是一种值得推荐的做法。  
> 提示2-6： 把伪代码改写成代码时，一般选择较为容易的任务来完成。

Question：如何判断n是否为完全平方数？  
用“开平方”函数，先求出其平方根，然后看它是否为正数，即用一个int 型变量m存储sqrt（n）四舍五入后的整数，然后判断m×m是否等于n。函数floor（x）返回不超过x的最大整数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 5]  
读者可能会问： 可不可以这样写？

if（ sqrt（ n） ＝ ＝floor（ sqrt（ n） ） ） 
          printf（ "％d\n"， n）；

即直接判断`sqrt（ n）` 是否为整数。 理论上当然没问题， 但这样写不保险， 因为浮点数的运算（ 和函数） 有可能存在误差。  
假设在经过大量计算后， 由于误差的影响， 整数1变成了0.9999999999， floor的结果会是0而不是1。 为了减小误差的影响， 一般改成四舍五入， 即`floor（ x＋ 0.5） (2)`。  
如果难以理解， 可以想象成在数轴上把一个单位区间往左移动0.5个单位的距离。 `floor（ x）` 等于1的区间为`[1， 2）` ， 而`floor（ x＋ 0.5）` 等于1的区间为`[0.5， 1.5）` 。

> **提示2-7**： 浮点运算可能存在误差。在进行浮点数比较时，应考虑浮点误差。  
> ![7744问题][7744]

## 2.2 while、循环和do-while循环 ##

> **提示2-8**;  
> while循环的格式为“while（条件）循环体；”。  
> **提示2-9**：  
> 当需要统计某个事物的个数时，可以用一个变量来充当计数器。  
> **提示2-10**：  
> 不要忘记测试。一个看上去正确的能隐含错误。  
> **提示2-11**：  
> 在观察无法找出错误时，可以用“输出中间结果;”的方法查错。 Int整数的大小：-2147483648～2147483647  
> **提示2-12**：  
> C99并没有规定int类型的确切大小，但在当前流行的竞赛平台中，int都是32位整数。  
> **提示2-13**：  
> long long在linux下的输入输出格式符为%lld，但windows平台中有时为%I64d。为保险起见，可以用后面介绍的C++流，或者编写自定义输入输出函数。  
> ![3n+1问题][3n_1]

> **提示2-14**：  
> do-while循环的格式为“do\{循环体\}while（ 条件） ； ”， 其中循环体至少执 行一次，  
> 每次执行完循环体后判断条件， 当条件满足时继续循环。 只要末6位， 即输出对10的6次方取模。  
> **提示2-15**：  
> 在循环体开始处定义的变量，  
> 每次执行循环体时会重新声明并初始化。  
> **提示2-16**：  
> 要计算只包含加法、 减法和乘法的整数表达式除以正整数n的余数，  
> 可以在每步计算之后对n取余， 结果不变。

![阶乘之和][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 6]

这个程序真正的特别之处在于计时函数clock（ ） 的使用。 该函数返回程序目前为止运行  
的时间。 这样， 在程序结束之前调用此函数， 便可获得整个程序的运行时间。 这个时间除以  
常数CLOCKS\_PER\_SEC之后得到的值以“秒”为单位。

> **提示2-17**： 可以使用time.h和clock（ ） 函数获得程序运行时间。  
> 常数CLOCKS\_PER\_SEC和操作系统相关，  
> 请不要直接使用clock（ ） 的返回值， 而应总是除以CLOCKS\_PER\_SEC。

![输出结果和运行结果表][1ab50cfa17294165a019e19c891df8fd.png]

> **提示2-18**：  
> 很多程序的运行时间与规模n存在着近似的简单关系。 可以通过计时函数来发现或验证这一关系。

## 2.3 算法竞赛中的输入输出框架 ##

> **提示2-19**： 在Windows下， 输入完毕后先按Enter键， 再按Ctrl＋ Z键， 最后再按Enter键， 即可结束输入。  
> 在Linux下， 输入完毕后按Ctrl＋ D键即可结束输入。  
> **提示2-20**： 变量在未赋值之前的值是不确定的。

特别地， 它不一定等于0，在使用之前赋初值。 由于min保存的是最小值， 其初值应该是  
一个很大的数； 反过来， max的初值应该是一个很小的数。 一种方法是定义一个很大的常数， 如INF＝ 1000000000， 然后让max＝ -INF， 而min＝ INF， 另一种方法是先读取第一个整数x， 然后令max＝ min＝ x。  
事实上， 几乎所有算法竞赛的输入数据和标准答案都是保存在文件中的。  
使用文件最简单的方法是使用输入输出重定向， 只需在main函数的入口处加入以下两条  
语句：

freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

**提示2-21**： 请在比赛之前了解文件读写的相关规定： 是标准输入输出（ 也称标准I/O，即直接读键盘、 写屏幕） ， 还是文件输入输出？ 如果是文件输入输出， 是否禁止用重定向方  
式访问文件？

> 例如， 如果题目规定程序名称为test， 输入文件名为test.in， 输出文件名为test.out， 就不 要犯以下错误。  
> 错误1：程序存为t1.c（ 应该改成test.c） 。  
> 错误2： 从input.txt读取数据（ 应该从test.in读取） 。  
> 错误3：从tset.in读取数据（ 拼写错误， 应该从test.in读取） 。  
> 错误4： 数据写到test.ans（ 扩展名错误，应该是test.out） 。  
> 错误5： 数据写到c： `\\contest\\test.out`（ 不能加路径， 哪怕是相对路径。 文件名应该只有8个字符： test.out） 。

![数据统计][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 7]  
**加粗样式**

> **提示2-22**：  
> 在算法竞赛中， 选手应严格遵守比赛的文件名规定， 包括程序文件名和输入输出文件名。 不要弄错大小写， 不要拼错文件名，不要使用绝对路径或相对路径。

这是一份典型的比赛代码， 包含了几个特殊之处：  
重定向的部分被写在了\#ifdef和\#endif中。 其含义是： 只有定义了符号LOCAL， 才编译两条freopen语句。  
输出中间结果的printf语句写在了注释中——它在最后版本的程序中不应该出现， 但是又舍不得删除它（ 万一发现了新的bug， 需要再次用它输出中间信息） 。 将其注释的好处是： 一旦需要时， 把注释符去掉即可。  
上面的代码在程序首部就定义了符号LOCAL， 因此在本机测试时使用重定向方式读写文件。  
如果比赛要求读写标准输入输出， 只需在提交之前删除\#defineLOCAL即可。 一个更好的方法是在编译选项而不是程序里定义这个LOCAL符号（ 不知道如何在编译选项里定义符号的， 这样， 提交之前不需要修改程序， 进一步降低了出错的可能。  
**提示2-23**： 在算法竞赛中， 有经验的选手往往会使用条件编译指令并且将重要的测试语句注释掉而非删除、  
**提示2-24**： 在算法竞赛中， 如果不允许使用重定向方式读写数据， 应使用fopen和fscanf/fprintf进行输入输出。  
**提示2-25**： 在算法竞赛中， 偶尔会出现输入输出错误的情况。 如果程序鲁棒性强， 有时能在数据有瑕疵的情况下仍然给出正确的结果。 程序的鲁棒性在工程中也非常重要。  
**提示2-26**： 在多数据的题目中， 一个常见的错误是： 在计算完一组数据后某些变量没有重置， 影响到下组数据的求解。  
**提示2-27**： 当嵌套的两个代码块中有同名变量时，内层的变量会屏蔽外层变量，有时会引起十分隐蔽的错误。

初学者在求解“多数据输入”的题目时常范的错误，请读者留意。这种问题通常很隐蔽，但也不是发现不了：对于这个例子来说，编译时加一个-Wall 就会看到一条提示：

Warning : unused variable’s’[-Wunused-variable](警告：没有用过的变量’s’)。

**提示2-28**：用编译选项`-Wall` 编译程序时，会给出很多（但不是所有）警告信息，以帮助程序员查错。但这并不能解决所有的问题：有些“错误”程序是合法的，只是动作不是所期望的。

# \#3 数组和字符串 #

## 3.1 数组 ##

**提示3-1**： 语句“`int a[maxn]`”声明了一个包含maxn 个整形变量的数组，即a\[0\],a\[1\], … ,a\[maxn-1\],但不包含a\[maxn\]。Maxn必须是常数，不能是变量。  
**提示3-2**： 在算法竞赛中，常常难以精确计算出需要的数组大小，数组一般会声明得稍大一些。在空间够用的前提下，浪费一点不会有太大影响。  
**提示3-3**： 对于变量n，n++和++都会给n加1，但当它们用在一个表达式中时，行为有所差别：n++会使用加1前得值计算表达式，而++n会使用加1后得值计算表达式。  
只有只有在放外面时，数组a才可以开得很大；放在main函数内时，数组稍大就会异常退出。  
**提示3-4**： 比较大的数组应尽量声明在main函数外，否则程序可能无法运行。  
![开灯问题][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 8]  
![AC][]  
“`memset（a，0，sizeof（a））`”得作用是把数组a清零，它也在string.h中定义。虽然也能用for循环完成相同的任务，但是用memset又方便又快捷。另一个技巧在输出：为了避免输出多余空格，设置了一个标志变量吧first，可以表示当前要输出得变量是否为第一个。第一个变量前不应有空格，但其他变量都有。  
![蛇形填数][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 9]  
**提示3-5**： 可以用“`int a[maxn][maxn]`”生成提个整型得二维数组，其中maxn 和maxn 不必相等。这个数组共有maxn\*maxn个元素，分别为`a[0][0],a[0][1],…, a[0][maxm-1],a[1][0],a[1][1],…,a[1][maxm-1],…,a[maxn-1][0],a[maxn-1][1],…, a[maxn-1] [maxm -1]`。

![分析][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 10]

> **提示3-6**: 可以利用C语言简洁的语法，但前提是保持代码的可读性。

那4条while语句有些难懂，不过十分相似，因此只需介绍其中的第一条：不断向下走，并且填数。我们的原则是：先判断，再移动，而不是走一步以后发现越界了再退回来。这样，则需要进行“预判”，即是否越界，以及如果继续往下走会不会到达一个已经填过的格子。越界只需要判断x+1<n因为y的值并没有修改；下一个格子是（x+1，y），因此只需“a\[x+1\]\[y\]==0”，简写成“!a\[x+1\]\[y\]”（其中“！”是“逻辑非”运算符）。

> **提示3-7**： 在很多情况下，最好是在做一件事之前检查是不是可以做，而不是做完再后悔。因为“悔棋”往往比较麻烦。

细心地读者也许会发现这里的一个“潜在Bug”:如果越界，`x+1会等于n`，`a【x+1】【y】`将访问非法内存！幸运的是，这样的担心是不必要的。“&&”是短路运算符（还记得我们在哪里提到过吗？）。如果`x+1<n`为假，将不会计算“`！a【x+1】【y】`”，也就不会越界了。  
至于为什么是`++tot`而不是`tot++`，留给读者思考。

## 3.2 字符数组 ##

![竖式问题][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 11]  
![分析][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 12]

> **提示3-8**：C语言中的字符型用关键词char表示，它实际存储的是字符的ASCII码。字符常量可以用单引号法表示。在语法上可以把字符当作int型使用。

另一个新内容是“`scanf(“%s”,s)”和scanf(“%d”,&n)`类似，它会读入一个不含空格，TAB和回车符的字符串，存入字符数组s。注意，不是“`scanf(“%s”,&s)`”，s前面没有“&”字符号。  
**提示3-9**： 在“`scanf("%s", s)`”中， 不要在s前面加上“&”符号。 如果是字符串数组`chars[maxn] [maxl]`， 可以用“`scanf("%s", s[i])`”读取第i个字符串。 注意， “`scanf("%s", s)`”遇到空白字符会停下来。  
![竖式问题][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 13]

还有两个函数是以前没有遇到的：`sprint`f和`strchr`。`Strchr`的作用是在一个字符串中查找单个字符，而这个sprintf似曾相识：之前用过`printf`和`fprintf`。没错！这3个函数是“亲兄弟”，printf输出到屏幕，fprintf输出到文件，而sprintf输出到字符串。多数情况下，屏幕总是可以输出的，文件一般也能写（除非磁盘满或者硬件损坏），但字符串就不一样了：应该保证写入的字符串有足够的空间。  
**提示3-10**： 可以用sprintf把信息叔叔到字符串，用法和printf，fprintf类似。但应当保证字符串足够大，可以容纳输出信息。  
**提示3-11**： C语言中的字符串是以“\\0”结尾的字符数组， 可以用strlen(s)返回字符串s中结束标记之前的字符个数。 字符串中的各个字符是`s[0], s[1],…,s[strlen(s)-1]`。  
**提示3-12**： 由于字符串的本质是数组， 它也不是“一等公民”， 只能用strcpy(a, b),strcmp(a, b), strcat(a, b)来执行“赋值”、 “比较”和“连接”操作， 而不能用“=”、 “==”、“<=”、 “+”等运算符。 上述函数都在string.h中声明。  
另一个例子是“`count=count++`”。这里对count++的解释是：count++在表达式中的值是加1之前的值（即原来的值），但计算count++之后count会增加1。问题出现了：这个“”“”稍后再加1”到底是何时进行的呢？如果是计算完复制的右边（即count++）之后就立刻执行，最后count的值不会变（别忘了最后执行的是赋值）；但如果是整个赋值完成之后才加1，最后count的值会比原来多1.如果在理解刚才这段话时感到吃力，最好的方法就是避开它。  
**提示3-13**： 滥用“++”，“–”，“+=”等可以修改变量值的运算符很容易带来隐蔽的错误。建议每条语句最多只能用一次这种运算符，并且所修改的变量在整条语句中只出现一次。  
**提示3-14**： 使用fgetc(fin)可以从打开的文件fin中读取读取一个字符。一般情况下应当在检查它不是EOF再将其转换成char值。从标准输入读取一个字符可以用getchar ,它等价于fgetc（stdin）。

> 这里有个潜在的陷阱：不同操作系统的回车换行符是不一致的。Windows是“\\r”和“\\n”两个字符，linux是“\\n”，而Macos是“\\r”。如果在windows下读取windows文件，fgetc和getchar会把“\\r”吃掉，只剩下“\\n”;但如果要在linux下读取同样一个文件，它们会忠实地先读取“\\r”，然后才是“\\n”。如果编程时不注意，所写程序可能会在某个操作系统上是完美的，但是在另一个操作系统上就错得一塌糊涂。当然，比赛的组织方应该避免在Linux下使用windows格式得文件，但正如前面所强调过的：选手也应该把自己的程序写得更鲁棒，即容错性更好。

**提示3-15**： 在使用fgetc和getchar时，应该避免写出和操作系统相关的程序。  
**提示3-16**： "fgets(buf, maxn, fin)“将读取完整的一行放在字符数组buf中。 应当保证  
buf足够存放下文件的一行内容。 除了在文件结束前没有遇到“\\n”这种特殊情况外， buf总是以“\\n”结尾。 当一个字符都没有读到时， fgets返回NULL。  
**提示3-17**： C语言并不禁止程序读写"非法内存”。 例如， 声明的是char s\[100\]， 完全可以赋值s\[10000\] = ‘a’（ 甚至-Wall也不会警告） ， 但后果自负。  
**提示3-18**： C语言中的gets(s)存在缓冲区溢出漏洞， 不推荐使用。 在C11标准里， 该函数已被正式删除。  
**提示3-19**： 善用常量数组往往能简化代码。 定义常量数组时无须指明大小， 编译器会计算。  
**提示3-20**： 头文件ctype.h中定义的isalpha、 isdigit、 isprint等工具可以用来判断字符  
的属性， 而toupper、 tolower等工具可以用来转换大小写。 如果ch是大写字母， 则ch-'A’就是它在字母表中的序号（ A的序号是0， B的序号是1， 依此类推） ； 类似地， 如果ch是数字，则ch-'0’就是这个数字的数值本身。  
**提示3-21**： 字符还可以直接用ASCII码表示。如果用八进制，应该写成：“\\o”,”\\oo”或”\\ooo”（o为一个八进制数字）；如果用十六进制，应该写成“\\xh”（h为十六进制数字串）。

> 在二进制中，8位最大整数就是8个1，即28-1， 用C语言写出来就是(1<<8)-1。 注意括号是必需的，  
> 因为“<<”运算符的优先级没有减法高。

补码表示法。 计算机中的二进制是没有符号的。 尽管123的二进制值是1111011， -123在计算机内并不表示为-1111011——这个“负号”也需要用二进制位来表示。

> “正号和符号”只有两种情况， 因此用一个二进制位就可以了。 容易想到一个表示“带符号32位整数”的方法： 用最高位表示符号（ 0： 正数；1： 负数） ， 剩下31位表示数的绝对值。 可惜， 这并不是机器内部真正的实现方法。  
> 在笔者的机器上，语句“`printf("%u\n",-1)`”的输出是4294967295(4)。 把-1换成-2、 -3、 -4……后，  
> 很容易总结出一个规律： -n的内部表示是232-n。 这就是著名的“补码表示法”（ `Complement Representation`） 。

**提示3-22**： 在多数计算机内部，，整数采用的是补码表示法。  
为什么计算机要用这样一个奇怪的表示方法呢？前面提到的“符号位+绝对值”的方法哪里不好了？  
答案是：`运算不方便`。  
试想，要计算1+（-1）的值（为了简单起见，假设两个数都是带符号8位整数）。如果用“符号位+绝对值”法，将要计算00000001+10000001，而答案应该是00000000。似乎想不到什么简单的方法进行这个“加法”。但如果采用补码表示，计算的是00000001+11111111，只需要直接相加，并丢掉最高位的进位即可。“符号位+绝对值”还有一个好玩的Bug:存在两种不同的0：一个是吧00000000（正0），一个是10000000（负0）。这个问题在补码表示法中不会出现。  
[http://uva.onlinejudge.org/][http_uva.onlinejudge.org]

# \#4 函数和递归 #

函数是“过程是程序设计”的自然产物，单页产生了局部变量，参数传递方式，递归等诸多新的知识点。  
主要目的在于理解这纷繁复杂的，最后的语法。同时，通过gdb，可以从根本上帮助读者理解，看清事物的本质。

## 4.1 自定义函数和结构体 ##

**提示4-1**：C语言中的数学函数可以定义成“返回类型 函数名（参数列表）｛函数体｝”，其中函数体的最后一条语句应该是“return表达式；”。  
**提示4-2**： 函数的参数和返回值最好是“一等公民”，如int，char或者double等。其他“非一等公民”作为参数和返回值要复杂一些。如果函数不需要返回值，则返回类型应写成void。

注意：这里的return是一个动作，而不是描述。

**提示4-3**： 如果在执行函数的·过程中碰到了return语句，将直接退出这个函数，不去执行后面的语句。相反，如果在执行过程中始终没有retutrn语句，则会返回一个不确定的值。幸好，-wall可以捕捉到这一可疑情况并产生警告。  
顺便说一句，main函数也是有返回值的！到目前为止，我们总是让它返回0，这个0是什么意思呢？尽管没有专门说明，读者应该已经发现了，main函数是整个程序的入口。换句话说，有一个“其他的程序”来调用这个main函数——如操作系统，IDE，调试器，甚至自动评测系统。这个0代表“正常结束”，即返回给调用者。在算法竞赛中，除了有特殊规定之外，请总是让其返回0，避免评测系统错误地认为程序异常退出了。  
**提示4-4**： 在算法竞赛中，请总是让main函数返回0。  
**提示4-5**： 在C语言中，定义结构体的方法为”struct 结构体名称｛域定义｝;”，注意花括号的后面还有一个分号。  
**提示4-6**：为了使用方便，旺旺用“typedef struct｛域定义；｝类型名；”的方式定义一个新类型名。这样，就可以像原生数据类型一样使用这个自定义类型。  
**提示4-7**： 即使最终答案在所选择的数据类型范围之内，计算的中间结果仍然可能溢出。  
如何避免溢出？  
办法是进行“约分”。  
一个简单的方法是利用n！/m!=(m+1)(m+2)…(n-1)n.虽然不能完全避免中间结果溢出，但对于题目给出的范围已经可以保证得到正确的结果了。  
**提示4-8**： 对复杂的表达式进行化简有时不仅能减少计算量，还能减少甚至避免中间结果溢出。  
**提示4-9**： 建议把谓词（用来判断某事物是否具有某种特性的函数）命名成“is\_xxx”的形式，返回int值，非0表示真能，0表示假。  
**提示4-10**： 编写函数时，应尽量保证该函数能对任何合法参数得到正确的结果。如若不然，应在显著位置标明函数的缺陷，以避免误用。

## 4.2 函数调用与参数传递 ##

![形参与实参][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 14]

程序里有两个变量a，一个在main函数里定义，一个是swap的形参，二者不会混淆吗？不会。函数（包括main函数）的形参和在该函数里定义的变量都被称为该函数的局部变量（local variable）。不同函数的局部变量相互独立，即无法访问其他函数的局部变量。需要注意的是，局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。与此对应的是全局变量（global variable）：此变量在函数外声明，可以在任何时候，由任何函数访问。需要注意的是，应该谨慎使用全局变量。

## 4.2.2 调用栈（call stack） ##

For循环的学习：多演示程序执行的过程，把注意力集中在“当前代码行”的转移和变量值的变化。

调用栈描述的是函数之间的调用关系。它由多个栈帧（stack frame）组成，每个栈帧对应着一个未运行完的函数。栈帧中保存了该函数的返回地址和局部变量，因而不仅能在执行完毕后找到正确的返回地址，还很自然地保证了不同函数间的局部变量互不相干——因为不同函数对应着不同的栈帧。  
**提示4-12**： C语言用调用栈（call stack）来描述函数之间的调用关系。调用栈由栈帧（stack frame）组成，每个栈帧对应着一个未运行完的函数。在gdb中可以用backtrace（简称bt）命令打印所有栈帧信息。若要用p命令打印一个非当前栈帧的局部变量，可以用frame命令选择另一个栈帧。  
![用函数交换变量][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 15]  
**提示4-13**： C语言的变量都是放在内存中的，而内存中的每个字节都有一个称为地址（address）的编号。每个变量都占有一定数目的字节（可用sizeof运算符获得），其中第一个字节的地址称为变量的地址。  
**提示4-14**： 用int\* a声明的变量a是指向int型变量的指针。赋值a=&b的含义是把变量b的地址存放在指针a中，表达式\*a代表a指向的变量，既可以放在赋值符号的左边（左值），也可以放在右边（右值）。

> ***注意***：\*\*a是指“a指向的变量”，而不仅是“a指向的变量所拥有的值”。理解这一点相当重要。例如，*a=a+1就是让a指向的变量自增1.甚至可以把它写成（a）++。注意不要写成a++，因为“++”运算符的优先级高于“取内容”运算符“”，实际上会被解释成*（a++）。 有了指针，C语言变得复杂了很多。一方面，需要了解更多底层的内容才能彻底解释一些问题，包括运行时的地址空间布局，以及操作系统的内存管理方式等。另一方面，指针的存在，是的C语言中变量的说明变得异常复杂——你能轻易地说出用

char * const *（*next）（）

声明的next是什么类型的吗？  
这是一个指向函数的指针，该函数返回一个指针，该函数指向一个只读的指针，此指针指向一个字符变量。

> 算法竞赛的核心是算法，没有必要纠缠如此复杂的语言特性。了解底层的细节是有益的（事实上，前面已经介绍了一些底层细节），但在编程时应尽量避开，只遵守一些注意事项即可。

**提示4-15**： 千万不要滥用指针，这不仅会把自己搞糊涂，还会让程序产生各种奇怪的错误。  
**提示4-16**： 以数组为参数调用函数时，实际上只有数组首地址传递给了函数，需要另加一个参数表示元素个数。除了把数组首地址本身作为实参外，还可以利用指针加减法吧其他元素的首地址传递给函数。  
![计算左闭右开区间的元素和][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 16]

**写法一**先进行了一次指针减法，算出了从begin到end（不含end）的元素个数n，然后再像前面那样把begin作为“数组名”进行累加。  
**写法二**看起来更“高级”，事实上也更具一般性，用一个新指针p作为循环变量，同时累加其指向的值。  
这两个函数的调用方式与之前相似，例如，声明了一个长度为10的数组a，则它的元素之和就是sum（a，a+10）；  
若要计算a【i】，a【i+1】，…，a【j】，则需要调用sum（a+i，a+j+1）。  
把数组作为指针传递给函数时，数组内容是可以修改的。因此如果要写一个“返回数组”的函数，可以加一个数组参数，然后在函数内修改这个数组的内容。  
![古老的密码][e0affacc35ce4b3eb1c2eb2504e67ac8.png]  
**【分析】**  
既然字母可以重排，则每个字母的位置并不重要，重要的是每个字母出现的次数。这样可以先统计出两个字符串中各个字母出现的次数，得到两个数组cnt1【26】和cnt2【26】。下一步需要一点想象力：只要两个数组排序之后的结果相同，输入的；；两个串就可以通过重排和一一映像变得相同。这样，问题的核心就是排序。  
C语言的`stdlib.h`中有一个叫`qsort`的库函数，实现了著名的快速排序算法。它的声明是这样的：

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void *) );

前3个参数不难理解，分别是待排序的数组起始地址，元素个数和每个元素的大小。最后一个参数比较特别，是一个指向函数的指针，该函数应当具有这样的形式：

int cmp(const void *, const void *) {  … }

这里的新内容是指向常数的“万能”的指针：const void \* ，它可以通过强制类型转化变成任意类型的指针。

## 4.3 递归 ##

**定义**：  
（1）1是正整数。  
（2）如果n是正整数，n+1也是正整数。  
（3）只有通过（1），（2）定义出来的才是正整数。  
这样的定义也是递归的：在“正整数”还没有定义完时，就用到了“正整数”的定义。这和前面“参见递归”在本质上是相同的，只是没有它那么直接和明显。  
同样地，可以递归定义“常量表达式”（以下简称表达式）：  
（1） 整数和浮点数都是表达式。  
（2） 如果A是表达式，则（A）是表达式。  
（3） 如果A和B都是表达式，则A+B,A-B,A\*B,A/B都是表达式。  
简洁而严密，这就是递归定义的优点。

## 4.3.2 递归函数 ##

数学函数也可以递归定义。例如，阶乘函数f（n）=n！可以定义为：  
![阶乘函数递归][d8ac0a3a8e114f92bca0283a0b950fd3.png]

**提示4-17**： C语言支持递归，即函数可以直接或间接地调用自己。但要注意为递归函数编写终止条件，否则将产生无限递归。

## 4.3.3 C语言对递归的支持 ##

首先用bf命令设置断点——除了可以按行号设置外，也可以直接给出函数名，断点将设置在函数的开头。下面用r命令运行程序，，并在断点处停下来。接下来用s命令单步执行：  
![s命令单步执行][s]  
看到了吗？在第一次断点处，n=3（3是main函数中的调用参数），接下来将调用f（3-1），即f（2），因此单步一次后显示n=2.由于n==0仍然不成立，继续递归调用，直到n=0.这时不再递归调用了，执行一次s命令以后会到达函数的结束位置。  
**提示4-18**：由于使用了调用栈，C语言支持递归。在C语言中，调用自己和调用其他函数并没有本质不同。

> 如果仍然无法理解上面的调用栈，可以作如下的比喻：  
> 皇帝（拥有main函数的栈帧）：大臣，你给我算一下f（3）。  
> 大臣（拥有f（3）的栈帧）：知府，你给我算一下f（2）。  
> 知府（拥有f（2）的栈帧）：县令，你给我算一下f（1）。  
> 县令（拥有f（1）的栈帧）：师爷，你给我算一下f（0）。  
> 师爷（ 拥有f(0)的栈帧） ： 回老爷， f(0)=1。  
> 县令： （心算f(1)=f(0)\*1=1） 回知府大人， f(1)=1。  
> 知府： （ 心算f(2)=f(1)\*2=2） 回大人， f(2)=2。  
> 大臣： （ 心算f(3)=f(2)\*3=6） 回皇上， f(3)=6。  
> 皇帝满意了。

虽然比喻不恰当，但也可以说明一些问题。递归调用时新建了一个栈帧，，并且跳转到了函数开头处执行，就好比皇帝找大臣，大臣找知府这样的过程。尽管同一时刻可以有多个栈帧（皇帝，大臣，知府同时处于“等待下级回话”的状态），但“当前代码行”只有一个。

## 4.3.4 段错误与栈溢出 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70]: /images/20220829/c03a2dae8b954dadba1703caa4ecfafd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 1]: /images/20220829/f14864501656479e93f094d269b30b16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 2]: /images/20220829/a613053bea984bc18d437d320be08ece.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 3]: /images/20220829/2f3f4a56cd0446899cd5ea65f910bd9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 4]: /images/20220829/a986846ff0344e408728d4cfa34d714f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 5]: /images/20220829/7204140eaa024e9cb7e2d2aca7660d85.png
[7744]: /images/20220829/b700515168a8474aa75f362343bf22df.png
[3n_1]: /images/20220829/f74c6824f4314fe9843b96ffc12ac089.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 6]: /images/20220829/7a1b80f88fc14f538b69409e88cca1bc.png
[1ab50cfa17294165a019e19c891df8fd.png]: /images/20220829/085233f471834077a8ff58c3fcd1c8b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 7]: /images/20220829/4ffecea5b48440e5919a1c2c09df8c92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 8]: /images/20220829/5f61d92759ac412caf8fb8d806e9091b.png
[AC]: /images/20220829/a308ef5eefdb4dd3bce9aca988a7529d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 9]: /images/20220829/6edf8f15d8494dc0b8b9bc5a6c466f77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 10]: /images/20220829/fd89fb16dcd9401b82d991f017f7aed2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 11]: /images/20220829/1ef2c4e3e59448b194ee7080567616b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 12]: /images/20220829/1c7ba81f7f274c749410a807899d0629.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 13]: /images/20220829/47795e0a2f224af48d65b30a3e627cdb.png
[http_uva.onlinejudge.org]: http://uva.onlinejudge.org/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 14]: /images/20220829/c790e2dcbc694a7289f02e8ba599c63c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 15]: /images/20220829/1b622194f2194ca49ed34964fa39f00f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70 16]: /images/20220829/1ad0824736ed47bf80e512851337cf4b.png
[e0affacc35ce4b3eb1c2eb2504e67ac8.png]: /images/20220829/e9796ddcc66a4784a283538fd8fae59e.png
[d8ac0a3a8e114f92bca0283a0b950fd3.png]: /images/20220829/07e30c8d62484f3c9911e5f07ade116b.png
[s]: /images/20220829/da3a7a610fe746bf9e4e752d836a8310.png