算法设计与分析第三章1循环与递归.ppt

第三章 算法基本工具和优化技巧 第三章 算法基本工具和优化技巧 利用算法的基本机制——循环和递归设计算法 利用算法的基本操作提高算法效率的技巧 利用数组提高算法质量 建立高效的数学模型 本章主要讲解如何充分利用这些基本的程序设计技术设计高质量的算法，在程序设计与算法设计之间起承上启下的作用 3.1 循环与递归 【例1】求1/1!-1/3!+1/5!-1/7!+…+（-1）n+1/(2n-1)! 分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。数学模型1：Sn=Sn-1+（-1）n+1/(2n-1)!算法设计1：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为： S=S+（-1）n+1/(2n-1)!需要用二重循环来完成算法，算法1如下： 算法如下： 算法分析： 以上算法是二重循环来完成 ，但算法的效率却太低是O（n2）。 当前一次循环已求出7！，当这次要想求9！时，没必要再从1去累乘到9，只需要充分利用前一次的结果，用7！*8*9即可得到9！，模型为An=An-1*1/((2*n-2)*(2*n-1)。另外运算sign = sign *(-1);总共也要进行n*(n-1)/2次乘法，这也是没有必要的。下面我们就进行改进。 数学模型2：Sn=Sn-1+（-1）n+1An； An=An-1 *1/((2*n-2)*(2*n-1)) 算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O（n）。 算法说明2 2．“自顶向下”的设计方法 自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的过程。 【例2】编算法找出1000以内所有完数 例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28 it’s factors are 1，2，4，7，14。 4）考虑输出格式—判断i是否“完数”算法 考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下： 算法如下： 【例3】求一个矩阵的鞍点 (即在行上最小而在列上最大的点)。 算法设计： 1）在第一行找最小值，并记录其列号。 2）然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则继续在下一行找最小值 …… 。 算法如下： 3．由具体到抽象设计循环结构 算法设计： 3．1．2 递归设计要点 递归的关键 两个经典的递归例题： 【例1】汉诺塔问题 【例2】整数的分划问题 【例1】汉诺塔问题描述： 算法设计： 如何找出大规模问题与小规模问题的关系，从而实现递归呢？ 把n个盘子抽象地看作“两个盘子”，上面“一个”由1——n-1号组成，下面“一个”就是n号盘子。移动过程如下： 第一步：先把上面“一个”盘子以a基座为起点借助b基座移到c基座。 第二步：把下面“一个”盘子从a基座移到b基座。 第三步：再把c基座上的n-1盘子借助a基座移到b基座。 函数设计 算法如下： 【例2】整数的分划问题 模型建立： 算法如下： 3.1.3 递归与循环的比较 循环算法设计：从题目中我们并不能获知正整数的位数，再看题目的要求，算法应该从低位到高位逐位求出各位数字并输出。详细设计如下：1）? 求个位数字的算式为 n mod 102）? 为了保证循环体为“不变式”，求十位数字的算式仍旧为n mod 10，这就要通过算式n=n\10，将n的十位数变成个位数。 【例3】找出n个自然数(1,2,3,…,n)中r个数的组合。 算法设计1： 1）n个数中r的组合，其中每r个数中，数不能相同； 2）任何两组组合的数，所包含的数也不应相同。 例如，５、４、３与３、４、５。为此，约定前一个数应小于后一个数。将上述两条作为约束条件； 3）当r=3时，可用三重循环进行枚举。 算法1如下： 分析n=5,r=3时的10组组合数 1）首先固定第一个数５，其后就是n=4,r=2的组合数，共6个组合。 2）其次固定第一个数4，其后就是n=3,r=2的组合数，共3个组合。 3）最后固定第一个数3，其后就是n=2,r=2的组合数，共1个组合。 至此找到了“５个数中３个数的组合”与“４个数中２个数的组合、3个数中２个数的组合、2个数中２个数的组合”的递归关系。 则递归算法的三个步骤为： 递归算法如下： 古代有一个梵塔，塔内有3个基座A、B、C，开始时A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移到B座，但每次只允许移动一个