预备知识-含猴子吃桃问题求解的迭代算法(详见第5章)-20161003.docx

预备知识构造性是计算机软硬件系统的最根本特征，而递归和迭代是最具有代表性的构造性数学方法，它广泛地应用于计算学科各个领域，理解递归和迭代的基本思想有助于今后的学习。递归和迭代密切相关，实现递归和迭代的基础基于以下一个事实。不少序列项常常可以用这样的方式得到：由an1得到an，按这样的法则，可以从一个已知的首项开始，有限次地重复做下去，最后产生一个序列。该序列是递归和迭代运算的基础。1. 递归递归不仅是数学中的一个重要概念，也是计算技术中重要的概念之一。20世纪30年代，可计算的递归函数理论与图灵机、演算和POST规范系统等理论一起为计算理论的建立奠定了基础。在计算技术中，与递归有关的概念有递归关系、递归数列、递归过程、递归算法、递归程序、递归方法。（1）递归关系指的是一个数列的若干连续项之间的关系。（2）递归数列指的是由递归关系所确定的数列。（3）递归过程指的是调用“自身”的过程。（4）递归算法指的是包含递归过程的算法。（5）递归程序指的是直接或间接调用“自身”的程序。（6）递归方法（也称递推法）是一种在“有限”步骤内，根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素（如数或函数）的方法。在以上有关递归概念的定义中，调用自身中的“自身”两个字加了引号。若不加引号，就会出现循环定义的问题。事实上，递归定义从来不是以某一事物自身来定义的，而是以比自身简单一些的说法来定义。在计算中，这种比自身简单的说法就是要在计算结构相同的情况下，使计算的规模小于自身。递归是一个重要的概念，然而，对于刚入大学的学生来说，理解起来却有一定的困难，为了更好地理解递归思想，我们先给出一个简单的例子。例5.21 计算56。计算方法之一：6，6+6=12，12+6=18，18+6=24，24+6=30。计算方法之二：56，46，36，26，16；16+6=12，12+6=18，18+6=24，24+6=30。方法之二从56开始计算，假设一个刚学乘法的小学生计算不出这个数，那么，这个小学生一般会先计算46，然后再加6就可以了，若仍计算不出，则会再追溯到36，直到16，然后，再依次加6，最后得到30。这种计算方法其实就反映了一种递归的思想，这个例子还可以用更一般的递归关系表示：an=Can1+g(n)，2，3，4，其中，C是已知常数，g(n)是一个已知数列。如果已知an1就可以确定an。从数学归纳法的角度来看，这相当于数学归纳法归纳步骤的内容。但仅有这个关系还不能确定这个数列，若使它完全确定，还应给出这个数列的初始值a1，相当于数学归纳法归纳基础的内容。与数学归纳法相对应，递归由递归基础和递归步骤两部分组成。数学归纳法是一种论证方法，递归是算法和程序设计的一种实现技术，涉及递归定义的证明通常采用数学归纳法。若给出阶乘F(n)=n!的递归定义：F(0)=1递归基础F(n)=nF(n1)，n=1，2，3，递归步骤可以据此给出其Raptor程序实现：2. 迭代“迭”是屡次和反复的意思，“代”是替换的意思，合起来，“迭代”就是反复替换的意思。在程序设计中，为了处理重复性计算的问题，最常用的方法就是迭代方法，主要是循环迭代。迭代与递归有着密切的联系，甚至，一类如X0=a，Xn+1=f(n)的递归关系也可以看作是数列的一个迭代关系。可以证明，迭代程序都可以转换为与它等价的递归程序，反之，则不然。就效率而言，递归程序的实现要比迭代程序的实现耗费更多的时间和空间。因此，在具体实现时，又希望尽可能将递归程序转化为等价的迭代程序。前面介绍的阶乘F(n)=n!，其迭代法Raptor实现如下：下面再介绍一个容易被误判为递归的迭代实例猴子偷桃问题。猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就多吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半多一个。第10天只剩一个桃子，求第一天共摘下来多少个桃子？请设计一个程序求解该问题。假设an表示第n天摘下的桃子数量，分析可以得到第n-1天摘下的桃子数量为an-1=2(an+1)，通过此递推公式得到每天的桃子数量如下表所示：天数n12345678910桃子数量an15347663821909446221041递推方向 递推也是一种迭代，但是往往被人误以为是递归（递归是自己调用“自己”，递推不是）。因此，使用Raptor实现上述猴子偷桃问题，其迭代程序（递推程序）如下图所示：