《编程珠玑》习题练习In Python——第三章 数据决定程序结构

本章的主旨是：数据视图决定了程序结构。简单的数据表示可以使用简单高效的程序来处理。好的数据表示是好的程序的前提。正如好的食物原料是做出美味食物的前提。

本章中的编程思路总结： 1、尽量使用数组处理重复数据。 2、定义简单的表示语言和一个语言的解释器来表示复杂的数据结构。

习题1

税收计算。准确说是超额累进税率计算。使用两个数组分别定义不同等级税收的区间，和该区间的税率。一个循环便可解决问题。最后一个区间的上限应该设置为无穷，Python可以使用float('inf')来表示。 代码如下：

def test_1(): tax_strt = [2000,3000,4000,6000,float('inf')] tax_rate = [0.14,0.17,0.24,0.40] income = 20000 tax = 0 for i in range(len(tax_strt)-1): if income < tax_strt[i]: break tax += (min(income-tax_strt[i],tax_strt[i+1]-tax_strt[i]))*tax_rate[i] print(tax)

习题2

k阶常系数线性递归定义的级数如下：

an=c1an−1+c2an−2+...+ckan−k+ck+1 其中c为常数。编写一个程序，输入为 k,a1,a2,...ak,c1,c2...ck+1和m ，输出为 a1到am 。

著名的斐波那契数列其实就是这个级数在k=2的时候的一种特殊形式。斐波那契数列使用递归法计算时间复杂度是指数级别的。具体证明要用到母函数的方法。总之，递归法不能解决这个问题，那么可以从序号更小的元素开始依次计算，每次计算出的值存储在数组中。每计算一个元素，只需要用到比它小的k个元素，因此更进一步，可以只保存这k个数。实现代码：

def test_2(): k = 5 m = 6 c = list(range(1,k+2)) a = list(range(1,k+1)) curIndex = k cur = 0 while(curIndex<m): cur = 0 for i in range(0,k): cur += c[i]*a[(curIndex+i)%k] cur += c[-1] a[curIndex%k] = cur curIndex +=1 print(cur)

习题3

编写一个函数，输入为一个大写字母，输出为一个数组，该数组用图形化的形式表示该字母。

非常清楚记得大一学C++就有做过这种题目。要求输入一个菱形或者三角形。当时整个程序写了大量的输出代码，根据每行输出有规律的变化可以使用一些循环简化代码。这样做的问题在于，将数据内容编码在了程序之中。也就是说，程序只能输出菱形，如果要输出三角形，整个代码都需要修改。

这个题更进一步，要根据输入来输出不同的图形。现在就不可能为每个字母写一个子程序了。根据数据和程序分离的思想。应该将图形表示为一种简单的数据形式，将这种数据输入一个绘制程序应该要可以获得不同的图形。这就是定义一种描述语言同时实现该语言的解释器的编程方法。

首先定义一种描述图形的语言，结构如:r3s3#3s3。有三种特殊符号，r代表行重复，s代表空格，空格忽略，其他符号则代表该符号本身。除了r之外，符号后面接数字代表该符号在一行中重复的次数，r符号则表示该行重复的次数。数字均是一位数。上面的语句输出为：

### ### ###

那么如字母I可以表示为：l2#6 l4s2#2s2 l2#6，输出为：

###### ###### ## ## ## ## ###### ######

实现这个语言的解释器：

def InterpretLetter(dsc): cur = 0 pic = [] while(cur<len(dsc)): cur+=1 r = int(dsc[cur]) cur+=1 line = [] while(cur<len(dsc) and dsc[cur]!='l'): char = dsc[cur] if char ==' ': cur+=1 continue elif char =='s': char = ' ' cur +=1 time = int(dsc[cur]) line += [char]*time cur +=1 for i in range(r): pic.append(line) return pic

测试程序：

def test_3(): dic ={ 'C': "l2#6 l4#2 l2#6", 'E':"l2#7 l2#2 l2#7 l2#2 l2#7", 'H':"l4#2s3#2 l2#7 l4#2s3#2", "I":"l2#6 l4s2#2s2 l2#6" } letter = "I" pic = InterpretLetter(dic[letter]) for l in pic: print("".join(l))

这个描述语言的能力有限，描述复杂图形是及其复杂的。但是在绘制字母任务中勉强可以胜任。合理的设计应该在功能和复杂度上取得平衡。

习题4

编写日期处理函数，处理以下问题：给定两个日期，计算两者天数差；给定一个日期，返回星期；给出年月，使用字符数组生成该月日历。

第一个问题是后面两个问题的基础。我的计算方法用一张图表示如下： 这里要计算2017年某天到2020年某天的天数差X。只需要分别计算两个时间点在该年中的天数A,B，以及两个时间点年份区间的天数和Y。X = Y+B-A。需要判断两个天数的先后。程序分为几个部分，首先是对时间字符串的解释程序：

def InterpDate(ds):# 解释日期字符串 date = [0,0,0] # 年月日 dInd = 0 sInd = 0 while(sInd<len(ds)): v = ds[sInd] sInd += 1 if v == '/': dInd +=1 if dInd >= len(date): raise Exception("date error") else: v = int(v) date[dInd] = date[dInd]*10 + v return date

计算二月的天数：

def GetFebDay(year): if year%4 ==0 and year % 100 != 0 or year%400 ==0: return 29 else: return 28

计算时间是一年中的第几天：

MONTH_DAY = [31,0,31,30,31,30,31,31,30,31,30,31] def DaysPassInYear(date):# 计算当年过去几天 day = 0 day += sum(MONTH_DAY[:(date[1]-1)]) # 过去的月 if date[1]>2: day += GetFebDay(date[0]) # 本月过去的日 day += date[2] return day

计算一年总共几天：

def DaysInYear(year):# 计算一年几天 return sum(MONTH_DAY)+GetFebDay(year)

最后计算天数差就很好算了：

def CmpDate(d1,d2): # 比较d1 d2 两个日期 if d1[0] * 10 ** 4 + d1[1] * 10 ** 2 + d1[2] < d2[0] * 10 ** 4 + d2[1] * 10 ** 2 + d2[2]: return -1 if d1[0] * 10 ** 4 + d1[1] * 10 ** 2 + d1[2] > d2[0] * 10 ** 4 + d2[1] * 10 ** 2 + d2[2]: return 1 else: return 0 def CalDay(ds1,ds2): # 计算两日期间的天数差。输入字符串 d1,d2 = InterpDate(ds1),InterpDate(ds2) if CmpDate(d1,d2) < 0: #保证 d1更大 tmp = d1 d1 = d2 d2 = tmp day1 = DaysPassInYear(d1) day2 = DaysPassInYear(d2) dayYear = 0 for y in range(d2[0],d1[0]): dayYear+=DaysInYear(y) return dayYear+day1-day2

第二个问题，计算星期。在第一个问题基础上，只要知道某一天的星期，就可以通过天数差来推算其他任意一天的星期了。不过上一问返回非负数，这一问里面需要增加这个时间差的正负。将写这段代码的时间2016年12月3日星期6作为基准，得到代码：

def GetWeek(ds): # 给定日期，计算星期。输入字符串 day = CalDay(ds,STD_DS) if CmpDate(InterpDate(ds),InterpDate(STD_DS)) < 0: day = day*-1 return (day+STD_WEEK)%7

第三问实现没有问题，但是还是应该遵循一个原则，尽量使用循环，增加灵活性减少程序复杂度：

def GetCalend(year,month): # 给年月，输出日历 cal =[] cal.append("Year: "+str(year) +" Month: " + str(month)) line = [] for w in WEEKS: line.append(w) line.append("\t") cal.append(line) line =[] wk = GetWeek(''.join([str(year),'/',str(month),'/1'])) line += ["\t"]*wk day = 1 md = MONTH_DAY[month-1] if month ==2: md = GetFebDay(year) while(day <= md): line+= [str(day)]+["\t"] day+=1 wk = (wk+1)%7 if wk == 0: cal.append(line) line = [] if len(line)>0: cal.append(line) return cal

2016年12月显示如下：

Year: 2016 Month: 12 Sun Mon Tue Wen Thu Fri Sat 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

给一个单词和后缀列表。匹配该单词的后缀。

我理解的题目意思就是这么简单，答案考虑翻转字符什么我觉得完全没必要。代码：

def test_5(): SUFFIXS = ['et-ic','al-is-tic','s-tic','p-tic'] word = "ppap-tic" s = None for suf in SUFFIXS: strt = len(word)-len(suf) find = True for i in range(len(suf)): if word[strt+i] != suf[i]: find = False break if find: s = suf break print(word,s)

习题6

编写一个格式信件发生器。也就是给定一个文本模板和文本变量，自动将变量填充到模板中。Python中可以直接用format函数实现。不过这里我们要自己实现这个功能。

首先要定义文本模板的格式，使用$加一个序号n表示第n变量。$和序号必须相连。另外定义\为转义字符。代码如下：

def InterpretText(ts,args): t = [] cur = 0 getArg = False argNum = 0 escape = False while(cur<len(ts)): c = ts[cur] if getArg: if ord(c) in range(ord('0'),ord('9')+1): argNum = argNum*10 + ord(c)-ord('0') else: t.append(args[argNum]) t.append(c) argNum = 0 getArg = False elif escape: t.append(c) escape = False elif c == '\\': escape = True elif c == "$": getArg = True else: t.append(c) cur+=1 return ''.join(t)

测试代码：

def test_6(): ts = r"Hello \$ $0 \\ !" text = InterpretText(ts,["World"]) print(text)

输出：

Hello $ World \ !