《编程珠玑》第 3 章──数据决定程序结构

恰当的数据视图实际上决定了程序的结构,在节省空间方面无计可施时,将自己从代码中解脱出来,退回起点并集中心力研究数据,常常能有奇效。

几点原则

  • 使用数组重新编写重复代码。冗长的相似代码常常可以使用最简单的数据结构——数组来更好地表述。
  • 封装复杂结构。当需要非常复杂的数据结构时,使用抽象术语进行定义,并将操作表示为类。
  • 尽可能使用高级工具。超文本、名字——值对、电子表格、数据库、编程语言等都是特定问题领域中的强大的工具。
  • 从数据得出程序的结构。在动手编写代码之前,优秀的程序员会彻底理解输入,输出和中间数据结构,并围绕这些结构创建程序。

习题

1. A programming text gives the following twenty-five if statements as a reasonable approach for calculating the 1978 United States Federal Income Tax. The rate sequence 0.14, 0.15, 0.16, 0.17, … exhibits jumps larger than 0.01 later in the sequence. Any comments?

1
2
3
4
5
6
7
8
9
10
11
12
13
if Income <= 2200 then
Tax := 0
else if Income <= 2700 then
Tax := 0.14 * (Income - 2200)
else if Income <= 3200 then
Tax := 70 + 0.15 * (Income - 2700)
else if Income <= 3700 then
Tax := 145 + 0.16 * (Income - 3200)
else if Income <= 4200 then
Tax := 225 + 0.17 * (Income - 3700)
...
else
Tax := 53090 + 0.70 * (Income - 102200)

使用数组,数组中的每一项包含三个值:该等级起征点、基本税和税率。

2. A kthk^{\text{th}}-order linear recurrence with constant coefficients defines a series as

an=c1an1+c2an2++ckank+ck+1,wa_n = c_1a_{n-1} + c_2a_{n-2} + \dots + c_ka_{n-k} + c_{k+1},w

where c1,,ck+1c_1, \dots ,c_{k+1} are real numbers. Write a program that with input k,a1,,ak,c1,,ck+1k, a_1, \dots , a_k, c_1, \dots , c_{k+1}, and N produces the output a1a_1 through aNa_N. How difficult is that program compared to a program that solves one particular fifth-order recurrence, but does so without using arrays?

这里还是在考察使用数组来编写重复代码。

1
2
3
4
5
6
7
8
9
10
11
12
void calc(std::vector<int> &result, int k, const std::vector<int> &a, const std::vector<int> &c, int N) {
result = a;
assert(k <= N);
for (int i = k; i < N; ++i) {
int sum = 0;
for (int j = 0; j < k; ++j) {
sum += c[j] * result[i - j - 1];
}
sum += c[k];
result.emplace_back(sum);
}
}

3. Write a “banner” procedure that is given a capital letter as input and produces as output an arrar of characters that graphically depicts that letter.

把每个字母用数组存起来。比如:

1
2
3
4
5
[
[0, 9, 0, 3],
[3, 3, 3, 6],
[0, 9, 0, 3]
]

可以用来代表:

1
2
3
4
5
6
7
8
9
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXX
XXX
XXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

4. Write procedures for the following date problems: given two dates, compute the number of days between them; given a data, return its day of the week; given a month and year, produce a calendar for the month as an array of character. The first version of your programs may assume that the year is in the 1990’s; the second version should be as general as possible.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <vector>
#include <iomanip>
#include <iostream>

class Date {
public:
Date(int y, int m, int d) {
year = y;
month = m;
day = d;
}

bool isLeapYear(int y) {
return (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0));
}

bool isLeapYear() {
return isLeapYear(year);
}

int whichDay() {
// 今年的第几天
int sum = day;
for (int i = 0; i < month - 1; ++i) {
sum += months[i];
}
if (isLeapYear() && month > 2) {
++sum;
}
return sum;
}

int getYear() {
return year;
}

int getDays(int m) {
if (m >= 0 && m <= 11) {
return months[m];
}
return -1;
}

private:
int year;
int month;
int day;
std::vector<int> months = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
};

int dayDelta(Date &before, Date &after) {
int sum = -(before.whichDay());
for (int i = before.getYear(); i < after.getYear(); ++i) {
sum += before.isLeapYear(i) ? 366 : 365;
}
sum += after.whichDay();
return sum;
}

int whatDay(Date &d) {
// 1990 年 1 月 1 号是星期一
Date tmp(1900, 1, 1);
return dayDelta(tmp, d) % 7 + 1;
}

void printCal(int y, int m) {
Date d(y, m, 1);
int week = whatDay(d);
int days = d.getDays(m - 1);
std::cout << "Su Mo Th We Th Fr Sa\n";
std::cout.flags(std::ios::right);
for (int i = 0; i < week; ++i) {
std::cout << " ";
}
for (int j = 0; j < days; ++j) {
std::cout << std::setw(2) << j + 1;
if (week++ % 7 == 6) {
std::cout << "\n";
} else {
std::cout << " ";
}
}
std::cout << std::endl;
}

int main() {
Date today(2018, 3, 30);
std::cout << "what day? " << whatDay(today) << std::endl;
printCal(2018, 3);
return 0;
}

输出结果:

1
2
3
4
5
6
7
what day? 5
Su Mo Th We Th Fr Sa
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

5. This problem deals with a small part of the problem of hyphenating English words. The following list of rules describes some legal hyphenations of words that end in the letter “C”:

1
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

The rules must be applied in the above order; thus the hyphenations “ethnic”(while is caught by the rule “h-nic”) and “clinic”(which fails that test and falls through to “n-ic”). How would you represent such rules in a subroutine that is given a word and must return suffix hyphenations?

从后往前,依次比较每个字符。可以使用二维数组或者带有分割符号的一维字符数组来存储后缀序列。

6. Write a form letter generator that is general enough to interpret the schema we saw earlier; make your program as simple as possible. Design small schemas and input files to test the correctness of your program.

字符串格式化。

7. Typical dictionaries allow one to look up the definition of a word, and Problem 2.1 describes a dictionary that allows one to look up the anagrams of a word. Design dictionaries for looking up the proper spelling of a word and for looking up the rhymes of a word. Discuss dictionaries for looking up an integer sequence (such as 1, 1, 2, 3, 5, 8, …), a chemial structure, or the metrical structure of a song.

查找单词正确拼写或者押韵词,都需要先把单词中的字母按照顺序来排列,为了方便搜索查找。找到之后,利用相应的押韵词或者拼写对应关系来找到相关信息。