《计算机操作系统第三章精选PPT.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第三章精选PPT.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机操作系统第三章第1页，此课件共54页哦第三章第三章算法算法基本工具和优化技巧基本工具和优化技巧利用算法的利用算法的基本机制基本机制循环和递归设计循环和递归设计算法算法利用算法的利用算法的基本操作基本操作提高算法效率的技巧提高算法效率的技巧利用数组提高算法质量利用数组提高算法质量建立高效的数学模型建立高效的数学模型31循环与递归循环与递归33算法优化基本技巧算法优化基本技巧32算法与数据结构算法与数据结构34优化算法的数学模型优化算法的数学模型第2页，此课件共54页哦311循环设计要点循环设计要点312 递归设计要点递归设计要点313递归与循环的比较递归与循环的比较31 循环与循环与递归递
2、归第3页，此课件共54页哦311 循环设计要点循环设计要点 1 1设计设计中要注意算法的效率中要注意算法的效率 2 2“自自顶顶向下向下”的的设计设计方法方法 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构 第4页，此课件共54页哦 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现形是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。描述各种相似的重复运算。1 1循环循环设计设
3、计中要注意算法的效率中要注意算法的效率第5页，此课件共54页哦【例例1 1】求求1/1!-1/3!+1/5!-1/7!+1/1!-1/3!+1/5!-1/7!+（-1-1）n+1/(2n-n+1/(2n-1)!1)!分析：此问题中既有累加又有累乘，准确地说累加分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。的对象是累乘的结果。数学模型数学模型1 1：Sn=Sn-1+Sn=Sn-1+（-1-1）n+1n+1/(2n-1)!/(2n-1)!算法设计算法设计1 1：多数初学者会直接利用题目中累加项通式，：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为：构造出循环体不变式为
4、：S=S+S=S+（-1-1）n+1/(2n-1)!n+1/(2n-1)!需要用二重循环来完成算法，算法需要用二重循环来完成算法，算法1 1如下：如下：第6页，此课件共54页哦算法如下：算法如下：求（求（-1-1）n+1 for(j=1;j=i+1;j=j+1)for(j=1;j=i+1;j=j+1)sign=sign*(-1);sign=sign*(-1);s=s+sign/t;s=s+sign/t;print(print(“Snm=Snm=”,s);,s);main()main()int i,n,j,sign=1;int i,n,j,sign=1;float s,t=1;float s,t
5、=1;input(n);input(n);s=1s=1；for(i=2;i=n;i=i+1)for(i=2;i=n;i=i+1)t=1;t=1;求求阶乘阶乘 for(j=1;j=2*i-1;j=j+1)for(j=1;j=2*i-1;j=j+1)t=t*j;t=t*j;sign=1;sign=1;第7页，此课件共54页哦算法分析算法分析：以上算法是以上算法是二重循环二重循环来完成来完成 ，但算法，但算法的效率却太低是的效率却太低是O（n2）。其其原原因因是是，当当前前一一次次循循环环已已求求出出7 7！，当当这这次次要要想想求求9 9！时时，没没必必要要再再从从1 1去去累累乘乘到到9 9，只
6、只需需要要充充分分利利用用前前一一次次的的结结果果，用用7 7！*8*98*9即即可可得得到到9 9！，模模型型为为A An n=A=An-1n-1*1/(2*n-*1/(2*n-2)*(2*n-1)2)*(2*n-1)。另另外外运运算算sign sign=sign sign*(-1);*(-1);总总共共也也要要进进行行n*(n-1)/2n*(n-1)/2次次乘乘法法，这这也也是是没没有有必必要要的的。下下面面我我们们就就进进行改进。行改进。第8页，此课件共54页哦数学模型数学模型2 2：S Sn n=S=Sn-1n-1+（-1-1）n+1n+1A An n；A An n=A=An-1 n-
7、1*1/(2*n-2)*(2*n-1)*1/(2*n-2)*(2*n-1)main()main()int i,n,sign;int i,n,sign;float s,t=1;float s,t=1;input(n);input(n);s=1s=1；sign=1;sign=1;for(i=2;i=n;i=i+1)for(i=2;i=n;i=i+1)或或 for(i=1;i=n-1;i=i+1)for(i=1;i=n-1;i=i+1)sign=-sign;sign=-sign;t=t*(2*i-2)*(2*i-1);t=t*2*i*(2*i+1);t=t*(2*i-2)*(2*i-1);t=t*2
8、*i*(2*i+1);s=s+sign/t;s=s+sign/t;s=s+sign/t;s=s+sign/t;print(print(“Sum=Sum=”,s);,s);第9页，此课件共54页哦算法说明算法说明2 2：构造循构造循环环不不变变式式时时，一定要注意循，一定要注意循环变环变量的意量的意义义，如当，如当i i不不是是项项数序号数序号时时（右（右边边的循的循环环中）有关中）有关t t的的累乘累乘式与式与i i是是项项数序号数序号时时就不能相同。就不能相同。算法分析：算法分析：按照数学模型按照数学模型2 2，只需，只需一重循环一重循环就能解决问题就能解决问题算法的算法的时间时间复复杂杂性
9、性为为O O（n n）。第10页，此课件共54页哦2 2“自自顶顶向下向下”的的设计设计方法方法 自自顶顶向下的方法是从全局走向局部、从向下的方法是从全局走向局部、从概略概略走向走向详详尽的尽的设计设计方法。自上而下是系方法。自上而下是系统统分解和分解和细细化的化的过过程。程。【例例2 2】编算法找出编算法找出10001000以内所有完数以内所有完数例例如如，2828的的因因子子为为1 1、2 2、4 4、7 7，1414，而而28=1+2+4+7+1428=1+2+4+7+14。因因此此2828是是“完完数数”。编编算算法法找找出出10001000之之内内的的所所有有完完数数，并并按按下下面
10、面格格式式输输出出其其因因子子：28 28 itits s factors factors are are 1 1，2 2，4 4，7 7，1414。第11页，此课件共54页哦1 1）这这里里不不是是要要质质因因数数，所所以以找找到到因因数数后后也也无无需需将将其其从从数数据据中中“除掉除掉”。2 2）每每个个因因数数只只记记一一次次，如如8 8的的因因数数为为1 1，2 2，4 4而而不不是是1 1，2 2，2 2，2 2，4 4。（注：本题限定因数不包括这个数本身）（注：本题限定因数不包括这个数本身）第12页，此课件共54页哦1）顶层算法 for(i=0;in;i=i+1)找第i行上最小的
11、元素t及所在列minj;检验t是否第minj 列的最大值，是则输出这个鞍点;2）找第i行上最小的元素t及所在列minj t=ai0;minj=1;for(j=1;jn;j=j+1)if(aijt)t=aij;minj=j;第13页，此课件共54页哦3）进一步细化判断i是否“完数”算法s=1for(j=2;ji;j=j+1)if(i mod j=0)(j是i的因素)s=s+j;if （s=i）i是“完数”;第14页，此课件共54页哦4 4）考虑输出格式）考虑输出格式判断判断i i是否是否“完数完数”算法算法 考考虑虑到到要要按按格格式式输输出出结结果果，应应该该开开辟辟数数组组存存储储数数据据i
12、 i的的所所有有因子，并记录其因子的个数，因此算法细化如下：因子，并记录其因子的个数，因此算法细化如下：定义数组定义数组a，s=1;k=0;for(j=2;ji;j=j+1)j=2;ji;j=j+1)if(i mod j=0)(j if(i mod j=0)(j是是i i的因素的因素)s=s+j;ak=j;k=k+1;s=s+j;ak=j;k=k+1;if if （s=is=i）按格式输出结果按格式输出结果 第15页，此课件共54页哦算法如下：算法如下：main()inti,k,j,s,a20;for(i=1;i=1000;i+)s=1;/*两个赋初值语句两个赋初值语句s=1,k=0k=0;一
13、定要位于外部循环的内部一定要位于外部循环的内部*/for(j=2;ji;j+)if(imodj)=0)s=s+j;ak=j;k+;if(i=s)print(s,“itsfactorsare:”,1);for(j=0;ik;j+)print(“,”,ak);第16页，此课件共54页哦【例例3 3】求一个矩阵的鞍点求一个矩阵的鞍点 (即在行上最小而在列上最大的点即在行上最小而在列上最大的点)。算法设计算法设计：1 1）在第一行找最小值，并记录其列号。在第一行找最小值，并记录其列号。2 2）然后验证其是否为所在列的最大值，如果是，则找到然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则
14、继续在下一行找最小值问题的解；否则，则继续在下一行找最小值 。第17页，此课件共54页哦for(i=0;in;i=i+1)找第i行上最小的元素t及所在列minj;检验t是否第minj 列的最大值，是则输出这个鞍点;t=ai0;minj=1;for(j=1;jn;j=j+1)if(aijt)t=aij;minj=j;1）顶层算法 2）找第i行上最小的元素t及所在列minj 第18页，此课件共54页哦3）检验t是否第minj 列的最大值，是，则输出这个鞍点;for(k=0;kt)break;if(kn)continue;print(“the result is a“,i，“”,minj,“=”，t
15、);考虑到会有无解的情况，设置标志量kz，kz=0代表无解，找到一个解后，kz被赋值为1，就不再继续找鞍点的工作。请读者考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍点。第19页，此课件共54页哦算法如下：算法如下：buck()inta1010;inti,j,k,minj,t,n=10,kz=0;/*minj代表当前行中最小值的列下标；设置标志量代表当前行中最小值的列下标；设置标志量kz*/readmtr(a,n);prntmtr(a,n);for(i=0;in;i+)t=ai0;minj=1;for(j=1;jn;j+)if(aijt)t=aij;minj=j;for(k=0
16、;kaiminj)break;if(kn)continue;print(“theresultisa“,i,“”,minj,“=”，aiminj);kz=1;break;if(kz=0)print(“nosolution!”);第20页，此课件共54页哦 对于不太熟悉的问题，其数学模型或“机械化操作步骤”的不易抽象，下面看一个由具体到抽象设计循环细节的例题。【例4】编写算法：打印具有下面规律的图形。1 5 2 8 6 3 10 9 7 4 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构第21页，此课件共54页哦算算法法设设计计：容容易易发发现现图图形形中中自自然然数数在在矩矩阵阵中中排排
17、列列的的规规律律，题题目目中中1 1，2 2，3 3，4 4所所在在位位置置我我们们称称为为第第1 1层层（主主对对角角线线），例例图图中中5 5，6 6，7 7所所在在位位置置我我们们称称为为第第二二层层，。一一般般地地，第第一一层层有有n n个元素，第二层有个元素，第二层有n-1n-1个元素个元素基基于于以以上上数数据据变变化化规规律律，以以层层号号作作为为外外层层循循环环，循循环环变变量量为为i i（范范围围为为1 1n n）；以以层层内内元元素素从从左左上上到到右右下下的的序序号号作作为为内内循循环环，循循环环变变量量为为j j（范范围围为为1 1n+1-in+1-i）。这这样样循循环
18、环的的执执行行过过程程正正好好与与“摆摆放放”自自然然数数的的顺顺序序相相同同。用用一一个个变变量量k k模模拟拟要要“摆摆放放”的的数数据据，下下面面的的问问题题就就是是怎怎么么样样将将数数据据存存储储到到对对应应的数组元素。的数组元素。第22页，此课件共54页哦 数数组组元元素素的的存存取取，只只能能是是按按行行、列列号号操操作作的的。所所以以下下面面用用由由具具体体到到抽抽象象设设计计循循环环的的“归归纳纳法法”，找找出出数数组组元元素素的的行行号号、列列号号与与层层号号i i及及层层内序号内序号j j的关系：的关系：1.1.每每层层内内元元素素的的列列号号都都与与其其所所在在层层内内的
19、的序序号号j j是是相相同同的的。因因为为每每层层的的序序号号是是从第一列开始向右下进行。从第一列开始向右下进行。2.2.元素的行与其所在的层号及在层内的序号均有关系元素的行与其所在的层号及在层内的序号均有关系,具体地：具体地：第一层行号第一层行号1 1n n，行号与，行号与j j同；同；第二层行号第二层行号2 2n n，行号比，行号比j j大大1 1；第三层行号第三层行号3 3n n，行号比，行号比j j大大2 2；行行号号起起点点随随层层号号i i增增加加而而增增加加，层层内内其其它它各各行行的的行行号号又又随随层层内内序序号号j j增加而增加，由于编号起始为增加而增加，由于编号起始为1
20、1，i i层第层第j j个数据的列下标为个数据的列下标为i-1+ji-1+j。综合以上分析综合以上分析,i,i层第层第 j j个数据对应的数组元素是个数据对应的数组元素是ai-1+jjai-1+jj。第23页，此课件共54页哦main()main()int i,j,a100100,n,k;int i,j,a100100,n,k;input(n);input(n);k=1;k=1;for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1)for(j=1;j=n+1-i;j=j+1)for(j=1;j=n+1-i;j=j+1)ai-1+jj=k;ai-1+jj=k;k=k+1;k=k
21、+1;for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1)print(print(“换行符换行符”););for(j=1;j=i;j=j+1)for(j=1;j0)/*0阶的汉诺塔问题当作停止条件阶的汉诺塔问题当作停止条件*/2)hanoi(n-1,a,c,b);3)输出输出“Movedise”,n.”frompile”,a,”to”b);4)haboi(n-1,c,b,a);5)endif第32页，此课件共54页哦【例例2 2】整数的分划问题整数的分划问题 对于一个正整数对于一个正整数n n的分划就是把的分划就是把n n写成一系列正整数之和的表达式。写成一系列正整数之和的
22、表达式。例如，对于正整数例如，对于正整数n=6n=6，它可以分划为：，它可以分划为：6 6 5+1 5+1 4+2,4+2,4+1+1 4+1+1 3+3,3+3,3+2+1,3+2+1,3+1+1+1 3+1+1+1 2+2+2,2+2+2,2+2+1+1,2+2+1+1,2+1+1+1+1 2+1+1+1+1 1+1+1+1+1+11+1+1+1+1+1 根据例子发现根据例子发现“包括第一行以后的数据不超过包括第一行以后的数据不超过6 6，包括第，包括第二行的数据不超过二行的数据不超过5 5，第六行的数据不超过，第六行的数据不超过1 1”。因此，定义一个函数因此，定义一个函数Q(n,m)Q
23、(n,m)，表示整数，表示整数n n的的“任何被加数都任何被加数都不超过不超过m m”的分划的数目的分划的数目 。第33页，此课件共54页哦模型建立：模型建立：一般地一般地Q(n.m)Q(n.m)有以下递归关系：有以下递归关系：1)1)Q(n,n)=1+Q(n,n-1)Q(n,n)=1+Q(n,n-1)（m=nm=n）Q(n,n-1)Q(n,n-1)表示表示n n的所有其他分划，即最大被加数的所有其他分划，即最大被加数m=n-1m=n-1的划分。的划分。2)2)Q(n,m)=Q(n,m-1)+Q(n-m,m)Q(n,m)=Q(n,m-1)+Q(n-m,m)(mn)(mn)Q(n,m-1)Q(n
24、,m-1)表示被加数中不包含表示被加数中不包含m m的分划的数目；的分划的数目；Q(n-m,m)Q(n-m,m)表示被加数中包含表示被加数中包含(注意不是小于注意不是小于)m)m的分划的数目，的分划的数目，递归的停止条件：递归的停止条件：1)1)Q(n,1)=1Q(n,1)=1，表示当最大的被加数是，表示当最大的被加数是1 1时，该整数时，该整数n n只有一种分划，即只有一种分划，即n n个个1 1相加；相加；2)2)Q(1,m)=1Q(1,m)=1，表示整数，表示整数n=1n=1只有一个分划，不管最大被加数的只有一个分划，不管最大被加数的上限上限m m是多大。是多大。第34页，此课件共54页
25、哦算法如下：算法如下：Divinteger(n,Divinteger(n,m)m)if if（n n 1 1 or or m m 1 1 ）Error(Error(“输入参数错误输入参数错误”)；else else if if（n n=1 1 or or m m=1 1）returnreturn（1 1）；）；else else if if（n n =10)print(n mod 10);n=n10;print(n);第38页，此课件共54页哦递归算法设计：递归算法设计：1 1）同同上上，算算法法从从低低位位到到高高位位逐逐位位求求出出各各位位数数字字并并输输出出，求求个个位位数数字字的的算算
26、式为式为 n mod 10n mod 10，下一步则是递归地求，下一步则是递归地求n10n10的个位数字。的个位数字。2 2）当）当n10n10时，时，n n为一位数停止递归。为一位数停止递归。递归算法如下：递归算法如下：f2(n)f2(n)if(n10)if(n=10)while(n=10)ai=n mod 10;ai=n mod 10;i=i+1;i=i+1;n=n10;n=n10;ai=n;ai=n;for(j=i;j=0;j=j-1)for(j=i;j=0;j=j-1)print(aj);print(aj);第41页，此课件共54页哦递归算法设计：递归算法设计：与与f2f2不不同同，递
27、递归归算算法法是是先先递递归归地地求求n10n10的的个个位位数数字字，然然后后再再求求个个位位数数字字n n的的个个位位数数字字并并输输出出。这这样样输输出出操操作作是是在在回回溯溯时时完完成成的的。递递归归停停止止条条件件与与f2f2相相同同为为n10n10。递归算法如下：递归算法如下：f4(n)f4(n)if(n10)if(n=n;i-)for(i=1;i=n;i-)for(j=1;j=n;j-)for(j=1;j=n;j-)for(k=1;k=n;k-)for(k=1;k=n;k-)if(ij)and(ik)and(ij)and(jk)if(ij)and(ik)and(ij)and(j
28、k)t=t+1;t=t+1;print(i,j,k);print(i,j,k);print(total=,t);print(total=,t);第46页，此课件共54页哦或者constitute2（）int n=5,r=3,i,j,k,t;t=0;for(i=1;i=n-r+1;i=i+1)for(j=i+1;j=n-r+2;j=j+1)for(k=j+1;k=k;i-)ak=i;if(k1)comb(i-1,k-1);elsefor(j=a0;j0;j-)print(aj);print(“换行符换行符”);constitute3()intn,r;print(“n,r=”);input(n,r
29、);if（rn）print(“Inputn,rerror!”);elsea0=r;comb(n,r);/调用递归过程调用递归过程/第52页，此课件共54页哦分析分析：算法算法2 2递归的深度是递归的深度是r r，每个算法要递归，每个算法要递归m-k+1m-k+1次，所以的时间复杂性是次，所以的时间复杂性是O（r*nr*n）。递递归归是是一一种种强强有有力力的的算算法法设设计计方方法法。递递归归是是一一种种比比循循环环更更强强、更更好好用用的的实实现现“重重复复操操作作”的的机机制制。因因为为递递归归不不需需要要编编程程者者（算算法法设设计计者者）自自己己构构造造“循循环环不不变变式式”，而而只只需需要要找找出出递递归归关关系系和和最最小小问问题题的的解解。递递归归在在很很多多算算法法策策略略中中得得以以运运用用，如：分治策略、动态规划、图的搜索等算法策略。如：分治策略、动态规划、图的搜索等算法策略。综合以上讨论，可以得出以下结论：综合以上讨论，可以得出以下结论：第53页，此课件共54页哦递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难第54页，此课件共54页哦