1、第9章 基本算法设计学习目标学习目标 掌握枚举、递推和递归算法的基本思想 熟练运用枚举、递推和递归算法设计程序，解决实际问题目录目录 9.1 枚举算法枚举算法 9.2 递推算法递推算法 9.3 递归算法递归算法9.1 9.1 枚举算法枚举算法9.1.1 9.1.1 枚举概述枚举概述9.1.29.1.2枚举枚举算法应用举例算法应用举例9.1.1 9.1.1 枚举枚举概述概述 枚举法是计算机求解问题最常用的方法之一，也是最简单、最直接的统计计数方法。枚举的枚举的概念概念 举法又称为穷举法、列举法；基本思想是逐一列出该问题可能涉及的所有情形，并根据问题的条件对各解进行逐个检验，从中挑选出符合条件的解
2、，舍弃不符合条件的解9.1.1 9.1.1 枚举概述枚举概述 枚举法的特点算法设计比较简单，只需要一一列举问题涉及的所有情形，一般规模的许多实际应用问题都可以使用枚举法求解9.1.1 9.1.1 枚举概述枚举概述 利用枚举法求解问题的利用枚举法求解问题的步骤步骤 确定枚举对象，根据问题的实际情况，确定哪个量为枚举对象；确定枚举范围，根据问题的实际情况，确定枚举对象的枚举范围，设计枚举循环；确定筛选条件，根据问题要求，确定对解的筛选条件；设计枚举程序，运行和调试，对结果进行分析、讨论。9.1.1 9.1.1 枚举概述枚举概述 枚举法枚举法实现实现 使用循环结构实现，在循环体中，根据求解的具体条件
3、，应用选择结构进行筛选，确定问题的解。9.1 9.1 枚举算法枚举算法9.1.1 9.1.1 枚举概述枚举概述9.1.29.1.2枚举枚举算法应用举例算法应用举例9.1.2 9.1.2 枚举算法应用枚举算法应用举例举例【例9-1】涂抹单据问题一张单据上有一个5位数组成的编号，万位数是1，百位数是8，个位数是9，千位数和十位数已经变得模糊不清。但知道这个5位数是67和59的倍数。请找出所有满足这些条件的5位数并输出。其算法可以表示如下：Step1：对枚举变量thousands赋初值为0；Step2：判断thousands9是否成立，若成立，则程序运行结束，否则转去执行Step3；Step3：对枚
4、举变量tens赋初值为0；Step4：判断tens9是否成立，若成立，则转去执行Step7，否则转去执行Step5；Step5：计算单据编号number的值number10809+thousands*1000+tens*10，如果(number mod 67=0)and(number mod 59=0)，则输出这个5位数；Step6：取枚举变量tens的下一个值tenstens+1，转去执行Step5；Step7：取枚举变量thousands的下一个值thousandsthousands+1，返回Step4。【例9-2】鸡兔同笼问题一个笼子里关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。
5、已知鸡和兔子的总数量为19，总腿数为44。请问鸡和兔子的数目分别是多少。问题分析：这道题目很显然可以用枚举法来解答，枚举对象为鸡、兔的数量，将它们分别设为chick、rabbit。下面就要确定枚举对象的枚举范围和筛选条件。依据题意，鸡、兔的数量均小于19，即chick、rabbit的枚举范围均为019。枚举对象应同时满足以下两个筛选条件：鸡和兔的总数量为19；鸡和兔的总腿数为44。则上述用关系表达式表示如下：(chick+rabbit=19)and(2*chick+4*rabbit=44)该问题涉及chick、rabbit两个变量的枚举，需要使用二重循环实现。其算法表示如下：Step1：对枚举
6、变量chick赋初值chick0；Step2：判断chick19是否成立，如果不成立，则转去执行Step3，否则程序运行结束；Step3：对枚举变量rabbit赋初值rabbit0；Step4：判断rabbit19是否成立，如果不成立，则转去执行Step5，否则，转去执行Step7；Step5：判断枚举变量chick、rabbit的取值是否满足筛选条件，若满足则输出chick、rabbit的值，否则执行Step6；Step6：取枚举变量rabbit的下一个值rabbitrabbit+1，转去执行Step4；Step7：取枚举变量chick的下一个值chickchick+1，转去执行Step2。
7、目录目录 9.1 枚举算法枚举算法 9.2 递推算法递推算法 9.3 递归算法递归算法9.2 9.2 递推算法递推算法在自然界中，所有事物都随着时间的推移呈现出微妙的变化。许多现象的变化是有规律可循的，这种规律往往呈现出前因后果的关系，即某些现象的变化和紧靠它前面的一个或一些结果密切相关。递推的思想正是体现了这一变化规律。9.2 9.2 递推算法递推算法9.2.1 9.2.1 递推概述递推概述9.2.29.2.2递推递推算法应用举例算法应用举例9.2.1 9.2.1 递推概述递推概述 递推算递推算法法 递推方法是一种简便高效的常见数学方法，它是利用问题本身所具有的一种递推关系求解问题的方法。9
8、.2.1 9.2.1 递推概述递推概述9.2.1 9.2.1 递推概述递推概述 递递推推方法方法递推方法正是利用问题本身所具有的递推关系进行求解的一种方法，利用递推方法求解问题的关键是确定问题的递推关系，即相邻数据项之间的关系。9.2.1 9.2.1 递推概述递推概述 递推求解递推求解步骤步骤 确定递推变量 建立递推关系 确定初始（边界）条件，即确定递推变量的初始（边界）值。对递推过程进行控制9.2.1 9.2.1 递推概述递推概述 递推方式递推方式 利用递推方法对问题求解，通常分为顺推和逆推两种。顺推算法 顺推是从前向后推，利用已知或已求得的第1，2，i-1项的解，推出第i的解，直到求得第n
9、的解。其算法步骤如下：Step1：设定问题规模为1，2，i-1的初始值，问题规模变量k初始为i；Step2：利用递推关系推出规模为k的解；Step3：如果kn是否成立，如果成立，则程序结束，否则转去执行Step5；Step5：利用递推关系计算数列第k项akak-1+ak-2；Step6：kk+1转Step4。逆推算法逆推就是从后向前推，利用已知或已求得的第n，n-1，i+1项的解，推出第i的解，直到求得第1项的解。其算法步骤如下：Step1：设定问题规模为n，n-1，i+1的初始值，问题规模变量k初始为i；Step2：利用递推关系推出规模为k的解；Step3：如果k1，则k递减，转Step2；
10、否则，输出规模为1的解。【例9-5】乘客人数的问题一辆公交车共6站，从第一站发车时车上已有n位乘客，到第二站先下了一半乘客，然后又上来4位乘客；到第三站也先下了一半乘客，又上来3位乘客，以后每到一站都先下去车上一半的乘客，然后又上来比前一站所上乘客少一个的乘客，到了终点站车上还有4人，问发车时车上的乘客有多少？分析：首先确定递推关系。由题意知第n站新上来的乘客有6-n个。记passenger为第n站最终的乘客数，则passenger-（6-n）恰好为第n-1站最终乘客数的一半，由此，得到递推关系式：passengeri-1=2*（passengeri-（6-n）已知终点站车上乘客数为4，因此，
11、得到该问题的边界条件passenger=4。其算法表示如下：Step1：分别对乘客人数变量passenger和车站编号变量n初始赋值为4和5；Step2：判断nn是否成立，如果成立，则程序运行结束；否则，转去执行Step5；Step5：计算第i张纸得到的孔数x4*x，并输出；Step6：ii+1，转Step4。【例9-7】猴子爬山问题一只顽皮的猴子在一座有20级台阶的山上爬山跳跃，猴子每步可跳跃1级或4级台阶，试求猴子爬上20级台阶有多少种不同的爬法。问题分析：本题是一个典型的顺推问题。如果设k级台阶的不同爬法共f（k）种，那么爬上20级台阶共f（20）种不同的爬法。当台阶数小于4时，只有一种
12、爬法，即f（1）=1；当有4级台阶时，有两种爬法，即f（4）=2。爬上20级台阶的不同爬法的数列为1，1，1，2，3，4，5，7，10，14，19，26，由此可见，本题推导得到不是一个斐波那契数列。该数列初始条件：f（1）=1，f（2）=1，f（3）=1，f（4）=2为方便保存递推得到的中间项的结果，利用一维数组保存数据。其算法表示如下：Step1：对数列初始条件赋值f11，f21，f31，f42；Step2：对循环变量k赋值为5；Step3：判断k20是否成立，如果成立，则输出20级台阶的爬法总数，即f20的值，否则转去执行Step4；Step4：利用递推关系求解fkfk-1+fk-4；St
13、ep5：kk+1，转Step3。【例9-8】读书问题小红读书，第一天读了全书的一半加2页，第二天读了剩下的一半加2页，以后天天如此，第六天读完了最后的3页，问全书有多少页？问题分析：首先确定递推关系。记ai为第i天读书前剩余的页数，由题意得知，ai=(ai+1+2)*2。由于第六天读完最后的三页，也就是第六天读书前剩余3页，即a6=3，由此确定了问题的边界条件。依据题意，全书总页数恰好为第一天读书前的页数，即a1，为此，需要使用逆推的方法求解。其算法表示如下：Step1：对书的页数赋初值为3，即a3；Step2：循环变量赋初值i5；Step3：判断i2时，对数列第n项F（n）的求解可以转化为推
14、到求解F（n-1）和F（n-2），而要求解F（n-1）和F（n-2），又可以推到求解F（n-3）和F（n-4），依次类推，直至计算F（1）和F（2），分别能立即得到结果是1。因此原问题和子问题之间的递归关系式：F（n）=F（n-1）+F（n-2）递归的边界条件为n=1或n=2时，F（n）=1。因此原问题和子问题之间的递归关系式：F（n）=F（n-1）+F（n-2）递归的边界条件为n=1或n=2时，F（n）=1。其算法的表示如下：递归子过程Fibonacci（int n，out result）Step1：判断n=1 or n=2是否成立，如果成立，则resultn，则程序运行结束，否则转去执行s
15、tep4；Step4：调用递归子程序求解数列的第i项Fibonacci（i，result）；Step5：输出第i项的值result；Step6：i-i+1。递归算法递归算法优缺点优缺点使用递归算法求解问题的优点在于：结构清晰、可读性强。缺点在于：执行的效率很低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或者内存溢出的窘境。9.3.2 9.3.2 递归算法应用举例递归算法应用举例【例9-11】用递归方法求解读书问题问题分析：记ai为第i天读书前剩余的页数，由题意得知，递归关系为ai=（ai+1+2）*2。第六天读完了最后的三页，即a6=3，由此得到递归的边界条件。要求全书总页数为第一天读
16、书前的页数，即a1。该题目是根据最终的结果计算初始条件，是一个逆向求解的过程。【例9-12】用递归方法实现二分查找问题。从键盘上输入已排好序的10个元素，在这10个元素中找出一个特定的元素data，若查找成功，则返回该元素的位置；否则，返回“No Found”信息。问题分析：利用序列有序的特点，取序列的中间元素和待查找元素比较，若相等，则查找成功；若待查找元素小于中间元素，则在序列的左半区继续查找；若待查找元素大于中间元素，则在序列的右半区继续查找。重复上述过程，直到查找成功，或所查找的区域无元素，则查找失败。本章小结本章小结本章介绍了枚举、递推、递归三种算法的基本思想以及在一些实际问题中的应用。通过本章的学习，读者应该掌握三种算法的基本思想，并能够使用这三种算法进行程序设计，解决实际问题。
