计算机操作系统第三章精选文档.ppt

《计算机操作系统第三章精选文档.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第三章精选文档.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机操作系统第三章本讲稿第一页，共五十四页第三章第三章算法算法基本工具和优化技巧基本工具和优化技巧利用算法的利用算法的基本机制基本机制循环和递归设计循环和递归设计算法算法利用算法的利用算法的基本操作基本操作提高算法效率的技巧提高算法效率的技巧利用数组提高算法质量利用数组提高算法质量建立高效的数学模型建立高效的数学模型31循环与递归循环与递归33算法优化基本技巧算法优化基本技巧32算法与数据结构算法与数据结构34优化算法的数学模型优化算法的数学模型本讲稿第二页，共五十四页311循环设计要点循环设计要点312 递归设计要点递归设计要点313递归与循环的比较递归与循环的比较31 循环与循环与递归递

2、归本讲稿第三页，共五十四页311 循环设计要点循环设计要点 1 1设计设计中要注意算法的效率中要注意算法的效率 2 2“自自顶顶向下向下”的的设计设计方法方法 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构 本讲稿第四页，共五十四页 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现形式是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去描述各的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。种相似的重复运算。1 1循环循环设计设

3、计中要注意算法的效率中要注意算法的效率本讲稿第五页，共五十四页【例例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如下：如下：本讲稿第六页，共五十四页算法如下：算法如下：求（求（-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;本讲稿第七页，共五十四页算法分析算法分析：以上算法是以上算法是二重循环二重循环来完成来完成 ，但算法，但算法的效率却太低是的效率却太低是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次次乘乘法法，这这也也是是没没有有必必要要的的。下下面面我我们们就就进进行改进。行改进。本讲稿第八页，共五十四页数学模型数学模型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);本讲稿第九页，共五十四页算法说明算法说明2 2：构造循构造循环环不不变变式式时时，一定要注意循，一定要注意循环变环变量的意量的意义义，如当，如当i i不是不是项项数序号数序号时时（右（右边边的循的循环环中）有关中）有关t t的的累乘累乘式与式与i i是是项项数序号数序号时时就就不能相同。不能相同。算法分析：算法分析：按照数学模型按照数学模型2 2，只需，只需一重循环一重循环就能解决问题就能解决问题算法的算法的时间时间复复杂杂性

9、性为为O O（n n）。本讲稿第十页，共五十四页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。本讲稿第十一页，共五十四页1 1）这这里里不不是是要要质质因因数数，所所以以找找到到因因数数后后也也无无需需将将其其从从数数据据中中“除掉除掉”。2 2）每每个个因因数数只只记记一一次次，如如8 8的的因因数数为为1 1，2 2，4 4而而不不是是1 1，2 2，2 2，2 2，4 4。（注：本题限定因数不包括这个数本身）（注：本题限定因数不包括这个数本身）本讲稿第十二页，共五十四页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;本讲稿第十三页，共五十四页3）进一步细化判断i是否“完数”算法s=1for(j=2;ji;j=j+1)if(i mod j=0)(j是i的因素)s=s+j;if （s=i）i是“完数”;本讲稿第十四页，共五十四页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）按格式输出结果按格式输出结果 本讲稿第十五页，共五十四页算法如下：算法如下：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);本讲稿第十六页，共五十四页【例例3 3】求一个矩阵的鞍点求一个矩阵的鞍点 (即在行上最小而在列上最大的点即在行上最小而在列上最大的点)。算法设计算法设计：1 1）在第一行找最小值，并记录其列号。在第一行找最小值，并记录其列号。2 2）然后验证其是否为所在列的最大值，如果是，则找然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则继续

14、在下一行找最小值到问题的解；否则，则继续在下一行找最小值 。本讲稿第十七页，共五十四页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 本讲稿第十八页，共五十四页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，就不再继续找鞍点的工作。请读者考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍点。本讲稿第十九页，共五十四页算法如下：算法如下：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!”);本讲稿第二十页，共五十四页 对于不太熟悉的问题，其数学模型或“机械化操作步骤”的不易抽象，下面看一个由具体到抽象设计循环细节的例题。【例4】编写算法：打印具有下面规律的图形。1 5 2 8 6 3 10 9 7 4 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构本讲稿第二十一页，共五十四页算算法法设设计计：容容易易发发现现图图形形中中自自然然数数在在矩矩阵阵中中排排

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模模拟拟要要“摆摆放放”的的数数据据，下下面面的的问问题题就就是是怎怎么么样样将将数数据据存存储储到到对对应应的的数数组组元素。元素。本讲稿第二十二页，共五十四页 数数组组元元素素的的存存取取，只只能能是是按按行行、列列号号操操作作的的。所所以以下下面面用用由由具具体体到到抽抽象象设设计计循循环环的的“归归纳纳法法”，找找出出数数组组元元素素的的行行号号、列列号号与与层层号号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。本讲稿第二十三页，共五十四页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

21、=k+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本讲稿第三十二页，共五十四页【例例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,

23、m)Q(n,m)，表示整数，表示整数n n的的“任何被加数都不任何被加数都不超过超过m m”的分划的数目的分划的数目 。本讲稿第三十三页，共五十四页模型建立：模型建立：一般地一般地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

24、)Q(n,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是多大。是多大。本讲稿第三十四页

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);本讲稿第三十八页，共五十四页递归算法设计：递归算法设计：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);本讲稿第四十一页，共五十四页递归算法设计：递归算法设计：与与f2f

27、2不不同同，递递归归算算法法是是先先递递归归地地求求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(i

28、j)and(jk)t=t+1;t=t+1;print(i,j,k);print(i,j,k);print(total=,t);print(total=,t);本讲稿第四十六页，共五十四页或者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=”);i

29、nput(n,r);if（rn）print(“Inputn,rerror!”);elsea0=r;comb(n,r);/调用递归过程调用递归过程/本讲稿第五十二页，共五十四页分析分析：算法算法2 2递归的深度是递归的深度是r r，每个算法要递归，每个算法要递归m-k+1m-k+1次，所以的时间复杂性是次，所以的时间复杂性是O（r*nr*n）。递递归归是是一一种种强强有有力力的的算算法法设设计计方方法法。递递归归是是一一种种比比循循环环更更强强、更更好好用用的的实实现现“重重复复操操作作”的的机机制制。因因为为递递归归不不需需要要编编程程者者（算算法法设设计计者者）自自己己构构造造“循循环环不不变变式式”，而而只只需需要要找找出出递递归归关关系系和和最最小小问问题题的的解解。递递归归在在很很多多算算法法策策略略中中得得以以运运用用，如如：分分治治策策略略、动动态态规规划划、图图的的搜搜索等算法策略。索等算法策略。综合以上讨论，可以得出以下结论：综合以上讨论，可以得出以下结论：本讲稿第五十三页，共五十四页递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难本讲稿第五十四页，共五十四页