编程导论-以Python为舟

第5章熟练递归编程 第4章中讲解了递归函数以及递归思维，也带大家练习了很多递归的小程序，熟练递归编程是编程教育的重点！所以本章将讲解多个较为复杂和完整的例子，使得读者能进一步熟悉递归算法的思维。在本章的前面，首先讲解一个在解决问题中十分常用也非常重要的思想： 二分法思想。通过二分查找、求解算术平方根等小例子让大家熟悉二分法思想。然后再通过一些完整的实例来带大家熟练递归编程，如： 求两个数的*大公因数、中国余数定理、解线性方程组、排列组合问题等。其中排列问题和组合问题是本章的重点，我们希望通过讲解各种可用的求解方法来培养大家思考问题的方式并拓宽思路。相信从本章中读者也会渐渐体会到计算机思维和它的美丽。 5.1二分法求解问题 二分法思想在平时解决问题时十分重要，它可大大降低问题的复杂度，故本节首先讲解什么是二分法思想，然后通过几个小例子带领大家熟练掌握这一思想，并体会二分法思想的妙处。 5.1.1什么是二分法 何为“二分法”？首先来看一个小游戏： 以前电视台上有个很受大家欢迎的节目叫作“看商品，猜价格”，游戏规则是给出一件商品让你猜出它的准确价格，主持人给的提示只有“高了”或“低了”，如果在规定时间里猜中商品价格，这件商品就是你的了。例如主持人给出一个微波炉的价格介于200~1000元，它的实际价格是860元。 其中一种猜价格的方法为： 参赛者按照价格依次递增的顺序进行猜测，比如依次猜300、400、500、600、700、800，主持人都会给出“低了”的提示，接下来猜900，后主持人给出“高了”的提示，这时我们知道价格位于800~900，然后又从800开始递增地去猜，重复上述操作，直到猜中为止。 上述方法显然很慢，那么有没有一种快速而简单的方法呢？我们可以这样猜，**次猜200~1000中间的价格600元，这时主持人会给出“低了”的提示，我们立马知道价格在600~1000了，第二次猜600到1000的中间价格800元，这时主持人给出“低了”的提示，我们便知道价格在800~1000，第三次再取中间价格900元，主持人给出“高了”的提示，而此时我们只用了3次就把区间锁定在800~900了，利用这种方法再去猜800~900的数，直到猜中为止。 综上所述，第二种方法每次将猜测的区间缩小到原来的一半，明显好于**种方法。这种每次将解空间缩小为原来空间的一半，逐步逼近正确的解的方法 图51二分法思路图 就是二分法，如图51所示为二分法的思路图。有的同学可能会说本书前面的排序例子，比如归并排序、快速排序也是用了二分法，这样的看法不够全面，我们在排序中是先将问题分成两部分，然后分别对每部分进行处理，再将处理结果合并成*终的答案，是一种“先分后合，分而治之”的思想，严格说这是分治法，就如同在第4章中讲解用分治法的思想求数列的和、求数列的*小值和*大值一样； 而二分法主要强调的是“分”，其基本思想是，每次将搜索的区间减少一半，因此可以快速缩小搜索范围，区别是二分法“分而未合”。 5.1.2在有序序列中使用二分法查找元素位置 本节主要研究在给定的一个有序序列中如何快速找出某个给定的元素位置，简称为二分查找，5.1.1节的猜价格游戏其实就是二分查找的例子。那么如何进行二分查找？我们可以这样做： 每次取当前所剩序列的中间元素作为比较对象，若给定的值和中间元素相等，则查找成功； 若给定值小于中间元素，则在中间元素的左半区继续查找； 若给定值大于中间元素，则在中间元素的右半区继续查找。不断重复上述过程直到查找成功，或所查找的区域没有元素，查找失败。 上述二分查找方法的过程如图52所示，k为要查找的值，查找区间是r0到rn(有序区间)，我们选择区间中间的值rmid作为比较对象，若k=rmid则查找成功，若k>rmid，则在右半区进行查找，若k 图52折半查找的基本思想图解 本节将通过讲解在有序序列中查找和插入元素这两个小例子来带领大家理解二分法思想。 1. 在有序序列中查找元素位置(二分查找) 【问题描述】对于给定的有序序列L，在该序列中用二分法的思想查找元素k是否存在于L中。若存在，则返回索引值，否则返回-1或者False。 【解题思路】假定一个有序序列为L=［7,14,18,21,23,29,31,35,38,42,46,49,52］，利用二分查找的方法在该序列中查找值为14的元素。我们可以利用图53清晰地表示查找过程。*开始用变量low和high来标识当前查找的区间范围即为整个L，之后每次计算出该区间的中点mid=(low+high)//2，则将L［mid］的值与14做对比，若L［mid］>14，则将mid-1赋值给high； 若L［mid］ 图53二分查找过程 问题： 请各位同学想一想。为什么是将mid-1而不是mid赋值给high？同样，为什么是将mid+1而不是mid赋值给low？ 了解了二分法查找的过程，就可以方便地用程序实现了，如所示，BinSearch_ non_recursive函数有两个参数： L和k，该函数可实现在列表L中找元素k的位置的功能。在函数的开始，我们需要一些辅助变量： low表示待查找区间的起始位置，high表示结束位置。每次都取中间元素和k进行比较，若k比中间位置的元素小，则说明待查找的元素在左半区间，则令high=mid-1，继续执行循环； 若k比中间位置的元素大，则说明待查找的元素在右半区间，则令low=mid+1，继续执行循环； 若k和中间位置元素相等，则查找成功，可以直接返回中间位置mid，无须继续循环。当然，while循环要有终止条件： 当不满足low≤high时，即若出现low>high的情况，则表明没有找到k，查找失败，返回-1。 # def BinSearch_non_recursive(L,k): low=0;high=len(L)-1 while(low mid=(low+high)//2#注意整除符号 if k elif k>L［mid］: low=mid+1 else: return mid return -1 当然二分法查找的过程也可以用递归实现，递归的思路是要查找的元素k每次和列表中的中间元素比较，若不相等，则将查找区间分为左半区和右半区，若k小于中间元素，则在左半区继续查找； 若k大于中间元素，则在右半区继续查找。递归终止的条件是查找区间的中间元素为要查找元素k，即查找成功，或者查找区间为空，即查找失败。注意，在编写递归函数时需要返回两个值： **个返回值是布尔值，True表示找到，False表示没找到，第二个返回值表示所找到的元素在序列中的索引。分析到这里有的同学可能会问： 当前函数所返回的索引是折半后新序列的索引，并不是原序列的索引啊！没错，所以如果查找的是右半部分，还需要在返回索引时加上另一半序列的长度。程序实现如所示。 # def BinSearch(L,k): if L==［］:return False,-1 #没找到 if len(L)==1: if k==L［0］:return True,0 return False,-1 if k==L［len(L)//2］:return True,len(L)//2 if k else： flag,index=BinSearch(L［len(L)//2:］,k)#可否len(L)//2+1？ return flag,len(L)//2+index 函数BinSearch(L,k)表示在列表L中查找元素k，若L为空，则返回False、-1，表示查找失败，递归终止； 若L中只剩一个元素，则判断该元素是否和k相等，若相等则返回True以及k在当前L中的位置(即0)，查找成功，递归终止； 若不相等则返回False、-1，递归终止； 若L中元素个数大于1，则k和L的中间元素比较，若k等于L［len(L)//2］，则查找成功，返回True以及k在当前L中的位置len(L)//2，递归终止； 若k小于L［len(L)//2］，则继续调用BinSearch(L［0:len(L)//2］,k)，在L的左半区域继续查找，若k大于L［len(L)//2］，继续调用BinSearch(L［len(L)//2:］,k)，在L的右半区域继续查找，并将调用函数返回的元素位置加len(L)//2。 问题(见习题)要如何改写程序，使得若k大于L［len(L)//2］，调用BinSearch(L［len(L)//2+1:］,k)。注意，要改动return的索引len(L)//2+index。 兰兰： 为什么一定要用两个返回值呢？既然没有找到，则索引值可以返回-1，也就是说，可以用-1表示没有找到，那么**个布尔类型的返回值岂不是多余了？ 沙老师： 两个返回值是必需的！请仔细想一想，虽然在没有找到时会返回-1，但是这个-1会返回给上一层函数，而在计算右半部分的索引值时需要加上序列长度值的一半，所以一旦-1加上这个数之后就是一个正数，如果没有False标志，就无法判别是否真的找到了k这个值。所以再次提醒大家，递归函数的终止条件，包括终止的时候需要返回什么，很重要！ 练习题5.1.1如何改写程序使得上述递归函数的返回值只有一个。 【解题思路】上述递归函数之所以需要返回两个值，是因为在传递参数的过程中列表发生了改变，则其索引也相应地发生了变化，而我们要求的是原列表的索引，所以在对列表索引进行返回时会相应进行一定的加法运算而造成结果出错。所以，为了避免这种情况的发生，可以将新的参数列表在原列表中的起始位置作为参数进行传递。但是这就造成递归函数的参数与之前定义的不一致，所以可以通过嵌套函数的方式使得递归函数与外界的界面保持接口一致，且接口相对简洁。程序如所示。 # def binary_r0_search(L,a): def r0_search(L,index_min):