第四次(贪心).ppt

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第一章 算法概述,第二章 递归与分治策略,第三章 动态规划,第四章 贪心算法,第五章 回朔法,第六章 分支限界法,第七章 概率算法,第八章,NP,完全性理论简介,算法设计与分析,目录,1,4.1,最优化问题简介,4.2,贪心算法思路,4.3,任务安排问题,4.4,装载问题,4.5,背包问题,4.6,哈夫曼编码,4.7,最短路径,4.8,最小生成树,算法设计与分析,目录,4.9,多机调度问题,2,第四章,.,贪心算法,(,Greed method,),用以求解,最优化问题,算法设计与分析,贪心算法,3,4-1,.,贪心算法,基本思想,将问题的求解过程看作一系列选择（每次选择确定一个输入值）,每次选择都是当前状态下的最好选择,(,局部最优解,).,每作一次选择后,所求问题会简化为一个规模更小的子问题,.,从而通过每一步的最优解逐步达到整体最优解,算法设计方法,贪心算法,贪心算法的一般模式,procedure greedy(A,n),solusion,for i,1 to n do,x,selese(A,),if,feasible(solusion,x,),solusion,union(solusion,x,),repeat,return(solusion,),/,从,A,中选择一个当前最好输入,/,判断,X,是否包含在当前解中,.,/,将,X,与解合并,修改目标函数,算法设计与分析,贪心算法,4,适用问题,具备,贪心选择,和,最优子结构,性质的最优化问题,算法优点,求解速度快,时间复杂性有较低的阶,.,整体的最优解可通过一系列局部最优解达到,.,每次的选择可以依赖以前作出的选择,但不能依赖于后面的选择,.,问题的整体最优解中,包含着它的子问题的,最优解,.,算法缺点,需证明是最优解,.,常见应用,背包问题,最小生成树,最短路径,作业调度等等,算法设计方法,贪心算法,算法设计与分析,贪心算法,5,例,1,最小代价通讯网络,:,在,N,个城市之间架设通讯线路,要求造价最低,.,问题描述,输入,:,任一连通图,G(G,的邻接矩阵,),可行解,:,图,G,的生成树,优化函数,:,生成树的权,最优解,:,使优化函数达到最小值的生成树,.,问题可描述为有,n,个输入,(x1,x2,.,xn,),一组约束条件和一个优化,(,目标,),函数。满足约束条件的输入称为,可行解,使优化函数取得极值的可行解称为,最优解,.,算法设计与分析,贪心算法,4.2,最优化问题 简介,(optimization problem),城市间的通讯连接视作一个无向图,G,G,中每边的权值表示建成这段线路的代价,.,问题转化为求一棵最小生成树,.,6,e1(1),e2(6),e8(9),e6(2),e9(4),e5(5),e4(7),e10(8),e11(3),e7(10),e3(11),1),以,G,中全部点为点作图,2),将各边按权值递增排序,3),依次添加各边,若出现回路,则忽略此边,.,4),加入,n-1,条边后就得到最小,生成树,.,1,2,5,3,7,图论,树与生成树,求最小生成树,(,Kruscal,),最优解,:(,e1,e6,e11,e5,e4,),7,算法思路,1.,将活动按结束时间排序,得到活动集,E=e,1,e,2,e,n,；,2.,先将,e,1,选入结果集合,A,中，即,A=e,1,；,3.,依次扫描每一个活动,e,i,:,如果,e,i,的,s,i,最后,一个选入,A,的活动,e,j,的,f,j,则将,e,i,选入,A,中,否则放弃,e,i,4.3.,活动安排问题,问题陈述,有,n,个活动,E=1,2,n,要使用同一资源,同一时间只允许一个活动使用该资源,.,设活动,i,的起止时间区间,s,i,f,i,),如果选择活动,i,则它在时间区间,s,i,f,i,),内占用该资源,;,若区间,s,i,f,i,),与,s,J,f,J,),不相交,则称活动,i,与,j,是,相容的,.,要求在所给的活动集合中选出最大相容活动子集,.,算法设计与分析,贪心算法,8,算法设计与分析,贪心算法,1 2 3 4 5 6 7 8 9 10 11,例,1 3 0 5 3 5 6 8 8 2 12,4 5 6 7 8 9 10 11 12 13 14,i,si,fi,设待排的,11,个活动起止时间按结束时间的非减序排列,最大相容活动子集,(1,4,8,11),也可表示为等长,n,元数组,:(1,0,0,1,0,0,0,1,0,0,1),9,算法操作过程,算法设计与分析,贪心算法,10,活动安排问题贪心算法,Template,void,GreedySelector,(,int,n,T s,T f,bool,A ),A1=true;,int,j=1;,/,从第二个活动开始检查是否与前一个相容,for(,int,i=2;i=f j),Ai=true;,j=i;,else A i=false;,T(n)=,O(nlogn,)(,未排序时,),算法分析,T(n)=O(n)(,排序时,),各活动的起始时间和结束时间存储于数组,s,和,f,中且按结束时间的非减序排列,算法设计与分析,贪心算法,11,装载问题,:,一艘大船装载货物。所有待装货物都装在,n,个大小一样的集装箱中,集装箱的重量各不相同。设第,i,个集装箱的重量为,w,i,(1,i,n).,船的最大,载重量为,c,求装载方案使装船的箱子数最多,.,问题描述,输入,:(x,1,x,2,x,n,),xi=0:,货箱,i,不装船,;xi=1,货箱,i,装船,可行解,:,满足约束条件 ,c,的输入,优化函数,:,最优解,:,max,4.4,最优装载,12,问题描述,输入,:(x1,x2,.xn),xi=0,货箱,i,不装船,;xi=1,货箱,i,装船,.,可行解,:,满足约束条件,c,的输入,优化函数,:,最优解,:,使优化函数达到最大值的可行解,.,算法设计与分析,贪心算法,设,n=8,，,w1,，,w8=100,200,50,90,150,50,20,80,，,c=400,。,所考察货箱次序为,:7,3,6,8,4,1,5,2,。,货箱,7,3,6,8,4,1,的总重量为,390,个单位且已被装载,剩下的装载能力为,10,小于任意货箱,.,所以得到解,:,x1,.x8=1,0,1,1,0,1,1,1,算法思路,将装船过程化为多步选择，每步装一个货箱每次从剩下的货箱中选择重量最轻的货箱,.,如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱,13,最优装载的贪心算法,template,void,Loading(int,x,T w,T c,int,n),int,*t=new,int,n+1;,/w,的游标,Sort(w,t,n);,/,按货箱重量递增排序,/,for(,int,i=1;i =n;i+),xi=0;,for(,int,i=1;i,算法设计方法,贪心算法,X:,解向量,w:,货箱重量,c:,船的载重量,n:,货箱数量,算法设计与分析,贪心算法,14,最优化描述,输入,:,n,元,向量,(,x,1,x,n,),0,xi,1,约束条件,:.,4-5,背包问题,(,Knapsack Problem,),问题描述,设有,n,个物体和一个背包,物体,i,的重量为,w,i,价值为,v,i,背包的承载的重量为,C.,若将物体,i,的,x,i,部分,(1,i,n,0,x,i,1),装入背包,则具有价值为,v,i,x,i,.,求解目标是找到一个方案,使放入背包的物体总价值最高,.,算法设计与分析,贪心算法,其中,C,W,i,v,i,0,1,i,n,目标函数,:,15,例,n=3,c=20,(,v,1,v,2,v,3)=(25,24,15),(w1,w2,w3)=(18,15,10),x1,x2,x3,0,2/3,1,0,1,1/2,.,1,2/15,0,20,20,20,28.2,31,31.5,.,.,算法设计与分析,贪心算法,算法思路,1).,将各物体按单位价值由高到低排序,.,2).,取价值最高者放入背包,.,3).,计算背包剩余空间,.,4).,在剩余物体中取价值最高者放入背包,.,当背包剩余容量,=0,或物体全部装入背包为止,16,void,Knapsack(int,n,float M,float v,float w ,float x),Sort(n,v,w);,/,按单位价值排序,/,int,i;,for(i=1;i=n;i+)xi=0;,float c=M;,/c,为背包剩余空间,/,for(i=1;i c)break;,xi=1;,c-=wi;,if(i,贪心算法,X:,解向量,w:,物体重量,V:,物体价值,M:,背包容量,n:,物体数量,17,背包问题中的物体不能分拆,只能整个装入称为,0-1,背包问题,.,用贪心算法能得到,0-1,背包的最优解吗,?,算法设计与分析,贪心算法,n=3,c=25,(,v,1,v,2,v,3)=(35,24,15),(w1,w2,w3)=(18,15,10),例,分析,:,单位价值,(,v,1/w1,v,2/w2,v,3/w3),=(35/18,24/15,15/10),=(1.94,1.6,1.5),装入顺序,:(x1,x2,x3),贪心解,:(1,0,0),总价值,35,最优解,:(0,1,1),总价值,39,18,问题,设一个由,N,个城市,v,1,v,2,v,n,组成的网络,c,i,j,为,从,v,i,到,v,j,的代价不妨设,c,i,j,=,c,j,i,且,c,i,i,=,.,一推销员要从,某城市出发经过每城市一次且仅一次后返回出发地,问如何选择路线使代价最小。,问题抽象,将城市以及之间的道路抽象为一个无向图,G,G,中每边的权值表示这段线路的代价,.,问题转化为求一条最佳周游路线,:,从一点出发,经过每点一次且仅一次并返回原点,且该路线的总代价最小,.,算法设计与分析,贪心算法,*旅行商问题,(,货郎担问题,),输入,:,任一连通图,G,可行解,:,从,v0,v0,的汉密顿回路,优化函数,:,回路各边的权之和,最优解,:,使优化函数达到最小值的回路,.,19,5,1,4,3,1,7,3,4,2,2,v1,v5,v2,v4,v3,C=,算法设计与分析,贪心算法,*旅行商问题,(,货郎担问题,),贪心解,:,最优解,:,1,2,5,4,3,1,路长,10,1,2,5,3,4,1,路长,14,20,输入,:,城市的数目,n,代价矩阵,c,=,c,(1.n,1.n).,输出,:,最小,代价,路线,1.tour:=0;/,tour,纪录路线,/,2.cost:=0;/,cost,纪录到目前为止的花费,/,3.v:=N;/,N,为起点城市,v,为当前出发城市,/,4.,for k:=1 to N-1 do,5.tour:=tour+(v,w)/,/(v,w),为,v,到其余点代价最小边,/,6.cost:=cost+c(v,w),7 v:=w,8 tour:=tour+(v,N),9 cost:=cost+c(v,N),print tour,cost ,算法的最坏时间复杂性为,O(n,2,),*,该算法不能求的最优解,.,算法设计与分析,贪心算法,该问题为,NP,难问题,.,旅行商问题贪心近似算法,21,算法设计与分析,贪心算法,上机作业：,1.,编写一个完整的背包问题贪心算法程序,.,2.,找零钱,.,设集合,1,2,5,10,50,100,是货币单位。,1),编写贪心算法,使买东西时找回的硬币数目最小,.,2),分析你的算法复杂性,.,3),货币单位集满足何条件可确保贪心法获最优解,?,22,算法设计与分析,贪心算法,贪心算法,要点,将问题的求解过程看作一系列选择,每次选择一个输入,每次选择都是当前状态下的最好选择,(,局部最优解,).,每作一次选择后,所求问题会简化为一个规模更小的子问题,.,从而通过每一步的最优解逐步达到整体最优解,.,一,.,最优化问题,1.,输入,(,或问题的解,):,可表为,n,元向量,(x1,x2,.,xn,).,2.,约束条件,:,满足约束条件的向量为可行解,.,3.,优化函数,:,是与可行解分量相关的函数,.,4.,最优解,:,使优化函数达到极限值的可行解,.,二,.,算法思路,23,算法设计与分析,贪心算法,三,.,算法模式,for i,1 to n do,x,selese,(A,),if,feasible,(solusion,x,),solusion,union,(solusion,x,),retur,n(solusion,),/,从,A,中选择一个当前最好输入,/,判断,X,是否包含在当前解中,.,/,将,X,与解合并,同,时修改目标函数,.,四,.,适用问题,具备,贪心选择,和,最优子结构,性质的最优化问题,24,问题,通讯过程中需将传输的信息转换为二进制码,.,由于,英文字母使用频率不同,若频率高的字母对应短的编码,频率低的字母对应长的编码,传输的数据总量就会降低,.,要求找到一个编码方案,使传输的数,据量最少,(,最佳编码,).,算法设计与分析,贪心算法,找最佳前缀编码问题可化为求一棵,为能正确译码,编码需采用,前缀码,.,前缀码和二叉树一一对应,.,最优二叉树,是编码的集合,.,其任一编码不能是另一编码的前缀,.,4.6,哈夫曼编码,25,最优二叉树,树的权,:,在,叶带权二叉树,中,若,带权为,w,i,的叶,其通路长度为,L(,w,i,),则称 为该叶带权二叉树的,权,.,最优二叉树,:,在所有叶带权为,w,1,w,2,w,t,的二叉树,T,中,w,(T),最小者称之,.,图论,根,树及其应用,w,(T)=,w,i,L(,w,i,),1,2,3,4,5,1,2,4,5,3,3,4,5,2,1,w,(T),为,33,w,(T),为,39,w,(T),为,50,26,算法设计与分析,贪心算法,输入,(,x1,xn,):,叶权,(,各字符出现的频率,),约束条件,:,叶带权二叉树,(,前缀码,),最优解,:,树权 最小的二叉树（最佳编码）,抽象描述,w,(T),27,设在,1000,个字母的文章中各字母出现的频率为,:,a:83,b:14,c:28,d:38,e:131,f:29,g:20,h:53.,14 20 28 29 38 53 83 131,34 28 29 38 53 83 131,34 57 38 53 83 131,57 72 53 83 131,72 110 83 131,110 155 131,155 241,396,最佳编码,:,a:10;b:1111;c:0101;d:110;,e:00;f:0100;g:1110;h:011,1),将权从小到大排序,2),每次选取最小权合并,例 题,算法设计与分析,贪心算法,哈夫曼编码,28,算法设计与分析,贪心算法,1),以,n,个字母为结点构成,n,棵仅含一个点的二叉树,集合,字母的频率即为结点的权,2,),每次从二叉树集合中找出两个权最小者合并,为一棵二叉树,:,增加一个根结点将这两棵树作,为左右子树,.,新树的权为两棵子树的权之和,.,3),反复进行步骤,2),直到只剩一棵树为止,.,算法思路,29,算法设计与分析,贪心算法,哈夫曼编码,30,template,BinaryTree,HuffmanTree,(T f,int,n),/,根据权,f 1:n,构造霍夫曼树,/,创建一个单节点树的数组,Huffman*W=,newHuffman,n+1,；,BinaryTree,z,zero,；,for(int,i=1,；,iQ(1),；,Q.Initialize(w,n,n),；,/,将堆中的树不断合并,Huffman x,y,for(i=1;i,贪心算法,哈夫曼编码,32,问题,给定带权有向图,G=(V,E),要求找出从,V,的一点,v,0,(,源点,),到其他任意顶点的最短路径,.,算法设计与分析,贪心算法,算法思路,(,Dijkstra,):,设最短路长已知的终点集合为,S,初始时,v,0,S,其最短路长为,0.,然后用贪心选择逐步扩充,S:,每次在,V-S,中,选择,长度最短的一条最短路径,的终点加入,S,例 题,求路长最短的最短路径,:,只需,求出,v0,到,V-S,中各点的,当前最短路长,并取最小者的终点,u,加入,S,即可,.,例 题,计算,v0,到,V-S,中各点的,当前最短路长：,该长度或者是弧,(v,0,u),或者是从,v,0,出发,中途只经过,S,中的顶点到达,u,的路径长,.,4.7,单源最短路径,33,算法设计与分析,贪心算法,例如,:v1,到其他各点的最短路,34,算法设计与分析,贪心算法,算法描述,(1),用代价矩阵,c,来表示带权有向图,cij,表示弧,上的权值,.,若,E,则置,cij,为,设,S,为已知最短路径的终点的集合,初值为空,.,从源点,v,到图上其余各点,vi,的当前最短路径长度为,Di,其初值为,Di=cvi,vi,V,(2),选择,vj,使得,Dj=Min Di|vi,V-S,vj,就是长度最短的最短路径的终点。令,S=S,j,(3),修改从,v,到集合,V-S,上任一顶点,v,k,的当前最短路径长度,:,如果,Dj+cjk,贪心算法,单源最短路径,例 题,1)v1,v2:10,2)v1,v3:50,3)v1,v4:30,4)v1,v5:60,36,算法设计与分析,贪心算法,void,Dijkstra(int,n,int,v,T d,int,prev,Type*c),bool,smaxint,；,for(,int,i=1;i=n;i+),di=cvi,；,si=false,；,if(di=,maxint,),previ,=0,；,else,previ,=v;,dv=0,；,sv=true,；,for(,int,i=1;in,；,i+),int,temp=,maxint,；,int,u=v,；,for(,int,j=1,；,j=n,；,j+),if(!sj)&(djtemp),u=j,；,temp=dj,；,su=true,；,for(,int,j=1,；,j=n;j+),；,if(!sj),(cuj,maxint,),Type,newdist,=du)+cuj;,if(,newd,贪心算法,算法分析,用带权邻接矩阵表示有,n,个顶点和,e,条边的带权有向图,主循环体需要,O(n),时间,循环需要执行,n-1,次,所以完成循环需要,O(n,2,).,38,算法设计与分析,贪心算法,最小生成树,问题陈述,设,G(V,E),是一个无向连通带权图。,E,中每条边,(v,w),的权为,cvw,若,G,的一个子图,G,是一棵包含,G,的所有顶点的树，则称,G,为,G,的生成树。生成树各边权的总和称为该生成树的耗费。在,G,的所有生成树中,耗费最小的生成树称为,G,的最小生成树,.,抽象描述,输入,:,任一连通图,(,该图的边集合,),可行解,:,图的生成树,优化函数,:,生成树的各边权值之和,最优解,:,使优化函数达到最小的生成树,.,4.8,最小生成树,例 题,39,e1(1),e2(6),e8(9),e6(2),e9(4),e5(5),e4(7),e10(8),e11(3),e7(10),e3(11),1),以,G,中全部点为点作图,2),将各边按权值递增排序,3),依次添加各边,若出现回路,则忽略此边,.,4),加入,n-1,条边后就得到最小,生成树,.,1,2,5,3,7,图论,树与生成树,求最小生成树,(,Kruscal,),最优解,:(,e1,e6,e11,e5,e4,),40,算法思路,将,G,的,n,个顶点看成,n,个孤立的连通分支,1).,将所有的边按权从小到大排序,.,2).,从第一条边开始,依边权递增的顺序依次查看每一边,(v,w):,如果端点,u,和,w,分别是当前两个不同的连通分支,T1,T2,中的顶点时,就用边,(u,w),将,TI,和,T2,连接成一个,连通分支,.,3).,查看第,k+1,条边,.,4).,直到只剩下一个连通分支为止。,Kruskal,算法,G=(V,E),V=1,2,n,c=(c,i j,),为代价矩阵,例 题,算法设计与分析,贪心算法,最小生成树,41,算法设计与分析,贪心算法,最小生成树,例 题,42,template,bool,Kruskal,(,int,n,int,e,EdgeNode,E,EdgeNode,t ),MinHeap,H(1);,H.Initialize(E,e,e);,UnionFind,U(n);,iht,k=0;,while(e&k n-1),EdgeNode,x;,x.u=2;,x.v=1;,x.weight=5;,H.,DeleteMin(x,);,e-;,int,a=U.Find(x.u);,int,b=,U.Eind(x.v,);,if(a!=b),tk+=x;,U.Union(a,b);,H.Deactivate(),renturn,(k=n-1),Kruska,算法,算法设计与分析,贪心算法,最小生成树,43,当图的边数为,e,时，将其组成优先队列需,O(e),时间,while,循环中,DeleteMin,需要,O(loge),时间,.,故优先队列所需时间,O(eloge,),。,实现,UnionFind,所需时间为,O(eloge,),所以,Kruska,的时间是,O(eloge,).,适合求边数较少的最小生成树,。,算法设计与分析,贪心算法,最小生成树,算法分析,44,算法思路,1.,置,S=1,T=.,2.,若,S,V,选取边,(i,j):i,S,j,V-S,且,cij,最小,.,3.,将顶点,j,添加到,S,中,边,(i,j),添加到,T,中,.,4.,直到,S=V,时为止,.,T,中的所有边构成,G,的一棵最小生成树。,void,Prim(int,n,Type *c),T=;,S=1;,while(S!=V),(i,j)=i,S,且,j,V-S,的最小权边,;,T=TU(i,j);,S=S U j;,算法描述,Prim,算法,设,G=(V,E),是连通带权图,v=l,2,n.c=(,cij,),为代价矩阵,算法设计与分析,贪心算法,最小生成树,45,例 题,算法设计与分析,贪心算法,最小生成树,46,template,void,Prim(int,n,Type*c),Type,lowcostmaxint,;,int,closest maxim;,bool,smaxint,;,s1=true;,for(int,i=2;i=n;i+),lowcosti,=cli;,closest i=1;,si=false;,for(,int,i=1;i,贪心算法,最小生成树,Type min=,inf,;,int,j=1;,for(,int,k=2;k=n;k+),if(,lowcostk,min)&(!sk),min=,lowcost,k;,j=k;,cout,j closestj end;,sj=true;,for(intk,=2;k=n;k+),if(cjk,贪心算法,4.9,多机调度问题,问题描述,要求给出一种作业调度方案，使所给的,n,个作业在尽可能短的时间内由,m,台机器加工处理完成,.,作业,i,所需时间为,t,i,.,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断,作业不能拆分成更小的子作业。,该问题是,NP,完全问题，到目前为止还没有有效的解法。用贪心选择策略有时可设计出较好的近似算法。,贪心近似算法,采用,最长处理时间作业优先,的贪心策略,.,当,nm,时,只要将机器,i,的,0,ti,时间区间分配给作业,i,即可,;,当,nm,时,将,n,个作业依其所需的处理时间从,大到小排序,然后依次将作业分配给空闲的处理机,。,48,算法设计与分析,贪心算法,例题,设,7,个独立作业,1,2,3,4,5,6,7,由,3,台机器,M1,，,M2,和,M3,加工处理。各作业所需的处理时间分别为,:,2,14,4,16,6,5,3,。,按算法,greedy,产生的作业调度如下图所示,:,所需的加工时间为,17,49,算法设计与分析,贪心算法,class,JobNode,friend void,Greedy(JobNode,*,int,int,);,friend void main(void);,public:,operator,int,()const return time;,private:,int,ID,time;,class,MachineNode,friend void,Greedy(JobNode,*,int,int,);,public:,operator,int,()const return avail;,private:,int,ID,avail;,多机调度问题的贪心近似算法,50,template,void Greedy(Type a,，,int,n,，,int,m),if(n=m),cont”,为每个作业分配一台机器,.“,endl,return,；,Sort(a,，,n),；,MinHeap,H(m),；,MachineNode,x,；,for(int,：,i=1,；,i=1,；,i-),H,DeleteMin(x,),；,cout,”,将机器”,x,ID“,从”,x,avail,到”,(x,avail,十,ai,time),”,的时间段分配给作业”,ai.ID,贪心算法,基本思想,：,菲波那契提出的贪心算法,用变量,A,表示分子，变量,B,表示分母；（,1,）把,B,除以,A,的商的整数部分加,1,后的值作为埃及分,数的某一个分母,C,；（,2,）将,A,乘以,C,减去,B,作为新的,A,；（,3,）将,B,乘以,C,作为新的,B,；,(4),输出,1/C;,（,5,）如果,A,大于,1,且能整除,B,，则最后一个分母为,B/A,（,6,）如果,A,1,，则最后一个分母为,B,；（,7,）否则转步骤（,2,）。,53,伪代码,用变量,A,表示分子，变量,B,表示分母；,C=BA+1,A=A*C-B,B=B*C,打印,1/C,若,A1,且,B/A=BA,，则,C=B/A,若,A,1,，则,C=B,打印,1/C,转步骤（,2,）。,54,程序清单：,CLS,DO,INPUT,a,b,=;a,b,LOOP UNTIL a 1 THEN PRINT+;,LOOP WHILE a 1,PRINT+1;b,END,55,算法设计与分析,贪心算法,作业,3,、,一辆汽车加满油后可行驶,n,公里,途中设有若干加,油站,若要使沿途加油次数最少,设计一个有效算,法,给出应该在那些加油站加油,.,56,算法设计与分析,贪心算法,本上机实验是,算法设计与分析,课程的重要组成部分，是该课程的重要实践环节。通过上机编程，使学生加深理解、验证、巩固课堂教学内容。本上机实验的主要任务是：,1,加深对所学算法设计方法的理解，,掌握算法设计方法,和技巧；,2,掌握算法复杂性分析的方法,学会分析算法的实际执,行效率。,3,运用所学算法设计方法解决简单的实际应用问题,.,上机目的,57,算法设计与分析,贪心算法,实验报告要求,算法上机实验报告,学号姓名 班级,1.,实验名称,2.,实验目的,3.,问题描述,:,4.,算法描述,:,可用伪码描述,也可用流程图,.,5.,源代码：要求可读性,(,有注释,),交互性,(,有输入提示,),结构化程序设计风格,(,分层缩进,),6.,实验数据和结果,:,要求用运行画面给出,(,抓图,).,7.,算法时间复杂性分析,:,最坏时间复杂性的阶,.,58,