1. 请定义下面函数，其参数nlist是数值的表，函数构造另一个表返回：

a) abs_list(nlist)，结果表中的元素是原表元素的绝对值。

b) accum(nlist)，在函数返回的表中，各元素是nlist中前段元素的部分积累和。例如accum([1,3,6])应返回[1,4,10]。

c) remove_neg(nlist)，结果表中元素来自表nlist，除去所有负数。

2. 请定义下面以表为参数的谓词：

a) all_positive(nlist)检查数值表nlist中全部元素是否都为正；

b) is_sorted(list1)检查表list1中元素是否按 <= 关系正确排序；

c) has_duplicate(list1)，检查list1是否有重复出现的元素。

3. 定义函数find_dups(list1)，其参数是一个表，函数返回一个集合，其中的元素是表list1里出现了多于一次的那些元素。另定义find_unique(list1)，它返回的表里包含了并仅包含list1里只出现一次的元素。要求保存原来的元素顺序。

4. 定义函数函数choose(list1, list2)，参数是两个整数表，函数返回一个表，表中元素都选自list1，而在list2中存在着这些数的平方。

5. 请定义函数prime_factors(n)返回n的素因子的表，重复元素只出现一次。

6. 定义函数squeeze(list1, list2)，两个参数都是整数的表。squeeze从list1里删除所有比表list2里的某个整数大1的数。注意，本函数不适合用for循环实现，因为删除元素将会改变被处理表的长度和内容。有兴趣的话，你可以用一些例子试验，注意观察计算中出现的情况。

7. 表可以有任意嵌套的结构，例如[3, [[5, 8], 6]]。如果两个表的嵌套结构相同，而且对应的基本元素相等，我们就说这两个表相等。请定义函数comp(list1, list2)，其两个参数都是基本元素全为整数的表（函数定义中不需要检查）。当且仅当list1和list2相等时comp返回True，否则返回False。函数中不能直接判断表相等（题目就是要求定义这个操作），只能对整数使用判断相等操作。

8. 对一个整数表，如果有一个切分位置使其前面的元素之和等于后面的元素之和，就称该位置是平衡点。请定义一个函数返回表的平衡点，不存在时返回 -1。

9. 请定义函数partition(s)，其参数为至少包含2个元素的正整数的表。该函数确定表s的三段划分a + b + c，要求得到的划分使a段元素之和suma与c段的元素之和sumc之差的绝对值 |suma - sumc| 达到最小。partition(s)返回元组(i,j)给出b段的范围，因此a段是s[:i]且c段是s[j:]；返回(i, i)表示b段为空且a是s[:i]而b是s[i:]。（b段可以为空，但a段和c段均不能为空）。

10. 写一个函数计算并输出直至第n行的杨辉三角形。请尽可能利用格式化功能排好输出形式，将杨辉三角形的一行输出为一行，整数之间用空格分隔。

11. 定义函数disjoins(list1)，其表参数list1的元素都是一对整数的表，形如[a,b]，表示数轴上的闭区间。函数返回一个表，其中是从list1选出的一组不相交区间，而且每个未选的区间至少与一个被选区间相交。这里不要求考虑区间的总长度最大等问题，这些问题可以作为自我练习的要求。

12. 请参考5.2.3节有关多项式求值方法的讨论，定义另一个多项式求值函数，其循环中每次迭代只做一次乘法（而不是做一次乘幂）。

13. 考虑5.2.3节生成整数的素因子表的函数。由于它从小到大生成素因子，后一个素因子一定大于前一个。请利用这个认识修改函数定义，尽量减少试除次数。

14. 为5.2.3节的素因子分解函数（和前一题的函数）确定一组测试用例，写一个驱动程序自动完成它们的测试。另外，用一些较大的数比较两者的效率。

15. 请参考5.2.3节的筛法实现定义另一个函数，使其在计算过程中直接从表里删去已确定的非素数。请从各方面对比你定义的函数与正文中的函数，包括定义的方便性等，再请针对较大范围的整数做些试验，比较两种算法的效率，并仔细思考某种方法较慢的原因。再参考5.2.3节最后的建议，用全部元素为1和0的表实现筛法。

16. 定义函数date(year, num)，其参数都是整数：year表示年份，num表示该年的第num天。函数返回表示日期的三元组(y, m, d)；参数不正确时报错。

17. 扩充5.3.2节的有理数包，尽可能完善其设计，加入更多有用操作。

18. 5.4.4节给出了一个实现表反转的函数，请设计一组试验，尽可能完整地检查这个函数的功能。并说明为什么你给出的这组试验是合适的。

19. 请根据5.4.4节讨论表反转函数时的建议，实现另一个表反转函数，函数里实际使用两个变量，在每次循环开始时，它们总指向待交换的那对元素。

20. 扩充5.4.5节中自定义的函数map，使之可以接受多元函数作为元素处理函数，同时处理多个序列参数，生成一个新表。

21. 请定义另一个函数实现5.4.5节中fib_sum的功能，但其中只使用有限的几个变量，不用高阶函数，操作中也不构造表。

22. 请定义一个谓词函数，判断一个字符串能否转换为一个浮点数。然后把这个检查功能加入5.5.3节的简单计算器程序。

23. 请定义函数use_only(text, cset)，它检查字符串text里是否只用到用字符串cset表示的字符集合中的字符，返回一个逻辑值。

24. 请定义函数remove(text, cset)，它基于text做出一个字符串返回。串中包含text里所有不属于cset的字符（出现），并维持原来的顺序。

25. 定义谓词anagram(s1, s2)，如果调整字符串s1中字符的位置能得到s2，函数就返回True，否则返回False。称这样两个字符串类似。

26. 如果一个字符串的反转是另一字符串，则称它们互逆。定义函数rev_pair(slist)，它返回字符串表slist里所有互逆的字符串对，形式上是二元组的表。

27. 请定义函数list2dic_count(list1)，参数是不变元素的表。函数返回一个字典，其中关键字是list1的所有元素，关联值是这些元素在list1里出现的次数。

28. 利用字典实现一个高效的has_duplicate(list1)，检查list1中是否有重复元素。

29. 请生成一个字典，其关键字是形式为classi的字符串，其中i为表示整数的十进制数字串，取值从100到200。该字典把classi映射到i的平方。例如，字典将字符串class100映射到10000，将class111映射到12321。

30. 定义函数rev_map(dic, v)，参数dic是字典，函数返回dic中所有以v为关联值的关键字的表。

31. 请定义函数rev_dict(dic)，它以一个值也为不变对象的字典dic为参数，返回一个字典，其中关键字是dic中所有的关联值v，与v关联的值是在dic中映射到v的所有关键字的表。也就是说，假设rev_dict(dic)的结果赋给变量dic1，那么就有：如果dic[k] == v，那么k in dic1[v]。

32. 请定义下面处理字典的函数：

a) dict_intersect(dic1, dic2)构造一个字典，其中包含且仅包含在两个字典dic1和dic2都有的关键字，各关键字总取其在dic2的关联值。

b) dict_union(dic1, dic2)构造一个字典，其中包含所有出现字典dic1或dic2的关键字。如果某关键字在两字典都有，取其在dic2的关联值。

33. 请定义一个函数dict_intersection(*dics)，它以任意多个字典为参数，返回一个字典，其中包含参数字典中共有的所有关键字，与每个关键字关联的值是一个集合，集合元素是各字典里该关键字的关联值。

34. 定义一个函数most_frequanct(text)，它找出一个（可能很长的）字符串里出现最多的字符，返回这个字符及其出现次数的元组。如果有多个字符出现次数相同，就返回以它们的元组为元素的元组。

35. 请选择正文中的三个函数，为它们增加完全的参数检查。讨论你遇到的问题。

36. 数学中的连分数指如下形式的表达式：

可以将其简记为。已知：

n

n

n

请完成下面工作：

a) 定义一个求连分数值的函数cfrac_n，它接受一个函数参数和一个整参数，求出连分数的值；

b) 对函数，假定收敛，定义函数cfrac求其收敛值；

c) 写出程序验证上面给出的三个连分数等式。

37. 设班级有23个学生，现在希望求出其中存在两个人的生日相同的概率。请通过蒙特卡罗模拟给出结果。再对任意n个学生的情况完成这一工作。

38. 请查阅书籍或者网上的资源，找到有关RSA加密算法的材料。请定义一个函数实现该算法，并尽可能提高算法的效率。

39. 假设参数image是一个表示图像的n×n二维表（以表元素为表），其中每个元素表示一个图元（彩色图形的图元可能是表示红绿蓝的三元组，黑白图形的图元可能是表示灰度的整数0~255，但这里不关注图元的具体表示）。请定义函数totate90(image)，它将图形image按顺时针方向旋转90度。函数执行中不另外建立表结构，请直接在图像中修改。函数开始请检查参数确实是n×n的正方形图像。

40. 问题与前一题类似，但被处理图形包含任意m×n个图元，要求不修改参数而是另外创建一个作为旋转结果的表。请：

a) 定义函数rotate90(image)将图形顺时针旋转90度；

b) 定义函数rotate180(image)将图形顺时针旋转180度；

c) 定义函数halfsize(image)，它生成一个大小为(m/2)×(n/2)的图形，其中每个元素的值是原来相邻的4个元素的平均值。为简单起见，可以假设m和n均为偶数，你可以假设原图为彩色图或者灰度图。

41. 完成一个猜单词游戏：程序里保存了一组单词，每轮游戏中程序从这些单词里随机选出一个。一轮游戏包含若干回合，每个回合开始时，程序从单词中随机选出一个字母，输出该字母及其在单词里的位置作为提示。如果用户认为已经猜到，就输入所猜单词，前面加一个叹号“!”，程序评判对错并记录有关信息。如果用户无法猜出结果，可以输入问号“?”要求程序继续给提示。输入“quit”时程序结束并输出一组信息：本次游戏共猜了几个单词，正确和错误的次数，平均每个单词要求了几轮提示。

42. 模拟一个金属杆的热传导过程。杆左端有一个100度的稳定热源，右端有一个70度的稳定热源。将杆分为10段，除两端点外其余分段点初始温度为0度。通过一轮轮计算模拟热传导过程，每个点下一时刻温度是其自身当前温度与其左右相邻点温度的平均值。①输出前10轮传导中各分段点的情况；②确定多少轮传导后各点温度均超过60度，输出此期间每5轮传导后的情况。请用格式化功能把输出排列整齐。

43. 考虑下面游戏：n个人围成一圈，每次游戏随机取两个数m和k。游戏开始，从编号为m的人开始计数，数到第k个人出列。然后再从出列的人之后数下去，直到圈子里只剩一个人为止。请写一个函数CGame(n, m, k)模拟这个游戏，在模拟中输出出列人的编号。围成一圈可以用计数到最大的编号后重新回到最小编号值来处理。

44. 请根据5.8.1节有关加法实现的讨论，利用多项式幂次集合的交集和两个差集的技术，实现一个完成多项式加法的函数，并将其与正文中的实现比较。

45. 请继续完善5.8.1节的多项式计算系统程序包，定义下面函数：

a) 按升幂顺序输出多项式，其中采用根据个人喜好设计的一种易读的输出形式（可以假设其自变量是x）；

b) 如果你觉得直接用字典描述多项式的输入不好，请设计一种多项式的输入形式，并实现相应的输入函数；

c) 其他算术运算，包括求负、减法和除法，其中除法可以返回一对多项式，分别表示除运算的商和余式；

d) 定义多项式的各种比较运算；

e) 多项式的求导和积分；

f) 考虑定义其他函数，其他有用的运算和功能。

46. 5.8.2节开始建议了一种可能的筛法实现，请定义函数完成这个设想。

47. 请考虑3.2.6节中用递归方式解决的两个问题，设计并实现不用递归求解的函数。

48. 一个m×n的矩阵可以表示为一个两层的表（前面已经有许多例子）。稀疏矩阵就是绝大部分元素都是0的矩阵，采用两层表表示，表中将有大量0元素。请设计一种用字典表示稀疏矩阵的方法，并实现几个矩阵运算，包括矩阵的加法和乘法。