VC编程教程 第四章 算法策略

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第四章 基本的算法策略,4.1,迭代算法,4.2,蛮力算法,4.3,分而治之算法,4.4,贪婪算法,4.1,迭代算法,4.1.1,递推法,4.1.2,倒推法,4.1.3,迭代法解方程,4,1,1,递推,法,【,例,1】,兔子繁殖问题,问题描述：,一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。,问题分析：,因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数,(,用斜体数字表示,),显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：,一月 二月 三月 四月 五月 六月,1 1 1+,1,=2 2+,1,=3 3+,2,=5 5+,3,=8 ,算法,1,：,main(),int,i,a=1,b=1;,print(a,b);,for(i=1;i,=10;i+),c=a+b;,print(c);,a=b;,b=c,；,数学建模：,y,1,=y,2,=1,，,y,n,=y,n-1,+y,n-2,，,n=3,，,4,，,5,，,。,【,例,2】,求两个整数的最大公约数。,数学建模：,辗转相除法是根据递推策略设计的。,不妨设两个整数,ab,且,a,除以,b,商,x,余,c,；则,a-,bx,=c,，,不难看出,a,、,b,的最大公约数也是,c,的约数（一个数能整除等式左边就一定能整除等式的右边），则,a,、,b,的最大公约数与,b,、,c,的最大公约数相同。同样方法推出,b,、,c,的最大公约数与,，直到余数为,0,时，除数即为所求的最大公约数。,算法设计：,循环“不变式”,第一次,是求,a,、,b,相除的余数,c,，,第二次,还是求“,a”“b”,相除的余数，经,a=b,b=c,操作，就实现了第二次还是求“,a”“b”,相除的余数，这就找到了循环不变式。循环在余数,c,为,0,时结束。,算法如下：,main,（）,int,a,b;,input(a,b);,if(b=0),print(“data error”);,return;,else,c=a mod b;,while c0,a=b;,b=c;,c=a mod b;,print(b);,4.1.2,倒推法,所谓,倒推法,：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。,例,1,在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例,2,由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例,3,），则问题容易理解和解决。下面分别看这几个例子：,【,例,1】,猴子吃桃问题,一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，,到第,10,天时就只有一个桃子了，求原有多少个桃？,数学模型：,每天的桃子数为：,a10=1,a9=(1+a10)*2,a8=(1+a9)*2,a10=1,，,递推公式为：,ai,=(1+ai+1)*2 I=9,8,7,61,算法如下：,main(),int,i,s;,s=1;,for(i=9;i=1;i=i-1),s=(s+1)*2,print(s),；,4.2,蛮力法,4.2.1,枚举法,4.2.2,其它范例,蛮力法,是基于计算机运算速度快这一特性，在解决问题时采取的一种“懒惰”的策略。这种策略不经过（或者说是经过很少的）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还有,枚举法,、盲目搜索算法等，本节介绍,枚举法,和其它一些小的范例，第五章介绍盲目搜索算法。,4,2,1,枚举法,枚举,（,enumerate,）,法（穷举法）是,蛮力策略的一种表现形式,，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。,用枚举法解决问题，通常可以从两个方面进行算法设计：,1,）,找出枚举范围：分析问题所涉及的各种情况。,2,）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。,【,例,1】,百钱百鸡问题。中国古代数学家张丘建在他的,算经,中提出了著名的,“,百钱百鸡问题,”,：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何,?,算法设计,1,：,通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用,“,懒惰,”,的枚举策略进行算法设计：,设,x,，,y,，,z,分别为公鸡、母鸡、小鸡的数量。,尝试范围：由,题意给定共,100,钱要买百鸡，若全买公鸡最多买,100/5=,20,只，显然,x,的取值范围,120,之间；同理，,y,的取值范围在,133,之间，,z,的取值范围,在,1100,之间,。,约束条件：,x+y+z=100,且,5*x+3*y+z/3=100,算法,1,如下：,main(),int,x,y,z;for(x=1;x=20;x=x+1)for(y=1;y=34;y=y+1)for(z=1;z=100;z=z+1)if(100=x+y+z and 100=5*x+3*y+z/3)print(the cock number is,x),；,print(the hen number is,y),；,print(the chick number is z);,算法分析,：以上算法需要枚举尝试,20*34*100=68000,次。算法的效率显然太低,算法设计,2,：,在,公鸡（,x,）、,母鸡（,y,）,的数量,确定后，小鸡,的数量,z,就固定为,100-x-y,，,无需再进行枚举了,此时,约束条件只有一个：,5*x+3*y+z/3=100,算法,2,如下：,main(),int,x,y,z;for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1),z=100-x-y;if(z mod 3=0 and 5*x+3*y+z/3=100)print(the cock number is,x),；,print(the hen number is,y),；,print(the chick number is z);,算法分析：,以上算法只需要枚举尝试,20*33=660,次。实现时约束条件又限定,Z,能被,3,整除时，才会判断,“,5*x+3*y+z/3=100”,。,这样省去了,z,不整除,3,时的算术计算和条件,判断，,进一步提高了算法的效率。,4.3,分而治之算法,4.3.1,分治算法框架,4.3.2,二分法,4.3.3,二分法变异,4.3.4,其它分治方法,4,3,1,分治算法框架,1,算法设计思想,分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。,分治法的基本步骤在每一层递归上都有三个步骤：,1,）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；,2,）解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；,3,）合并：将已求解的各个子问题的解，逐步合并为原问题的解。,有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后（最小）的子问题的解。分治法的这类应用，又称为,“,减治法,”,。,多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。,2,适合用分治法策略的问题,当求解一个输入规模为,n,且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。,1,）,能将这,n,个数据分解成,k,个不同子集合，且得到,k,个子集合是可以独立求解的子问题，其中,1,kn,；,2,）,分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；,在求出这些子问题的解之后，就可以推解出原问题的解；,分治法的一般的算法设计模式如下：,Divide-and-,Conquer(int,n)/n,为问题规模,/,if,（,nn0,）,/n0,为可解子问题的规模,/,解子问题；,return(,子问题的解,),；,for,（,i=1;i=k;i+,）,/,分解为较小子问题,p1,p2,pk,/,yi,=Divide-and-Conquer(|Pi|);/,递归解决,Pi/T=MERGE(y1,y2,.,yk,);/,合并子问题,/,return(T);,其中,|P|,表示问题,P,的规模；,n0,为一阈值，表示当问题,P,的规模不超过,n0,时，问题已容易直接解出，不必再继续分解。算法,MERGE(y1,y2,.,yk,),是该分治法中的合并子算法，用于将,P,的子问题,P1,P2,.,Pk,的相应的解,y1,y2,.,yk,合并为,P,的解。在一些问题中不需要这一步。如析半查找、,4,3,2,中的例,1,、例,2,等。,