3.5 练习
概念和理解
1. 复习下面概念：数值积分，区间分割法，舍入误差，简单重复，累积，累积变量，生成和筛选，递推，递推变量，素数（质数），因子和真因子，哥德巴赫猜想，输入循环，输入控制的循环，递归定义，递归函数，循环定义，无穷递归，循环和递归，斐波那契数列，二路递归，计时，循环不变式，计算复杂性，最大公约数，欧几里得算法（辗转相除法），河内塔问题，自递归，相互递归，程序终止性，不可判定，Collatz猜想，唯一定义原则，自下而上，自顶向下，逐步求精，形式参数（形参），文档串，实际参数（实参），类型错误，全函数，参数检查，断言语句，通用和专用的方法，枚举和检查，二分法，绝对误差，相对误差。
2. 请分析3.1.2节中定义的函数mysin的执行，为什么它对越大的实参误差越大？请考虑用Python做一些试验，分析并总结试验中看到的情况。
3. 请证明如果一个自然数有真因子，一定有小于其平方的真因子。
4. 请分析3.2.2节改进的乘幂函数，设法弄清它对一般的自然数n计算power(x, n) 时要做多少次乘法和加法。
5. 请设法论证3.2.2节改进的乘幂函数对任何非负整数乘幂参数都能终止。
6. 请在你计算机上试验递归的fib函数，看看算到第几个斐波那契数时，计算的时间就超过了10秒钟，半分钟和一分钟。
7. 请设法论证3.2.4节最后用for结构描述的fib函数的正确性。
8. 请设法说明3.2.5节中常用辗转相除法定义的函数一定能求出最大公约数。
9. 请证明对河内塔问题，搬移n个圆盘时正好调用moveone函数2n - 1次。
10. 对一些n值试验河内塔程序，给它们计时。据此估计你所用计算机搬完64个金盘需要的时间。再去掉程序执行中的输出（例如把moveone的体改为一个return语句）后重新试验。如果僧侣们1秒钟搬金盘1次，搬完64个金盘需要多少时间？将这一时间与科学家对宇宙从大爆炸至今的估计寿命比较，据此评价僧侣们的说法。
编程练习
1. 无穷级数4/1 - 4/3 + 4/5 - 4/7 + ... 的和是圆周率，请写一个程序计算出这一公式前n项的值，同时给出所得结果与值的差。
2. 请写一个程序，计算连分式1 + 1 / (1 + 1 / (...(1 + 1 / (1 + x))))，是有n层嵌套的连分式。其中的n和x由输入得到。再把程序改为一个函数定义。
3. 请写程序计算调和级数的部分和，检查这个“和”在你机器上达到10、11、...、16、17、18时所用的时间，输出这些结果。你看到了什么情况？（请在你的程序文件里用注释的方式说明试验的情况。）
4. 假设1元钱买一瓶水，三个空瓶可以换一瓶水。初始n元最终可以喝到几瓶水？
5. 如果一个正整数m的所有因子（包括1，但不包括m自身）之和s等于m，则称m为完全数；当s < m时称m为亏数；当s > m时称m为盈数。请定义一个函数，在参数m为亏数、完全数或盈数时分别返回 -1、0、1。基于这个函数定义另一函数，它检查a到b范围里的整数，统计其中亏数、完全数和盈数的个数并输出。最后调用你定义的函数统计几个范围里的整数的情况。
6. 天才数学家Srinivasa Ramanujan发现了下面无穷级数：
请定义函数，基于这个级数计算圆周率。
- 请定义函数is_palindrome(s)，它检查字符串s是否回文，也就是说，正向读和反向读一样的字符串。例如 "123454321" 就是一个回文数字字符串。
- 请定义函数make_palindrome(s)，它从任意字符串s做出一个回文字符串，其中前面一段是原字符串。例如，make_palindrome("abcd")应得到 "abcdcba"。定义中只使用已经介绍过的几个字符串操作。
- 一个单词是字符串里的连续的几个字符。请定义函数has(s, w)，它检查字符串s里是否出现单词w，如果出现就返回True，否则返回False。注意，这里你可能需要用到字符串长度、字符串切片的操作。只能使用已介绍的几个字符串操作。
- 写一个二进制浮点数转换计算器程序，通过输入送给它任意一个包含（一个）小数点的二进制串，它求出相应的浮点数并输出。该程序应反复读入二进制串并输出，直到人输入特殊的串end。
- 请修改3.1.3节求输入的10个正数之平均值的程序，保证在修改程序时，只要修改给变量num赋的值，函数的输出（包括输出的信息串）都正确了。
- 基于第2章有关三角恒等式检查的练习，写几个交互式的三角恒等式检查程序。执行时反复要求输入，完成检查并输出结果。
- 请考虑3.2.5节提出的另一种求最大公约数的方法：令一个变量从某个数开始取值，而后令其值递减，找到的第一个公约数就是两个参数的最大公约数。定义一个函数实现这种算法，并论证该函数能保证找到最大公约数。
- 函数f (n) 由如下规则定义：当n小于3时，f (n) = n；对于更大的n，f (n) = f (n-1) + 2 * f (n-2) + 3 * f (n-3)。请采用递归的方式直接定义一个计算f的函数，再按照递推的方式用循环结构定义一个计算f的函数。
- 请修改硬币兑换程序，改为先试验小币值硬币，后试大币值硬币。看看是否还能得到正确结果。另一方面，用一些总币值做试验，比较这种方法与正文中给出的方法，在求解时间上有没有差异。如果有差异请设法给出，说明为什么某种方法更好。
- 有人提出可以通过一个6重循环计算硬币兑换问题。请考虑这一可能性，设法定义一个函数。请比较你写出的函数和本章正文中给出的函数。
- 著名的Ackermann函数Ack(m, n) 定义如下：
请将其定义为Python函数，并试验求几个值。例如Ack(3, 4) 应该得到125，请试试更大的参数，看看函数值随着参数而增长的情况。 - 请修改collatz函数，令其统计并输出：得到结果的过程中操作的步数，计算中连续下降超过三步的阶段数。
- 请利用（修改/使用）3.3.2节讨论的Collatz函数，定义三个函数：第一个函数返回（注意，不是输出）对正整数n做Collatz计算的过程中历经的最大值。第二个函数检查m到n的所有正整数，输出其中造成Collatz函数迭代次数最多的数k以及它的迭代次数；第三个函数检查从m到n的所有正整数，找出其中的k，在对k的迭代中历经的最大整数值比其他数都大，输出k和对它的迭代中达到的最大数值。
- 请基于3.4.2节的函数，定义几个画出规范图形的函数，例如矩形、菱形、六边形等。
- 为各种字符图形函数增加一对描述基准点的参数。
- 请定义函数draw_4square(m, n)，它能输出用字符"-", "|", "+"拼出的“田”字，四个小方块的长度和宽度分别为m和n个字符或行数。例如，drawTian(4, 2)输出下面的“田”字。（注意，为了保证空格和各种字符宽度相同，以便输出字符对齐，应该把Python Shell的窗口设置为采用某种等宽字体输出。）
+----+---+
| | |
| | |
+----+---+
| | |
| | |
+----+---+ - 基于你完成上面函数的认识定义另一个函数draw_board(m, n)，它能生成用同样三个字符拼出的m * n个格子的棋盘（例如8*8个格子的国际象棋棋盘）。请注意在工作中定义有用的辅助函数。
- 请定义一个函数prime_factors(n)，它设法找出正整数参数n的所有素因子，并调用print逐个输出，重复的因子重复输出。请在函数开始检查参数情况，只对满足函数要求的参数做计算。
- 请搜索互联网，设法找到另一种判定素数的方法，并将其实现为Python函数。
- 哥德巴赫猜想说任一大于等于6的偶数可以分解为两个奇素数之和。正文中给出了利用函数is_prime分解的函数定义。请尝试不定义辅助函数，直接定义一个在一定范围内检查哥德巴赫猜想的函数，执行中给出遇到的各偶数的素数分解。请从各方面比较这两个函数定义。另外，再请利用素数判断函数定义一个函数，它对6到n的偶数输出其素数分解，而且保证对每个偶数只输出一种分解。
- 利用前面给的代码，比较采用二分法求立方根和采用立方根逼近公式两种计算的操作效率。用给定范围中的一组等差值检查它们的迭代次数，并生成出比较结果的表格。
- 假设需要从很长的钢条上剪裁出长度为5cm、8cm、17cm和28cm的短条。请写一个函数，它计算出从长度为n cm的钢条上裁出这些短条的不同方式的数目，要求浪费的钢条长度不超过3cm。（注意：裁短钢条的不同方式与顺序无关。请考虑如下递归看法：从长度为n的钢条上剪裁的不同方式等于...）。在上面的程序里用注释形式论述你的做法的正确性。请在定义好函数之后，调用它求出对100cm、160cm和240cm的钢条的计算结果，以清晰明了的形式产生输出。
- 作业中有些题目要求定义函数。请在每个函数定义后面附加几行代码，调用所定义函数做几个典型计算，并用print以容易看明白的方式输出计算结果（产生的输出行中应说明输出的是什么）。