编程珠玑课后习题答案第三章

第三章数据决定程序结构

1. 本书行将出版之时，美国的个人所得税分为 5 种不同的税率，其中最大的税率大约为 40%。以前的情况则更为复杂，税率也更高。下面所示的程序文本采用 25 个 if 语句的合理方法来计算 1978 年的美国联邦所得税。税率序列为 0.14，0.15，0.16，0.17，0.18，…。序列中此后的增幅大于 0.01。有何建议呢？（代码略）

税收表格中的每一项都包含三个值：该等级的下界、基本税收以及超出下界的税收。通过在表中增加一个具有“无限”下界的最终哨兵项，我们可以使顺序搜索代码更易编写、速度更快；当然也可以使用二分搜索。这些方法能够用于任何分段线性函数。

2. k 阶常系数线性递归定义的级数如下： $a_n = c_1a_{n-1} + c_2a_{n-2}+...+ c_ka_{n-k} + c_{k+1}$ ，其中， $c_1,...,c_{k+1}$ 为实数。编写一个程序，其输入为 $k,a_1,...,a_k,c_1,...,c_{k+1}$ 和 $m$ ，输出为 $a_1$ 至 $a_m$ 。该程序与计算一个具体的 15 阶递归的程序相比会复杂多少？不使用数组又如何实现呢？

用一个数组表示递归的系数，另一个数组表示前面 k 个值。程序在一个循环内部包含另一个循环。

3. 编写一个“banner”函数，该函数的输入为大写字母，输出为一个字符数组，该数组以图形化的方式表示该字母。

印刷体字母“I”可以编码为：

3 lines 9 x

6 lines 3 blank 3 x 3 blank

3 lines 9 x

或者更为紧凑的格式：

3 9 x
6 3 b 3 x 3 b
3 9 x

(意思就是前 3 行每行 9 个 x，接着 6 行每行 3 个空格 3 个 x 再 3 个空格，接着 3 行每行 9 个 x)

4. 编写处理如下日期问题的函数：给定两个日期，计算两者之间的天数；给定一个日期，返回值为周几；给定月和年，使用字符数组生成该月的日历。

为了求出两个日期之间的天数，我们需要计算这两个日期在相应年份中的编号，用后者减去前者（可能需要借助于具体的年份），然后加上年份之差的 365 倍，最后再为每个闰年加上 1。为了求出给定的日期是周几，我们需要计算给定日期和一个已知的周日之间的天数，然后用模运算将其转化为周几。为了生成给定年份中某个月的日历，我们需要知道该月有多少天（注意要正确处理二月份）以及该月的第一天是周几。Dershowitz 和 Reingold 专门写了一本 Calendrical Calculations（剑桥大学出版社 1997 年出版）。

5. 本习题处理英文中的一小部分连字符问题。下面所示的规则描述了以字母“c”结尾的单词的一些合法的连字符现象：et-ic al-is-tic s-tic p-tic -lyt-ic ot-ic an-tic n-tic c-tic at-ic h-nic n-ic m-ic l-lic b-lic -clic l-ic h-ic f-ic d-ic -bic a-ic -mac i-ac 规则的应用必须按照上述顺序进行；因此，有连字符“eth-nic”（由规则“h-nic”捕获）和“clin-ic”（前一测试失败，然后满足“n-ic”）。如何用函数来表达该规则？要求函数的输入为单词，返回值必须是后缀连字符。

由于对单词的比较是从右向左进行的，所以将单词按相反顺序（从右到左）存储可能需要付出一些代价。为了表示后缀序列，我们可以使用二维字符数组（通常比较浪费）或者用终止字符分割后缀的一维字符数组，也可以使用带有单词指针数组的字符数组。

6. 编写一个“格式信函发生器”，使之可以通过数据库中的每条记录来生成定制的文档（这常常称为“邮件归并”特性）。设计简短的模板和输入文件来测试程序的正确性。

Aho、Kernighan 和 Weinberger 在 AWK Programming Language（Addison-Wesley 出版社 1988 年出版）一书的第 101 页给出了一个 9 行的程序来生成格式信函。

7. 常见的字典允许用户查找单词的定义。习题 2.1 描述了允许用户查找变位词的字典。设计查找单词正确拼写的字典和查找单词的押韵词的字典。讨论具有以下功能的字典：查找整数序列（例如，1，1，2，3，5，8，13，21，…）、化学结构或者歌曲韵律结构。

斐波那契数列