suanfa.rar_贪婪

常用算法 一. 基本概念： 1. 算法：就是解决问题方法的精确描述。并不是所有问题都有算法，有些问题经研究可行，则相应有算法；而有些问题不能说明可行，则表示没有相应算法。 算法具有以下性质：是一有穷动作的序列； 动作序列仅有一个初始动作； 序列中每个动作的后继动作是确定的； 序列的终止表示问题得到解答或问题没有解答 2. 算法的分类：数值的和非数值的 数值的算法是以数学方式表示的问题求数值解的方法，如：代数方程计算、矩阵计算、线性方程组求解、函数方程求解等； 非数值的算法是求非数值解的方法，如排序查找、模式匹配、排列模拟、表格处理、文字处理等。 3. 算法设计：主要是针对各类具体问题设计良好的算法及研究设计算法的规律和方法。 4. 常用的算法设计方法： 数值算法：迭代法、递归法、插值法等； 非数值算法：分治法、贪婪法、回溯法等。 5. 算法分析：是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度。算法的复杂度分时间复杂度和空间复杂度。 二. 常用数值计算算法 1. 迭代法 迭代法适用于方程(或方程组)求解，是使用间接方法求方程近似根的一种常用算法。(参见清华版《PASCAL程序设计P89练习4.23》 设方程f(x)=0，该方法将方程表示为等价形式：x=g(x)，或一般地将f(x)拆成两个函数f1、f2，即f(x)= f1(x)-f2(x) =0，因而有f1(x)=f2(x)。其中f1(x)是这样一个函数，对于任意数c，容易求出f1(x)=c的精确度很高的实根。迭代法求解算法如下： (1). 首先选一个x的近似根x0，从x0出发，代入右面函数，并解方程f1(x)=f2(x0)得到下一个近似根x1; (2). 将上次近似根x1代入右面函数，并解方程f1(x)=f2(x1)，得到又一个近似根x2 (3). 重复(2)的计算，得到一系列近似根x0,x1,x2,…,xi,xi+1,…,xn,…； 若方程有根，这数列收敛于方程的根，若满足 ，则认为xn是方程的近似根。 例1：迭代计算n!、Fibonacci(斐波那契)数列 (详见清华版《PASCAL程序设计》P59-62例4.3,4.4) 例2：计算 直到最后一项的绝对值小于10-7时停止计算，x由键盘输入。(详见清华版《PASCAL程序设计》P72例4.11) 练习：清华版《PASCAL程序设计习题与选解》P18习题4.23,4.38 2. 递推法 递推法实际上是需要抽象为一种递推关系求解，此方法通常表现为两种方式：方式一是从简单推到一般； 方式二是将一个复杂问题逐步推到一个已知解的简单问题。这两种方式反映了两种不同的递推方向，前者往往用于计算级数，后者与“回归”配合成为一种特殊的算法――递归法。 3. 递归法 在数学中几个熟知的递归定义： (1). (2). 树结构：a)O是树(空树)；b)若t1和t2是树，则是树。 例3：递归计算n!；(详见清华版《PASCAL程序设计》P108例5.8) 例4：第二届初中组一、6 第二届初中组一、7 提示：利用y=((((ANX+AN-1)X+AN-2)X+AN-3)+……+A1)X+A0 第七届初中组三、1 练习：计算Fibonacci(斐波那契)数列 4. 插值法 也称为内插法。在实际问题中出现的函数f(x)，往往只知道它在某区间中若干点的函数值，这时作出适当的特定函数，使得在这些点上取已知值，并且在这区间内其它各点上就用这特定函数所取的值作为函数f(x)的近似值，这方法称为“插值法”。如果这特定函数是多项式，就称之为“插值多项式”或“内插多项式”。(常见用于高等代数中的计算) 三. 常用非数值计算算法 1. 穷举搜索法 穷举所有可能情形，并从中找出符合要求的解。最直观的是联系循环的算法。 例5：百钱买百鸡问题；第一届初中组3(也可用累加法) 第七届初中组四、2 输出1-100内的素数；验证哥德巴赫猜想 (详见清华版《PASCAL程序设计》P82-86例4.16,4.17) 例6：找出n个自然数(1,2,3,……,n)中r个数的组合 当n=5,r=3时，约定前一个数应大于后一个数， 有：543 542 541 532 531 521 432 431 421 321 可简单地用三重循环进行搜索，算法如下： for i:=5 downto 1 do for j:=5 downto 1 do for k:=5 downto 1 do if ((i<>j) and (i<>k) and (j<>k) and (i>j) and (j>k)) then writeln(i,j,k); 或者 for i:=5 downto 3 do for j:=i-1 downto 3-1 do for k:=j-1 downto 1 do if ((i<>j) and (i<>k) and (j<>k) and (i>j) and (j>k)) then writeln(i,j,k); 2. 递归法 例如：在例6中，可首先固定第一位数(如5)，其后是在另4个数中再“组合”2个数。这就将“5个数中3个数的组合”推到了“4个数中2个数的组合”上去了。第一位数可以是n→r(如5→3)，n个数中r个数组合递推为n-1个数中r-1个数的组合，这是一个递归的算法： procedure comb(n,r:integer); var i,temp:integer; begin for i:=n downto r do if ((i<>n) and (k<>r) then begin temp:=1 while temp<=(k-r)*3 do {k为过程外定义的} begin write(‘ ‘); temp:=temp+1 end; end; write(i); if (I>1) then comb(i-1,r-1) {递推到下一情形} else writeln; end; 例7：求m与n的最大公约数；汉诺塔游戏(Tower of Hanoi) (详见清华版《PASCAL程序设计》P109-P112例5.9,5.10) 例8：第六届初中组二、2 第五届高中组二、第五届初中组五 3. 回溯法 一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足条件的某个状态的点称为“回溯点”。 例如：在例6中将自然数排列在数组A中： A[1] A[2] A[3] 5 4 3 5 4 2 …… 3 2 1 排数时从A[1]→A[2]→A[3]，后一个至少比前一个数小1，并且应满足ri+A[ri]>r这个关系。若ri+A[ri]≤r就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为1，也应作一次回溯(若不回，便由上述回溯条件处理)。算法如下： procedure comb2(n,r,a[m]:integer); var j,ri:integer; begin ri=1;a[1]=n; repeat if (ri<>r) {没有搜索到底} then if (ri+a[ri]>r) {是否回溯} then begin a[ri+1]:=a[ri]+1;ri:=ri+1 end; else begin ri:=ri-1; a[ri]:=a[ri]-1 {回溯} end; else begin for j:=1 to r do write(a[j]); writeln; if (a[r]=1) {是否回溯} then begin ri:=ri-1; a[ri]:=a[ri]-1 {回溯} end; else a[ri]:=a[ri]-1 end; until (a[1]<>r-1) end; 例9：八皇后问题(详见清华版《PASCAL程序设计》P165) 练习：清华版《PASCAL程序设计》P172习题7.19跳马问题和7.20迷宫问题、四色问题 例10：第三届初中组二、3 4. 贪婪法 一种可以快速得到满意解(但不一定是最优解)的方法。方法的“贪婪”性反映在对当前情况，总是作最大限度的选择。即满足条件的均选入，然后分别展开，最后选得一个问题解。这方法不考虑回溯，也不考虑某次选择并不符合最优条件，但最终能得到最优结果的选择。 例11：用贪婪法求解“货郎担问题”。所谓货郎担问题是指，给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和为最小，如右图所示。如a,b,c,d,e,f这6个点，坐标分别为(0,0)、(4,3)、(1,7)、(15,7)、(15,4)、(18,0)，这是最优解。(算法程序略) 求解步骤一般如下： (1). 计算各点间距离（邻接矩阵）； (2). 距离关系表排序； (3). 贪婪法选择边，入选的边应符合如下两条件：每个端点不能联系两条以上的边；不会使入选的边形成回路，除非入选正好是边数等于端点数。为此引入端点关系表 (4). 如果由(3)得不到解，应调整距离关系表中距离相同的边的次序，再试； (5). 若有解，则按端点关系表给出回路的轨迹。 例12：旅行路线选择。设有n个城市(或景点)，今从某市出发遍历各城市，使之旅费最少(即找出一条旅费最少的路径)。 例13：背包问题。从n件不同价值、不同重量的物品中选取一部分，在不超过规定重量的原则下，使该部分价值最大。 例14：第三届初中组一、8； 第七届高中组四、2 5. 分治法 是应用十分广泛的一种算法设计方法，其基本思想是把一个规模为n的问题分成若干个规模较小的问题，使得从这些较小问题的解易于构造出整个问题的解。 例15：找一个集合的极大元和极小元。集合S含有n个元素，其中n=2k(k≥1)。算法思路如下： procedure MAXIM(S); begin 1. if ||S||=2 {集合S的元素个数为2} then begin 2. 设 S={a,b}; 3. return (MAX(a,b),MIN(a,b)) end else begin 4. 把S分为两个子集S1和S2，各有一半元素； 5. (max1,min1)←MAXMIN(S1)； 6. (max2,min2)←MAXMIN(S2)； 7. return (MAX(max1,max2),MIN(min1,min2)) end end; 注意到，需要在集合S的元素间进行比较的步骤只是步骤3(在此比较两个元素)及步骤7(在此把max1与max2及min1与min2进行比较)，设T(n)是用MAXMIN在一个具有n个元素的集合中找极大元和极小元时，需要在S的元素间进行比较的次数。显然，T(2)=1，如果n>2，则T(n)是在大小为n/2的集合上两次调用MAXMIN(第5、6步所需的比较次数加上第7步的两次比较所得的总次数，即 。经递推T(n)=3n/2-2，对于在集合S的元素间进行比较的次数来说，这种算法是最优的。 例16：设有n个选手的循环比赛(n=2m)，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天，要求每天没有选手轮空。例如m=3，见下表，用分治法将(2m*2m)矩阵分成四块，每块是(2m-1*2m-1)的矩阵，它应是对称的( )，再对A与B均是(2m-1*2m-1)的矩阵分成四块，直至(2*2)的矩阵定出每个元素的值，再按对称关系构造出比赛表。算法程序略。 选手 对手 第一天 第二天 第三天 第四天 第五天 第六天 第七天 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 四. 排序 1. 插入