计算机常用算法.ppt

《计算机常用算法.ppt》由会员分享，可在线阅读，更多相关《计算机常用算法.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计计 算算 机机 常常 用用 算算 法法安吉实验初中安吉实验初中 陈国锋陈国锋7、动态规划、动态规划1、穷举法（枚举法）、穷举法（枚举法）2、递归法、递归法3、回溯法、回溯法 4、模拟法、模拟法 6、分治法、分治法5、贪心法贪心法枚举法枚举法穷举法穷举法枚举法（通常也称为穷举法）是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。枚举的思想往往是最容易想到的一种解题策略，枚举法从本质上说是一种搜索的算法，但适用枚举法解题必须满足下列条件：1）可预先确定解元素的个数n,且问题的规模不是特别

2、大；2）对于每个解变量A1，A2，。An的可能值必须为一个连续的值域。枚举法的算法流程：设ai1为解变量Ai的最小值；aik为解变量的最大值；其中1in.A1a11,a12,a1KA2a21,A22,A2KAiai1,Ai2,AiKAnan1,An2,AnK我们称解变量为枚举变量。例如某问题的枚举变量有三个：A1，A2，A3。A11，2，A22，3，4，A35，6，7则问题的可能解为（A1，A2，A3）（1，2，5），（1，2，6），（1，2，7），（1，3，5），（1，3，6），（1，3，7），（1，4，5），（1，4，6），（1，4，7），（2，2，5），（2，2，6），（2，2，7），（

3、2，3，5），（2，3，6），（2，3，7），（2，4，5），（2，4，6），（2，4，7）在上述18个可能解的集合中，满足问题给定的检验条件的解元素即为问题的解。枚举法的优化方法：1）减少枚举的变量，在使用枚举法之前，先考虑一下解元素之间的关联，将一些非枚举不可的解元素列为枚举变量，其他元素通过计算得出解元素的可能值。例1、巧妙填数。将19这9个数字填入到9个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三个三位数是第一行的2倍，第三行的三位数是第一行的三倍，应怎样填数。如图1923845762）减少枚举变量的值域3）分解约束条件，将拆分的约束条件嵌套在相应的循环体间。本题目有9

4、个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合条件的即为解。因此可以用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。例2、有四个学生，上地理课时提出我国四大淡水湖的排序如下：甲：洞庭湖最大，洪泽湖最小，鄱阳湖第三；乙：洪泽湖最大，洞庭湖最小，鄱阳湖第二，太湖第三；丙：洪泽湖最小，洞庭湖第三；丁：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三；对于各个湖泊应处的地位，每个人只说对了一个。根据以上情况，编程序判断各个湖泊应处的地位。算法分析：本题是一个逻辑判断题，一般的

5、逻辑判断题都采用枚举法进行解决。四个湖的大小分别可以有4！=24种排列可能，因为24比较小，因此我们对每种情况进行枚举，然后根据给定的条件判断哪些符合问题的要求。源程序例3、最佳游览路线。某旅游区的街道成网格状。其中东西向的街道都是旅游街，南北向的街道都是林阴道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。阿龙想到这个旅游街游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之见的街道值得游览的程度，分值是从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。如图：-50-4736-30-2317-

6、19-34-13-8-42-3-4334-45北南东西输入数据：输入文件是input.txt.文件的第一行是两个整数m和n,之间用一个空格隔开，m表示有多少条旅游街（1m100），n表示有多少条林阴道（1n20001）。接下来的m行依次给出了由北向南每条旅游街的分值信息。每行有n-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。输出数据：输出文件是output.txt。文件只有一行，是一个整数，表示你的程序找到的最佳游览线路的总分值。Input.txtOutput.txt36-5047363023171934138-4234334-4584Lij为第I条旅

7、游街上自西向东第j段的分值（1im,1jn-1）。例如样例中L12=17，L23=-34，L34=34。我们将网格状的旅游区街道以林阴道为界分为n-1个段，每一段由m条旅游街的对应成段，即第j段成为L1j，L2j，。Lmj（1jn-1）。由于浏览方向规定横向自西向东，纵向即可沿林阴道由南向北，也可由北向南，而横行的街段有分值，纵行无分值，因此最佳游览路现必须具备如下三个特证：1）来自若干个连续的段，每一个段中取一个分值；2）每一个分值是所在段中最大的；3）起点段和终点段任意，但途经段的分值和最大。设Li为第i个段中的分值最大的段。即Li=maxL1i，L2i，。，Lmi（1in-1）。例如对于

8、样例数据：L1=max（-50，17，-42）=17；L2=max（-47，-19，-3）=-3；L3=max（36，-34，-43）=36；L4=max（-30，-13，34）=34；L5=max（-23，-8，-45）=-8；我们把段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条游览路线。显然，如果确定西端为起点，东端为终点，则这条游览路线的总分值最大。问题是某些段的最大分值可能是负值，而最优游览路线的起点和终点任意，在这种情况下，上述游览路线就不是最佳了。因此，我们只能枚举这条游览路线的所有可能的子路线，从中找出一条子路线ii+1j(1ibestthenbe

9、st:=sum;end;显然，n在120001之间，时间复杂度比较高。于是，我们必须对这个算法进行优化。仍然从顶点1开始枚举最优路线。若当前子路线延伸至顶点时我们发现总分值sum0,则应放弃当前的子路线。因为无论Li+1为何值，当前子路线延伸至顶点i+1后的总分值不会大于Li+1。因此应该从顶点i+1开始重新考虑新的子路线。优化后的算法：best:=0;sum:=0;fori:=1ton-1dobeginsum:=sum+Li;Ifsumbestthenbest:=sum;ifsum0;1,n=0。programfactorial;varn:integer;t:longint;function

10、fac(n:integer):longint;beginifn=0thenfac:=1elsefac:=n*fac(n-1)end;Beginwrite(n=);readln(n);t:=fac(n);writeln(n!=,t);End.例2、斐波那契数列0，1，1，2，3，5，8，13，21，34，55，,从第三项开始，每一项是前两项的和，其递归定义式为：F（n）=0,n=0;1,n=1;F（n-1）+f（n-2）,n2。求此数列第n项。参考程序：varn:integer;functionfib(n:integer):integer;beginifn=0thenfib=0elseifn=1

11、thenfib:=1elsefib:=fib(n-2)+fib(n-1);end;beginwriteln(inputn=);readln(n);ifn3。离散事件的递归离散事件的递归例1、简单的背包问题。设有一个背包，可以防如入的重量为s。现有n件物品，重量分别为t1,t2,t3,ti,tn,ti(1in),均为正整数。从n件物品中挑选若干件，使得放入背包的重量之和正好为s.算法分析：用snap(s,n)代表这一问题。1）先取最后一个物品tn放入背包中，若tn=s,正好放入包中，问题解决，输出结果（n,tn）2)若tn1），那么问题可以转化为从剩下的n-1件物品中选取若干件，使得它们的重量和

12、等于包里剩下的可放入重量(s-tn),即snap(s-tn,n-1);而选中的tn还要看后续的问题snap(s-tn,n-1)是否有解，无解的话说明先取的tn不合适，就要放弃tn,在剩余物品中重新开始挑选，即有snap(s,n)snap(s,n-1)。3）若tns，则不能放入包中，还得继续挑选；若还剩物品（即n1），那么问题转化为从剩余n-1件物品中选取若干个，使得她们的重量和等于s，即snap(s,n)snap(s,n-1)。在2）、3）中就出现了递归定义，而1）是有解时递归结束的条件；如果无解时，只有当2）、3）中所剩的物品不够的话问题就不能继续执行，这也是递归结束的条件。回溯法回溯法回溯

13、是重要的算法之一，有一些问题，要求找到一组解，或要求找到一个满足某些限制的最优解。对于解决这样的问题，可以通过使用彻底的搜索方法来解决。然而，彻底搜索的运算量很大，有时大到计算机承受不了的程度。彻底的搜索，要进行大量的比较，大量的舍弃，以大量的运算，大量的时间为代价。因此，用穷举法解某些实际问题是不现实的，回溯算法为我们提供了一个好方法，使用回溯法可以大大减少实际的搜索。例如，迷宫问题，八皇后问题，骑士周游世界问题。算法思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就逐步往回退，换别的路线再往前试探。实际上是广度与深度搜索结合的搜索

14、，深度搜索过程中碰到条件不满足，则退回上一层，在每一层上也进行全面的搜索。关键：找到回溯的条件。求解八皇后问题：在n*n个方块排成n行n列的棋盘上，如果两个皇后位于同一行、同一列或同一对角线上，则称它们互相攻击。现在要求找出使棋盘上n个皇后互不攻击布局。列号：（8，2，4，1，7，5，3，6）分析分析：为了找出互不攻击的布局，需要对n*n个方案进行检查，将有攻击的布局剔除掉。这是一种例举法。但这种方法对于较大的n，其工作量会急剧的增大，而逐一例举是没有必要的。算法：算法：由于在第一行上的皇后在第一列，则第二行上的皇后就不可能在第一列。首先将每一行上安置一个皇后，并假设第i个皇后在第i行上，用一

15、个一维数组queen1.n用于记录安放皇后的过程中随时记录第i行上的皇后所在的列号。由此可知，在这种情况下，实际上已经剔除了两个皇后在同一行的可能性。因此，在安置每一行上的皇后时，只需考虑每两个皇后不能在同一列或同一对角线上的可能性。从第一行（即i=1）开始布局。设前i-1行上的皇后已布局好，即它们互不攻击。现考虑安排第i行上皇后位置，使之与前i-1行上的皇后也互不攻击。为了实现这一点，可以从第i行皇后的当前位置开始向右搜索。引进集合a,b,c分别表示各列、各条右对角线和各条左对角线上是否放置了皇后。在同一右对角线上，i-j是常量。在同一左对角线上，i+j是常量。第i行第j列上放皇后在第i-j

16、条右对角线和第i+j条左对角线上。能放皇后时为真，不能放皇后时为假。数组queen存放各行皇后所在的列号。骑士周游问题骑士周游问题。给定一个n*n的方阵，共有n2个区域，有一个国际象棋的马置于一个区域上，要求找到一条路径，使马按国际象棋的规则，从开始区域出发，不重复地把n2个区域都恰好经过一次。分析1：由于马按“日”字走，马从本区域起一步最多能达到八个区域。设马所在区域坐标为（i,j）,则下一步能达到的8个位置的坐标如下：(i-2,j-1)（3）(i-2,j+1)（2）(i-1,j-2)（4）(i-1,j+2)（1）（i,j）(j+1,j-2)（5）(i+1,j+2)（8）(i+2,j-1)（

17、6）(i+2,j-1)（7）分析2：马从初始位置（i,j）开始，按8个方向（从（1）（8）走，如下一位置在方阵中而且未到过，则马跳到该位置，继续走；如果8个方向的位置都不能落脚，则退一步，上一步为当前步，再按下一个方向继续试跳。算法：Procedure过程名；Begin准备初值；repeatwhile选择范围不超过边界且工作未完成dobegin分析条件；保证不满足条件不进行if成功then进栈；由第选择开始进入下一层次（往下走）else本层更换选择；横向走end;if工作未完成then退栈；原来的上一层更换为下一选择，回溯，上层横向走until全部工作完成；输出；end;随机数的介绍在自然界和

18、日常生活中,许多现象具有不确定的性质,有些问题甚至很难建立数学模型,或者很难用计算机建立递推,递归,枚举,回溯法等算法.在这种情况下,一般采用模拟策略.在对实际问题中的随机现象进行数学模拟时,利用计算机产生的随机数是必不可少的,由于用计算机产生的随机数总是受字长的限制,其随机的意义要比实际问题中真实的随机变量稍差,因此,通常将计算机产生的随机数称为伪随机数.TURBO.PASCAL的系统中有两个产生伪随机数的单元:Randomize过程伪随机数发生器初始化,Random(range)函数产生一个范围在0 xrange的伪随机数x，range和x都为word类型.模拟法模拟法模拟法:就是模拟某个

19、过程,通过改变数学的各种参数,进而观察变更这些参数所引起过程状态的变化.一般题目给定或者隐含某一概率.设计者利用随机函数和取整函数设定某一范围的随机值,将符合概率的随机值作为参数.然后根据这一模拟的数学模型展开算法.模拟策略的关键:是如何按照概率的要求确定随机值的范围.这个随机值设计得好,模拟效果就好.例一:甲乙两人抓n个棋子,谁抓最后一个谁赢.每一次只能抓一个或两个,但不能为零个.甲方为计算机,对弈方为乙(由随机数替代).设计一个程序使计算机尽可能赢.输入:棋子数n,先下手的方k(k=b对方先下;k=a,计算机先下).输出:游戏过程.一行表示一步:现有棋子数,被抓走的棋子数.最后一行为赢方的

20、名字.这个问题的算法核心是:要置对方于死地,必须使余下的棋子是1+2=3的整数倍.因此,当甲方处在棋子数是3的倍数时要小心等待.一旦对方错一步,赶紧控制余下棋子数为3的倍数.设:b乙方抓走的棋子数.每一次轮到乙方抓时,则随机产生b(1+random(2).a-甲方抓走的棋子数.轮到甲方抓时,若剩余的棋子数非3的整数倍,则应使抓掉后是3的整数倍.若剩余的棋子数为3的整数倍,则随机产生a(1+random(2).计算过程如下:输入棋子总数n和先下手一方的名字kRandomize;Whilen0dobeginifk=bthenbeginx:=random(2);b:=1+x;ifn-b=0thenb

21、egin输出现有0枚棋子,乙方抓走n枚棋子;输出乙方赢;break;endelsebeginn:=n-b;输出现有n枚棋子,乙方抓走b枚棋子;K:=aEnd;Elsebegina:=nmod3;ifa0then若剩余棋子数为3的整数倍,则调整每次抓的棋数elsex:=random(2);a:=1+x;ifn-a=2*k+1），甲每次取a颗,（N,k,a均为随机数），乙怎样取赢的可能性最大？设甲为计算机产生的随机数，乙为由你编的计算机程序。猜数游戏：人和计算机做猜数游戏。人默想一个四位数，由计算机来猜。计算机将所猜的数显示到屏幕上，并问两个问题：（1）有几个数字猜对了？（2）猜对的数字中有几个位

22、置也对？人通过键盘来回答这两个问题。计算机一次又一次地猜，直到猜对为止。比如我们默想的一个数是5122，假定计算机第一次猜1166，然后问你：（1）有几个数字猜对了？1（2）猜对的数字中有几个位置也对？1假定计算机第二次猜1287（1）有几个数字猜对了？2（2）猜对的数字中有几个位置也对？0假定计算机第三次猜5122（1）有几个数字猜对了？4（2）猜对的数字中有几个位置也对？4计算机显示最后猜中的数，并报告共猜了几次？问题问题1：编程实现这样一个猜数的游戏程序。屏幕显示格式为：第二行显示计算机所猜的四位数。第三行提问猜对的数字个数，用“Number:”第四行提问位置对的数字个数，用“Posit

23、ion:”第五行显示当前已猜的步数，用“Stepxx”.注：其中末尾数字由键盘输入。最后给出结束信息，其他由编程者自定。问题问题2：仍是这样一个游戏，但要求计算机既是猜数者，又要模拟默想这个数的人（要猜的数由键盘输入）。屏幕显示格式为：第一行显示人所默想的数，用“xxxx”.第二行至第五行同问题1，只不过末尾数字不再由键盘输入，而是计算机判断后自动显示。问题问题3：从文本文件guess.dat中读入20个四位数，一个接一个让计算机猜，统计猜中所需的总步数。算法分析：1、计算机随机产生一个猜数设m-当前的猜数集合。varm:array1.9000ofinteger;t:integer;m的长度；

24、初始时m=1000，1001，9999t=9000每一次猜数时，从m1mt中随机取出一个四位数，该数即为计算机的一个猜数。若m集合为空（t=0）时还未猜中，则游戏以失败告终。计算机产生猜数的过程如下：functionget_next:integer;beginift0thenget_next:=mrandom(t)+1elseget_next:=-1;返回失败信息End;get_next计算机产生的猜数必须与m集合中的每一个四位数比较，以确定其中哪些四位数与猜数默想一方的应答信息相符。出于逐位比较的方便，我们将猜数由整数类型转化为整数数组类型。设：n由计算机产生的猜数，即n:=get_next

25、;nown转化为整数数组now0.3.定义如下：typenowtype=array0.3of0.9varnow:nowtype;转化过程如下：procedureput(n:integer,varnow:nowtype);beginforI:=0to3dobeginnow3-i:=nmod10;n:=ndiv10;end;forend;put2、缩小猜数范围：计算机从m集合中随机产生一个猜数now后，默想方必须应答（由键盘输入或由计算机计算）：猜对多少个数字，其中有多少个数字位置也对。根据这一信息，我们将m集合中的每一个元素与now比较，由比较结果确定哪些元素应从m集合中去除。设：keym集合中

26、的某元素或默想数，其数据类型为nowtype;Now计算机产生的猜数，其数据类型亦为nowtype。我们通过test1(key,now)函数计算key中有多少数字曾在now中出现：我们通过test2(key,now)函数计算key中有多少数字曾在now中出现且位置一一对应：functiontest1(key,now:nowtype):integer;varh,i,j:integer;h为key和now中的相同数字个数mark:array0.3ofboolean;now和key间有重复数字的标志。beginfillchar(mark,sizeof(mark),false);mark初始化h:=0

27、;forI:=1to3do依次搜索key中的每一个数字beginj:=0在now中寻找与keyi相同的数字nowjwhile(j=3)and(keyinowj)or(markj)doj:=j+1;ifj=3thenbeginmarkj:=true;h:=h+1;end;thenend;fortest1:=h;End;test1Functiontest2(key,now:nowtype):integer;varh:integer;beginh:=0;forI:=0todoifkeyi=nowithenh:=h+1;Test:=h;End;test2我们通过test2(key,now)函数计算ke

28、y中有多少数字曾在now中出现且位置一一对应：当默想数为key、计算机产生的猜数为now时，我们可以通过调用上述两个函数猜出猜对的数字个数t1t1:=test1(key,now)和猜对的数字中位置也对的数字个数t2t2;=test2(key,now).若t14或者t24，则计算机将now与m集合中的每一个四位数一一比较，将m中与now的相同数字个数为t1且相同数字中位置对应的数字个数为t2的所有四位数mi(1=I=t)保留下来，即：I:=0repeatI:=I+1;put(mi,key);if(test1(key,now)t1)or(test2(key,now)t2)then从m集合中剔除mi

29、;UntilIt;形成m的一个子集，m1mt(1=t=t).显然，默想数应为该子集的一个元素。这一计算过程由子程序delete(now)完成：proceduredelete(now:nowtype);BeginI:=0;repeatI:=I+1;put(mi,key);if(test1(key,now)t1)or(test2(key,now)t2)thenbeginmi:=mt;t:=t-1;I:=I-1;end;thenUntilIt;End;delete算法流程：算法流程：问题（问题（1）的算法。）的算法。for I:=1 to 9000 do mi:=I+999;t:=9000;rand

30、omize;Repeat n:=get_next;if n=-1 then begin 打印猜数失败西信息；打印猜数失败西信息；halt;end;thenPut(n,now)打印计算机产生的猜数打印计算机产生的猜数now；输入猜对的数字个数输入猜对的数字个数t1和猜对数字中位置也对的数字个数和猜对数字中位置也对的数字个数t2;Delete(now);Until(t1=4)and (t2=4);问题问题2的算法。的算法。设step猜中一个数的不数。step:=0;m集合初始化；读默想数key；Repeatn:=get_next;put(n,now);t1:=test1(key,now);t2:=

31、test2(key,now);输出t1和t2;Step:=step+1;Delete(now);Until(t1=4)and(t2=4);问题问题3的算法：的算法：设设total猜中二十个数的总步数猜中二十个数的总步数Total:=0;For k:=0 to 19 do begin 执行问题执行问题2的算法；的算法；Total:total+step;End;for输出猜中输出猜中20个数所需的总步数个数所需的总步数total;题目1:某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某

32、天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有的导弹最少需配备多少套这种导弹拦截系统。输入输入：导弹数n和n颗导弹依次飞来的高度（1=n=1000）输出输出：要拦截所有的导弹最少配备的系统数。贪心法贪心法贪心法贪心法是从问题的某一个初始解出发,向给定的目标推进.但不同的是,推进的每一步不是依据某一固定的递推式,而是做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似的子问题,并期望通过所做的局部最优选择产生出一个全局最优解.算法分析:k当前配备的系统数.Lk被

33、第k套系统拦截的最后一枚导弹的高度,简称系统k的最低高度.(1=k导弹的的高度导弹的的高度)；Lp:=导弹的的高度。这样，可以使得被一套系统拦截的导弹数尽可能增多。4.依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数。K:=1;L1:=导弹1的高度；ForI:=2tondobeginp:=0;forj:=1tokdoif(Lj=导弹I的高度)and（p=0）or(LjLp)）thenp:=j;Ifp=0thenbegink:=k+1;Lk:=导弹I的高度；endelseLp:=导弹I的高度；End;输出应配备的最少系统数k.旅行家问题一个旅行家想驾驶汽车以最少的费用从

34、一个城市到另一个城市（假设出发时油箱是空的）。给定两城市之间的距离D1,汽车油箱的容量C（以升为单位），每升汽油能行驶的距离D2,出发时每升汽油价格为p.沿途有N个油站（1=N=100）,油站离出发点的距离为di,该油站每升汽油的价格为pi(i=1,n).计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No solution”.输入：输入：D1,C,D2,P,N以下含n行。其中第（1=imaxthenmax:=aielseifai2)个数据先分成两组，分别求最大值、最小值，然后分别将这两组的最大值和最小值进行比较，求出全部元素的最大值和最小值。若分组后元素个数还大于2，则再次分组，

35、直至组内元素小于等于2。使用这一算法，比较次数为2（n-1）。若n=10，则比较18次。源程序例2、赛程问题有n个编号为1到n的运动员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛。试为这n个运动员安排一个比赛日程，使得每个运动员每天只能进行一场比赛，且整个比赛在n-1天内结束。输入数据：运动员人数n(n0时，Ai,j表示第i名运动员在第j天的比赛对手。算法分析由于n个运动员要进行单循环比赛，且在n-1天内要结束全部比赛，经过分析，当且仅当n为2的整数次幂时，问题才有解，当然解是唯一的。这样可以将运动员分成两组：1,2,n/2和n/2+1,n/2+2,n。给第一组运动员安

36、排一个比赛日程，得到一个n/2阶的方阵A1；同时给第二组的运动员安排一个比赛日程，同样得到一个n/2阶的方阵A2。考虑到比赛的性质，设定第i个运动员在某一天的比赛对手为第k个运动员，则第k个运动员在同一天的比赛对手必然是第i个运动员，即若有Ai,j:=k,则Ak,j:=i。因此原问题的解可以由分解后的两个子问题的解合并起来。同时每一个子问题又可以按照上述二分法分解下去，直至每个组中仅有2个运动员时为止。源程序例3、设有20名学生的姓名、数学成绩，按照字典顺序存放学生姓名及其相对应的成绩于数组中，现从键盘输入一个学生的姓名，编程查找该学生是否在这20个学生中，如果在，请输出他的姓名及数学成绩，否

37、则输出“NOFOUND”解析：1、根据题意，其数据存储结构为记录型数组，有两个域：姓名域、数学成绩域。2、数组中存放的数据，按照字典顺序存放学生姓名及相应成绩。3、查找一个学生的姓名及相应成绩：可以用顺序查找，即从第一个学生姓名开始，顺次查找到所需要的学生姓名，其时间复杂度为O(n)。4、采用二分查找，其时间复杂度为O(long2n)。算法如下：首先看将要查找学生的姓名与中间位置的amid.name是否相同，若相同则查找成功，输出该学生姓名和成绩；若查找学生姓名顺序大于中间位置学生姓名，则余下查找在数据序列的后半部分查找；若查找学生姓名顺序小于中间位置学生姓名，则余下查找在数据序列的前半部分查

38、找；重复以上三步操作，直到查找到或查无此人为止。从以上的二分查找算法可以看出，他是将原问题的规模，化为子问题（对半），其子问题的算法与原问题相同，通过不断减少查找范围，快速查找所需要的数据，因此，这是一个高效算法。例4、AB两地的距离为S公里，甲、乙、丙三人从A地到B地共同完成任务。从A地出发时，A地有X、Y两种出租车可供利用，已知三人步性速度都为V1，出租车Y速度为V2，并仅能载一人，出租车X的速度为V3，能载两人。问题是从A出发时X只能载一人，回头接人时才能载两人，试问怎样安排行程，才能使甲、乙、丙三人尽快同时到达B地后共同完成任务（已知V1V2ythen选择x且取得最大和为13+xels

39、e选择y且取得最大和为13+y这样，原先求根结点到底端的最大路径问题，变为从11出发和和从8出发求路径和的子问题。同理，求从11出发到底端的最大路径问题可以转化为从12出发和从7出发的最大路径问题。决策：路径和最大状态转移方程：Fi=max(Fi-1(左),Fi-1(右)A、当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。终止条件B、自底向上计算从底层开始，本身数即为最大数；倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32最后的路径为：13-8-26-8-244）数据结

40、构及算法设计：A、图形转化：直角三角形，便于搜索，向下或向右B、用三维数组表示数塔：ax,y,1表示行、列及结点本身数据ax,y,2表示能够取得最大值ax,y,3表示前进方向，0向下，1向右。C、算法：数组初始化，输入每个结点值以及初始的最大路径、前进方向0；从倒数第二层开始向上一层求最大路径，共循环n-1次；从顶向下，输出路径：关键是j的值，由于行逐渐递增，表示向下，究竟是向下还是向右取决于列的值。若j的值比原先多1则向右，否则向下。源程序分析例2、求一组数列的最长不下降序列。问 题 描 述：设 有 一 个 正 整 数 序 列 b1,b2,b3,bn,若 下 标 为i1i2i3,15，不符合

41、问题要求，不作任何链接，长度仍为1。2、从倒数第三项开始在其后有2项，因此需要做两次比较，得到目前最长的不下降序列长度为2，其链接情况如下表：.11121314.226315.211.1300.11121314.21226315.3211.1213003、一般处理过程：在i+1,i+2,.,n项中，找出比bi,1大的最长长度m，以及位置K；若m0，则bi,2:=L+1;bi,3:=k;本题通过计算，最终结果为：123456789101112131413791638243718441921226315787634352432114348979101311121300源程序分析题例、某国为了防御敌

42、国的导弹袭击，发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算一套导弹拦截系统最多能够拦截多少枚导弹。例3、一个n行m列迷宫（1n,m50）,入口位于左上角，规定只能往下或往右走。迷宫中存在一些障碍物无法通过。迷宫的某些地方里藏有不同价值的宝藏。求所能收集的宝藏的最大价值。子结构划分：逐行扫描。考虑迷宫某一点，要求走到这一点所能收集的宝藏的最大价值，

43、先求出走到它在边和上边所能收集的宝藏的最大价值。算法分析：变量的定义：Ai,j=迷宫第i行第j列的宝藏价值，-1表示障碍物；Fi,j=走到第i行第j列所能收集大宝藏的最大价值。状态转移方程：Fi,j=maxFi,j-1|j1,Fi-1,j|i1+Ai,j边界条件：F1,1=A1，1answer=Fn,m源程序在一个操场上摆放着一行共n堆石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分，请编程计算出将n堆石子合并成一堆的最小得分。采药采药【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医

44、师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【数据规模】对于30%的数据，M=10；对于全部的数据，M=100。