紫书第三章部分习题导引及知识点小结

紫书第三章部分习题导引及知识点小结

关于密集字符集映射问题,我们可以开一个个数组,并提前存入每个字符应当映射成什么,之后为了借助数组自身的对应关系(下标一一对应其中的值),我们通过一定的表达式建立起字符编码值对数组下标的意义对应关系,实现从字符集到目标集的映射,第三章的相关问题有:

【UVA – 10082】WERTYU【紫书】

【UVA – 401】Palindromes【紫书】

相对于这类“密集映射”【指原像集存在很多需要映射的键,并且这些键在数值上相差很小】,有时会遇到“稀疏映射”【指原像集中需要映射的键在数值上相差较大】,这时我们一般更倾向于类似C++ STL中的map的类来实现。

对于计数问题,我们常常会用到容斥思想,或者说,经常情况下我们可能会遇到一些不太便于计数的情况,但是它的对立情况便于计数、总数容易计数,这个时候,使用容斥原理会十分方便,相关问题有:

【UVA-340】Master-Mind Hints【紫书】

对于简单的模式输入问题,通常会有两种思路(逐行处理的思路或者逐字符处理的思路【或者说,设计一个自动机来解决】),需要注意输入的格式,特别是考虑到题设中所有可能的输入形式,以及,常常需要关注的一个问题——程序的鲁棒性,留意数据中是否会有一些平凡的非法输入(如结尾存在多余空格之类的),本章相关问题有:

【UVA – 1586】Molar mass【紫书】

提到模式输入问题,不得不提模式匹配问题,本章习题中也有一些十分简单的模式匹配问题(说简单,是因为它只需要暴力便可以解决),这类问题更偏向于思维,在判断时整体思路是:考虑是否有不判即可证明无法必然匹配的条件、匹配的大致思路是什么样的、这个匹配思路是否存在多判或漏判的情况,本章相关问题:

【UVA – 455】Periodic Strings【紫书】

简单的模拟问题的处理思想,也与自动机处理思想存在类似之处,考虑在每一状态下能够接受什么样的输入,输入后会转移到什么样的状态,题目一般会设计一些题意范围内的“非法输入”,比如在一个平面内进行移动,但是已经到达边界显然无法做到这一操作,这种情况需要注意判断,本章相关问题:

【UVA – 227】Puzzle【紫书】

部分复杂问题的难以解决的原因是数据的无序性,这些问题的解决核心就是让数据变得有序:

【UVA-1587】Box【排序】【紫书】

很多问题,题目会将一些显然易见的合法条件省略,甚至在输入样例中也省略掉该种情况,结果是造成一定的误导性:

【UVA-1588】Kickdown【紫书】

本章还有一个与计算机数据表示方式相关的题目,十分有亮点;同时,该题也是一道典型的暴力枚举解方程的问题:

【UVA – 11809】Floating-Point Numbers【紫书】