《从问题到程序：用Python学编程和计算》——练习

本节书摘来自华章计算机《从问题到程序：用Python学编程和计算》一书中的第3章，练习，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

练习

概念和理解

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个金盘需要多少时间？将这一时间与科学家对宇宙从大爆炸至今的估计寿命比较，据此评价僧侣们的说法。

编程练习