基本的算法策略

第四章基本的算法策略4.1迭代算法•概念用变量的旧值递推出新值的解决问题的方法•适合的范围数值计算•类型（1）递推法sn=sn-1+An（2）倒推法4．1．1递推法【例1】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。问题分析：则繁殖过程如下：一月二月三月四月五月六月……111+1=22+1=33+2=55+3=8……数学建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，……。算法1：main(){inti,a=1,b=1;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）*2I=9,8,7,6……1算法如下：main(){inti,s;s=1;for(i=9;i=1;i=i-1)s=(s+1）*2print(s)；}4.2蛮力法•蛮力法是基于计算机运算速度快这一特性，在解决问题时采取的一种“懒惰”的策略。这种策略不经过（或者说是经过很少的）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。•应用蛮力策略的应用很广，具体表现形式各异，数据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。4．2．1枚举法枚举（enumerate）法（穷举法）是蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。【例】解数字迷：ABCAB×ADDDDDD算法设计1：按乘法枚举1)枚举范围为：A：3——9（A=1，2时积不会得到六位数）,B：0——9,C：0——9六位数表示为A*10000+B*1000+C*100+A*10+B，共尝试800次。2)约束条件为：每次尝试，先求5位数与A的积，再测试积的各位是否相同，若相同则找到了问题的解。测试积的各位是否相同比较简单的方法是，从低位开始，每次都取数据的个位，然后整除10，使高位的数字不断变成个位，并逐一比较。算法1如下：main（）{intA,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=E1mod10;for(i=1;i=5;i++){G2=G1;E1=E1/10;G1=E1mod10;if(G1G2)break;}if(i=6)print(F，”*”，A，”=”，E);}}4.3分而治之算法4．3．1分治算法框架1．算法设计思想分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。分治法的基本步骤在每一层递归上都有三个步骤：1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2）解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；3）合并：将已求解的各个子问题的解，逐步合并为原问题的解。说明：有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后（最小）的子问题的解。分治法的这类应用，又称为“减治法”。多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。2．适合用分治法策略的问题当求解一个输入规模为n且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。1）能将这n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1＜k≤n；2）分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；在求出这些子问题的解之后，就可以推解出原问题的解；4．3．2二分法不同于现实中对问题（或工作）的分解，可能会考虑问题（或工作）的重点、难点、承担人员的能力等来进行问题的分解和分配。在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。分治法的一般的算法设计模式如下：Divide-and-Conquer(intn)/n为问题规模/{if（n≤n0）/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：比较简单的方法是逐个的进行比较查找。先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序，算法如下：maxmin(floata[],intn){max==min=a[1];for(i=2;i=n;i++)if(maxa[i])max=a[i];elseif(mina[i])min=a[i];}算法分析1：算法中需要n-1次比较得到max。最好的情况是金块是由小到大取出的，不需要进行与min的比较，共进行n-1次比较。最坏的情况是金块是由大到小取出的，需要再经过n-1次比较得到min算法设计2:在含n（n是2的幂（n=2））个元素的集合中寻找极大元和极小元。用分治法（二分法）：1）将数据等分为两组（两组数据可能差1），2）递归分解直到每组元素的个数≤2，可简单地找到最大（小）值。3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。算法2递归求取最大和最小元素floata[n];maxmin（inti,intj,float&fmax,float&fmin）{intmid;floatlmax,lmin,rmax,rmin;if(i=j){fmax=a[i];fmin=a[i];}elseif(i=j-1)if(a[i]a[j]){fmax=a[j]；fmin=a[i];}else{fmax=a[i];fmin=a[j];}else{mid=(i+j)/2;maxmin（i，mid，lmax，lmin）;maxmin（mid+1，j，rmax，rmin）;if(lmaxrmax)fmax=lmax;elsefmax=rmax;if(lminrmin)fmin=rmin;elsefmin=lmin;}【例】大整数乘法在某些情况下，我们需要处理很大的整数，它无法在计算机硬件能直接允许的范围内进行表示和处理。若用浮点数来存储它，只能近似地参与计算，计算结果的有效数字会受到限制。若要精确地表示大整数，并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个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)T（1）=1T（n）=4T(n/2)（2）由此递归式迭代过程如下：T(n)=4T(n/2)=4(4T(n/4)）＝４＊４T(n/4)=16*４T(n/8)=……=O（4k）=O(nlog4)=O（n2）所以可得算法的时间复杂度为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)。4．3．4其它分治方法【例】选择问题：对于给定的n个元素的数组a[0:n-1]，要求从中找出第k小的元素。问题分析：选择问题的一个应用就是寻找中值元素，此时k=[n/2]。快速排序算法来解决选择问题，一趟排序分解出的左子集中元素个数nleft,可能是以下几种情况：1）nleft=k-1，则分界数据就是选择问题的答案。2）nleftk-1，则选择问题的答案继续在左子集中找，问题规模变小了。3）nleftk-1，则选择问题的答案继续在右子集中找，问题变为选择第k-nleft-1小的数，问题的规模也变小了。