基本的算法策略ppt课件

1、第四章 根本的算法战略4.1 迭代算法概念 用变量的旧值递推出新值的处理问题的方法适宜的范围 数值计算类型1递推法 sn=sn-1+An2倒推法411 递推法 【例1】兔子繁衍问题问题描画：一对兔子从出生后第三个月开场，每月生一对小兔子。小兔子到第三个月又开场生下一代小兔子。假假设兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。问题分析：那么繁衍过程如下： 一月 二月 三月 四月 五月 六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 数学建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，。算法1： main( ) int i,a=1,b=1

2、; print(a,b); for(i=1;i=10;i+) c=a+b; print (c); a=b; b=c； 4.1.2 倒推法 所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。【例】猴子吃桃问题一只小猴子摘了假设干桃子，每天吃现有桃的一半多一个，到第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+

3、1*2 print (s)； 4.2 蛮力法 蛮力法是基于计算机运算速度快这一特性，在处理问题时采取的一种“懒惰的战略。这种战略不经过或者说是经过很少的思索，把问题的一切情况或一切过程交给计算机去一一尝试，从中找出问题的解。 运用 蛮力战略的运用很广，详细表现方式各异，数据构造课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力战略详细运用。421 枚举法 枚举 enumerate法穷举法是蛮力战略的一种表现方式，也是一种运用非常普遍的思想方法。它是根据问题中的条件将能够的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，假设超越

4、了我们所能忍受的范围，那么需求进一步思索，排除一些明显不合理的情况，尽能够减少问题能够解的列举数目。用枚举法处理问题，通常可以从两个方面进展算法设计： 1找出枚举范围：分析问题所涉及的各种情况。 2找出约束条件：分析问题的解需求满足的条件，并用逻辑表达式表示。【例】解数字迷： A B C A B A D D D D D D算法设计1：按乘法枚举1)枚举范围为： A：39A=1，2时积不会得到六位数,B：09, C：09 六位数表示为A*10000+B*1000+C*100+A*10+B， 共尝试800次。2)约束条件为： 每次尝试，先求5位数与A的积，再测试积的各位能否相 同，假设一样那么找到

5、了问题的解。 测试积的各位能否一样比较简单的方法是，从低位开场， 每次都取数据的个位，然后整除10，使高位的数字不断变 成个位，并逐一比较。 算法1如下：main int A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A=9; A+) for(B=0; B=9; B+) for(C=0; C=9; C+) F=A*10000+B*1000+C*100+A*10+B; E=F*A； E1=E; G1=E1 mod 10; for(i=1; i=5; i+) G2=G1; E1=E1/10; G1= E1 mod 10; if(G1G2 ) break; if(i=6) pri

6、nt( F，*，A，=，E); 4.3 分而治之算法431 分治算法框架 1算法设计思想分治法求解问题的过程是，将整个问题分解成假设干个小问题后分而治之。假设分解得到的子问题相对来说还太大，那么可反复运用分治战略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐渐合并这些子问题的解，从而得到问题的解。分治法的根本步骤在每一层递归上都有三个步骤： 1分解：将原问题分解为假设干个规模较小，相互独立，与原问题方式一样的子问题； 2处理：假设子问题规模较小而容易被处理那么直接解，否那么再继续分解为更小的子问题，直到容易处理； 3合并：将已求解的各个子问题的解，逐渐合并为原问题的解

7、。阐明： 有时问题分解后，不用求解一切的子问题，也就不用作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不用求解了，问题的解就是最后最小的子问题的解。分治法的这类运用，又称为“减治法。 多数问题需求一切子问题的解，并由子问题的解，运用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。 2适宜用分治法战略的问题当求解一个输入规模为n且取值又相当大的问题时，用蛮力战略效率普通得不到保证。假设问题能满足以下几个条件，就能用分治法来提高处理问题的效率。1 能将这n个数据分解成k个不同子集合，且得到k个子集合是可以独立求

8、解的子问题，其中1kn；2 分解所得到的子问题与原问题具有类似的构造，便于利用递归或循环机制；在求出这些子问题的解之后，就可以推解出原问题的解； 432 二分法 不同于现实中对问题或任务的分解，能够会思索问题或任务的重点、难点、承当人员的才干等来进展问题的分解和分配。在算法设计中每次一个问题分解成的子问题个数普通是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解战略，数据构造课程中的折半查找、归并排序等算法都是采用此战略实现的。分治法的普通的算法设计方式如下：Divide-and-Conquer(int n) /n为问题规模

9、/ 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); 【例1】金块问题： 老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较分量的仪器，我们希望用最少的比较次数找出最重的金块。算法设计1：比较简单的方法是逐个的进展比较查找。先拿两块比较分量，留下重的一个与下一块比较，直到全部比较终了，

10、就找到了最重的金子。算法类似于一趟选择排序， 算法如下：maxmin( float a,int n) max=min=a1; for(i=2; i=n ;i+ ) if(max ai) min=ai; 算法分析1：算法中需求n-1次比较得到max。最好的情况是金块是由小到大取出的，不需求进展与min的比较，共进展n-1次比较。最坏的情况是金块是由大到小取出的，需求再经过n-1次比较得到min算法设计2:在含nn是2的幂n=2个元素的集合中寻觅极大元和极小元。用分治法二分法：1 将数据等分为两组两组数据能够差1，2递归分解直到每组元素的个数2，可简单地找到最大小值。3回溯时将分解的两组解大者取大

11、，小者取小，合并为当前问题的解。算法2 递归求取最大和最小元素 float an;maxmin int i, int j ,float &fmax, float &fminint mid; float lmax, lmin, rmax, rmin;if (i=j) fmax= ai; fmin=ai;else if (i=j-1) if(airmax) fmax=lmax;else fmax=rmax;if(lminrmin) fmin=rmin;else fmin=lmin; 【例】大整数乘法在某些情况下，我们需求处置很大的整数，它无法在计算机硬件能直接允许的范围内进展表示和处置。假设用浮点

12、数来存储它，只能近似地参与计算，计算结果的有效数字会遭到限制。假设要准确地表示大整数，并在计算结果中要求准确地得到一切位数上的数字，就必需用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进展两个n位大整数的乘法运算。算法设计：设X和Y都是n位的二进制整数，如今要计算它们的乘积X*Y。图4-10 大整数X和Y的分段按照乘法分配律，分解后的计算过程如下：记：X=A*2n/2+B ，Y=C*2n/2+D。这样，X和Y的乘积为：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D(1) T1=1 Tn=4T(n/2) 2 由此递归式迭代过程如下

13、：T(n)=4T(n/2) =4(4T(n/4)T(n/4) =16*T(n/8) = =O4k= O(nlog4) =On2所以可得算法的时间复杂度为T(n)=O(n2)。模型改良：可以把X*Y写成另一种方式：X*Y=A*C*2n+(A-B)(D-C)+AC+BD*2n/2+B*D (3)式(3)看起来比式(1)复杂，但它仅需做3次n/2位整数的乘法：AC，BD和(A-B)(D-C)，6次加、减法和2次移位。由此可得: (4)用解递归方程的迭代公式法，无妨设n=2k： T(n)=3T(n/2) =3(3T(n/4) =9(T(n/8) = =3k +3k-1 *2c+3k-2 *4c+3c2k-1+c2k = O(nlog3)那么得到T(n)=O(nlog3)=O(n1.59)。434 其它分治方法 【例】选择问题： 对于给定的n 个元素的数组a0:n-1，要求从中找出第k小的元