计算机常用算法

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

2、模不是特别大；2）对于每个解变量A1，A2，。An的可能值必须为 一个连续的值域。4 枚举法的算法流程：设ai1为解变量Ai的最小值；aik为解变量的最大值；其中1 i n. A1 a11,a12,a1K A2 a21,A22,A2K Ai ai1,Ai2,AiK An an1,An2,AnK我们称解变量为枚举变量。例如某问题的枚举变量有三个： A1， A2， A3。5A11，2， A22，3，4， A3 5，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）， （

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

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

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

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

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

8、，但途经段的分值和最大。设Li为第i个段中的分值最大的段。即Li=maxL1i，L2i，。，Lmi（1in-1 ）。例如对于样例数据：12L1=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；我们把段设为顶点，所在段的最大分值设为顶点的权，各顶点按自西向东的顺序相连，组成一条游览路线。显然，如果确定西端为起点，东端为终点，则这条游览路线的总分值最大。问题是某些段的最大分值可能是负值，而最优游览路线的起点和终点任意，在这种情况下，上

9、述游览路线就不是最佳了。因此，我们只能枚举这条游览路线的所有可能的子路线，从中找出一条子路线ii+1j(1 ibest then best:=sum; end;显然，n在120001之间，时间复杂度比较高。于是，我们必须对这个算法进行优化。仍然从顶点1开始枚举最优路线。若当前子路线延伸至顶点时我们发现总分值sum 0,则应放弃当前的子路线。因为无论Li+1为何值，当前子路线延伸至顶点i+1后的总分值不会大于Li+1 。因此应该从顶点i+1开始重新考虑新的子路线。14优化后的算法：best:=0;sum:=0;for i:=1 to n-1 do begin sum:=sum+Li; If su

10、mbest then best:=sum; if sum0;1, n=0。17program factorial; var n:integer; t:longint; function fac(n:integer):longint; begin if n=0 then fac:=1 else fac:=n*fac(n-1) end;Begin write(n=);readln(n); t:=fac(n); writeln(n!=,t);End.18例2、斐波那契数列0，1，1，2，3，5，8，13，21，34，55，,从第三项开始，每一项是前两项的和，其递归定义式为：F（n）=0, n=0;1

11、, n=1;F（n-1）+f（n-2）, n 2。求此数列第n项。19参考程序：var n:integer; function fib(n:integer):integer; begin if n=0 then fib=0 else if n=1 then fib:=1 else fib:=fib(n-2)+fib(n-1); end; begin writeln(input n=); readln(n); if n3。21离散事件的递归离散事件的递归例1、简单的背包问题。设有一个背包，可以防如入的重量为s。现有n件物品，重量分别为t1,t2,t3,ti,tn,ti(1 i n),均为正整数。

12、从n件物品中挑选若干件，使得放入背包的重量之和正好为s.22 算法分析：用snap(s,n)代表这一问题。1）先取最后一个物品tn放入背包中，若tn =s,正好放入包中，问题解决，输出结果（n,tn）2)若tn 1），那么问题可以转化为从剩下的n-1件物品中选取若干件，使得它们的重量和等于包里剩下的可放入重量(s- tn) ,即snap(s- tn,n-1);而选中的tn还要看后续的问题snap(s-tn,n-1)是否有解，无解的话说明先取的tn不合适，就要放弃tn,在剩余物品中重新开始挑选，即有snap(s,n) snap(s,n-1)。3）若tns，则不能放入包中，还得继续挑选；若还剩物品

13、（即n1），那么问题转化为从剩余n-1件物品中选取若干个，使得她们的重量和等于s，即snap(s,n) snap(s,n-1)。在2）、3）中就出现了递归定义，而1）是有解时递归结束的条件；如果无解时，只有当2）、3）中所剩的物品不够的话问题就不能继续执行，这也是递归结束的条件。23回溯法回溯法 回溯是重要的算法之一，有一些问题，要求找到一组解，或要求找到一个满足某些限制的最优解。对于解决这样的问题，可以通过使用彻底的搜索方法来解决。然而，彻底搜索的运算量很大，有时大到计算机承受不了的程度。彻底的搜索，要进行大量的比较，大量的舍弃，以大量的运算，大量的时间为代价。因此，用穷举法解某些实际问题是

14、不现实的，回溯算法为我们提供了一个好方法，使用回溯法可以大大减少实际的搜索。例如，迷宫问题，八皇后问题，骑士周游世界问题。算法思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就逐步往回退，换别的路线再往前试探。实际上是广度与深度搜索结合的搜索，深度搜索过程中碰到条件不满足，则退回上一层，在每一层上也进行全面的搜索。关键：找到回溯的条件。24求解八皇后问题：在n*n个方块排成n行n列的棋盘上，如果两个皇后位于同一行、同一列或同一对角线上，则称它们互相攻击。现在要求找出使棋盘上n个皇后互不攻击布局。列号：（8，2，4，1，7，5，3，6）

15、25分析分析：为了找出互不攻击的布局，需要对n*n个方案进行检查，将有攻击的布局剔除掉。这是一种例举法。但这种方法对于较大的n，其工作量会急剧的增大，而逐一例举是没有必要的。26算法：算法：由于在第一行上的皇后在第一列，则第二行上的皇后就不可能在第一列。首先将每一行上安置一个皇后，并假设第i个皇后在第i行上，用一个一维数组queen1.n用于记录安放皇后的过程中随时记录第i行上的皇后所在的列号。由此可知，在这种情况下，实际上已经剔除了两个皇后在同一行的可能性。因此，在安置每一行上的皇后时，只需考虑每两个皇后不能在同一列或同一对角线上的可能性。 从第一行（即i=1）开始布局。 设前i-1行上的皇

16、后已布局好，即它们互不攻击。现考虑安排第i行上皇后位置，使之与前i-1行上的皇后也互不攻击。为了实现这一点，可以从第i行皇后的当前位置开始向右搜索。 引进集合a,b,c分别表示各列、各条右对角线和各条左对角线上是否放置了皇后。在同一右对角线上，i-j是常量。在同一左对角线上，i+j是常量。第i行第j列上放皇后在第i-j条右对角线和第i+j条左对角线上。能放皇后时为真，不能放皇后时为假。数组queen存放各行皇后所在的列号。27骑士周游问题 骑士周游问题。给定一个n*n的方阵，共有n2个区域，有一个国际象棋的马置于一个区域上，要求找到一条路径，使马按国际象棋的规则，从开始区域出发，不重复地把n2

17、个区域都恰好经过一次。分析1：由于马按“日”字走，马从本区域起一步最多能达到八个区域。设马所在区域坐标为（i,j）,则下一步能达到的8个位置的坐标如下：28分析2： 马从初始位置（i,j）开始，按8个方向（从（1）（8）走，如下一位置在方阵中而且未到过，则马跳到该位置，继续走；如果8个方向的位置都不能落脚，则退一步，上一步为当前步，再按下一个方向继续试跳。29算法：Procedure 过程名；Begin 准备初值； repeat while 选择范围不超过边界且工作未完成 do begin 分析条件；保证不满足条件不进行 if 成功 then 进栈；由第选择开始进入下一层次（往下走） else

18、 本层更换选择；横向走 end ; if 工作未完成 then 退栈；原来的上一层更换为下一选择，回溯，上层横向走 until 全部工作完成； 输出； end ;30 随机数的介绍 在自然界和日常生活中,许多现象具有不确定的性质,有些问题甚至很难建立数学模型,或者很难用计算机建立递推,递归,枚举,回溯法等算法.在这种情况下,一般采用模拟策略.在对实际问题中的随机现象进行数学模拟时,利用计算机产生的随机数是必不可少的,由于用计算机产生的随机数总是受字长的限制,其随机的意义要比实际问题中真实的随机变量稍差,因此,通常将计算机产生的随机数称为伪随机数.TURBO.PASCAL的系统中有两个产生伪随机

19、数的单元:Randomize过程伪随机数发生器初始化,Random(range)函数产生一个范围在0 xrange的伪随机数x，range和x都为word类型.模拟法模拟法31模拟法: 就是模拟某个过程,通过改变数学的各种参数,进而观察变更这些参数所引起过程状态的变化.一般题目给定或者隐含某一概率.设计者利用随机函数和取整函数设定某一范围的随机值,将符合概率的随机值作为参数.然后根据这一模拟的数学模型展开算法.模拟策略的关键: 是如何按照概率的要求确定随机值的范围.这个随机值设计得好,模拟效果就好.32例一: 甲乙两人抓n个棋子,谁抓最后一个谁赢.每一次只能抓一个或两个,但不能为零个.甲方为计

20、算机,对弈方为乙(由随机数替代).设计一个程序使计算机尽可能赢. 输入:棋子数n,先下手的方k(k=b对方先下;k=a,计算机先下). 输出:游戏过程.一行表示一步:现有棋子数,被抓走的棋子数.最后一行为赢方的名字. 这个问题的算法核心是:要置对方于死地,必须使余下的棋子是1+2=3的整数倍.因此,当甲方处在棋子数是3的倍数时要小心等待.一旦对方错一步,赶紧控制余下棋子数为3 的倍数.设: b乙方抓走的棋子数.每一次轮到乙方抓时,则随机产生b(1+random(2). a- 甲方抓走的棋子数.轮到甲方抓时,若剩余的棋子数非3的整数倍,则应使抓掉后是3的整数倍.若剩余的棋子数为3的整数倍,则随机

21、产生a(1+random(2).33 计算过程如下:输入棋子总数n和先下手一方的名字kRandomize;While n0 do begin if k=b then begin x:=random(2);b:=1+x; if n-b=0 then begin 输出现有0枚棋子,乙方抓走n枚棋子; 输出乙方赢; break; end else begin n:=n-b; 输出现有n枚棋子,乙方抓走b枚棋子; K:=aEnd;Else begin a:=n mod 3; if a0 then 若剩余棋子数为3的整数倍,则调整每次抓的棋数 else x:=random(2);a:=1+x; if n

22、-a=2*k+1），甲每次取a颗, （N,k,a均为随机数），乙怎样取赢的可能性最大？设甲为计算机产生的随机数，乙为由你编的计算机程序。36猜数游戏： 人和计算机做猜数游戏。人默想一个四位数，由计算机来猜。计算机将所猜的数显示到屏幕上，并问两个问题：（1）有几个数字猜对了？（2）猜对的数字中有几个位置也对？ 人通过键盘来回答这两个问题。计算机一次又一次地猜，直到猜对为止。比如我们默想的一个数是5122，假定计算机第一次猜1166，然后问你：（1）有几个数字猜对了？1（2）猜对的数字中有几个位置也对？1假定计算机第二次猜1287（1）有几个数字猜对了？2（2）猜对的数字中有几个位置也对？0假定计

23、算机第三次猜5122（1）有几个数字猜对了？4（2）猜对的数字中有几个位置也对？4计算机显示最后猜中的数，并报告共猜了几次？37问题问题1：编程实现这样一个猜数的游戏程序。屏幕显示格式为：第二行显示计算机所猜的四位数。第三行提问猜对的数字个数，用“Number:”第四行提问位置对的数字个数，用“Position:”第五行显示当前已猜的步数，用“Step xx”.注：其中末尾数字由键盘输入。最后给出结束信息，其他由编程者自定。问题问题2 ：仍是这样一个游戏，但要求计算机既是猜数者，又要模拟默想这个数的人（要猜的数由键盘输入）。屏幕显示格式为：第一行显示人所默想的数，用“xxxx”.第二行至第五行

24、同问题1，只不过末尾数字不再由键盘输入，而是计算机判断后自动显示。38问题问题3： 从文本文件guess.dat中读入20个四位数，一个接一个让计算机猜，统计猜中所需的总步数。39算法分析：1、计算机随机产生一个猜数设m-当前的猜数集合。 var m:array1.9000 of integer; t:integer; m的长度；初始时m=1000，1001，9999 t=9000每一次猜数时，从m1mt中随机取出一个四位数，该数即为计算机的一个猜数。若m集合为空（t=0）时还未猜中，则游戏以失败告终。计算机产生猜数的过程如下：function get_next :integer; begin

25、 if t0 then get_next:=mrandom(t)+1 else get_next:=-1;返回失败信息End;get_next40计算机产生的猜数必须与m集合中的每一个四位数比较，以确定其中哪些四位数与猜数默想一方的应答信息相符。出于逐位比较的方便，我们将猜数由整数类型转化为整数数组类型。设：n由计算机产生的猜数，即n:=get_next;nown转化为整数数组now0.3.定义如下：type nowtype=array0.3 of 0.9var now:nowtype; 转化过程如下：procedure put (n:integer,var now:nowtype); beg

26、in for I:=0 to 3 do begin now3-i:=n mod 10;n:=n div 10;end;forend;put412、缩小猜数范围：计算机从m集合中随机产生一个猜数now后，默想方必须应答（由键盘输入或由计算机计算）：猜对多少个数字，其中有多少个数字位置也对。根据这一信息，我们将m集合中的每一个元素与now 比较，由比较结果确定哪些元素应从m集合中去除。设： keym集合中的某元素或默想数，其数据类型为nowtype;Now计算机产生的猜数，其数据类型亦为nowtype 。我们通过test1(key,now)函数计算key中有多少数字曾在now中出现：我们通过tes

27、t2(key,now)函数计算key中有多少数字曾在now中出现且位置一一对应：42function test1(key,now:nowtype):integer; var h,i,j:integer;h为key和now中的相同数字个数 mark:array0.3 of boolean;now和key间有重复数字的标志。 begin fillchar(mark,sizeof(mark),false);mark初始化 h:=0; for I:=1 to 3 do 依次搜索key中的每一个数字 begin j:=0 在now中寻找与keyi相同的数字nowj while (j=3) and (ke

28、yinowj) or (markj) do j:=j+1; if j=3 then begin markj:=true;h:=h+1; end;then end;for test1:=h; End;test143Function test2(key,now:nowtype):integer; var h:integer; begin h:=0; for I:=0 to do if keyi=nowi then h:=h+1;Test:=h;End;test2我们通过test2(key,now)函数计算key中有多少数字曾在now中出现且位置一一对应：44 当默想数为key、计算机产生的猜数为n

29、ow时，我们可以通过调用上述两个函数猜出猜对的数字个数t1t1:=test1(key,now)和猜对的数字中位置也对的数字个数t2t2;=test2(key,now).若t14或者t24，则计算机将now与m集合中的每一个四位数一一比较，将m中与now的相同数字个数为t1且相同数字中位置对应的数字个数为t2的所有四位数mi(1=I=t)保留下来，即：I:=0 repeat I:=I+1; put(mi,key); if (test1(key,now)t1) or (test2(key,now)t2) then 从m集合中剔除mi;Until It;45形成m的一个子集，m1mt(1=t=t).

30、显然，默想数应为该子集的一个元素。这一计算过程由子程序delete(now)完成： procedure delete(now:nowtype);Begin I:=0; repeat I:=I+1; put(mi,key); if (test1(key,now)t1) or (test2(key,now)t2) then begin mi:=mt;t:=t-1; I:=I-1; end;thenUntil It;End;delete 46算法流程：算法流程：问题（问题（1）的算法。）的算法。 for I:=1 to 9000 do mi:=I+999; t:=9000; randomize;Re

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

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

33、一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有的 导弹最少需配备多少套这种导弹拦截系统。输入输入： 导弹数n和n颗导弹依次飞来的高度（1=n=1000）输出输出：要拦截所有的导弹最少配备的系统数。贪心法贪心法50 贪心法贪心法是从问题的某一个初始解出发,向给定的目标推进.但不同的是 ,推进的每一步不是依据某一固定的递推式,而是做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似的子问题,并期望通过所做的局部最优选择产生出一个全局最优解.算法分析: k当前配备的系统数. Lk被第k套系统拦截的最后一枚导弹的高度,简称系统k的最低高度.(1=k导弹的的高度导弹的的高度)；Lp:=导弹的的高度。这样，可以使得被一套系统拦截的导弹数尽可能增多。4.依次类推，直至分析了n枚导弹的高度为止。 此时得出的k便为应配备的最少系统数。52K:=1;L1:=导弹1的高度；For I:=2 to n do begin p:=0;for j:=