算法设计及分析实验.docx

算法设计与分析 学号： 120410101 姓名： 陈颖萍 班级： 1204101 日期： 2014.01.01 实验题目11-1问题描述：括号检验：输入一个代数表达式，表达式只能含有+，*，/,1,2,3,4,5,6,7,8,9,0字符且每个数字均小于10，设表达式除括号外匹配有误外，再无其他错误。编写算法对输入的表达式进行检验，判断括号匹配是否正确。正确的： 错误的：1+2+4 (1+)2(1+2)+4 (1+2(4+3)(1+2) (1+2+3*(4+5() 1+2+3*(4+5)1-2问题分析：编写算法对输入的表达式进行检测，判断括号匹配是否正确。如果对于输入的表示能按照正确的优先级将最终结果求出那么表达式肯定是正确的。而如果要求出最终结果，效率会低，那么对运算过程进行简化，按照所给的表达式推导出最终可以求出结果那么表达式肯定是正确的，括弧肯定匹配。1-3策略选择：采用蛮力法，从右向左处理表达式一旦出现错误的情况直接输出不匹配退出，否则继续进行处理直至表达式结束。用栈作为存储结构约定优先级。StackS,OP;S存储运算符，OP存储参与运算的数字。遇到（、数字，时直接压入相应的栈中，当遇到+、-、*、/操作符是先把栈S中的栈顶元素取出比较相应的优先级，若当前操作符的优先级低与栈顶的则进行一次运算。不断计算直至符合结束条件。1-4模型：采用信息数字化的方法，用栈作为存储结构约定优先级。StackS,OP;S存储运算符，OP存储参与运算的数字。遇到（、数字，时直接压入相应的栈中，当遇到+、-、*、/操作符是先把栈S中的栈顶元素取出比较相应的优先级，若当前操作符的优先级低与栈顶的则进行一次运算。由于问题要求的是单位数而进行相应的运算后可能会变成小数，或多位数，若对其进行处理会麻烦，则默认运算后结果是1，将以压入相应的栈中。若在运算过程中不能进行或不可操作则说明表达式不正确。1-5时间及空间复杂度分析1-6算法描述（流程图）：1-7算法实现：1-8测试及说明：1-9总结实验题目22-1问题描述：某售货员要到若干城市去推销商品，已知个城市之间的路程（或旅费）。要选择一条从驻地出发，经过每一个城市一遍，最后回到驻地的路线，使总的路线最小。问题的解为从一个带权图中找到一个包含所有顶点的回路，且该回路的权值之和最小。用邻接矩阵存储图。2-2问题分析：该问题可以用邻接矩阵存储图，图的下标表示两个城市，图的权值表示两城市间的路程，此时的邻接矩阵是关于主对角线对称的。在此问题中要设定NoEdge =-1来表示当两个城市间无通路时邻接矩阵存储的值，方便在连接结点时进行判断。2-3策略选择：采用蛮力枚举的递归法，递归出口为i=n+1表示到达第n+1层也就是最后一个结点，此时完成了递归。递归公式为Traveling(i+1,n)，表示继续判断下一个结点是否能连接。2-4模型：开始memset(G,NoEdge,sizeof(G)T=1T=m输入i，j，lenGij=len;Gji=lenT+T=1I=nxi=iT+bestc=-1;cc=0结束采用递归公式的抽象的方法，问题的解为含有N个节点的一条回路，可以尝试将所有的路径都找出来找到权值之和最小的一条路径就为问题的解。向当前求解的路径中不断加入新的节点，当节点数为N时一条新的回路产生。可以路径的长度为控制量，用递归的方法求解所有的路径，如果有边与前一顶点相连且此点之前距离和仍小于最小值，那么可以选择这条路径，继续递归直至达到递归出口。2-5时间及空间复杂度分析时间复杂度：T(log2n)空间复杂度：S(n2)2-6算法描述（流程图）：2-7算法实现：#include using namespace std;const int NoEdge=-1;/表示两城市间不通const int MAX=20;int GMAXMAX;int ansMAX,xMAX;int bestc,cc;void init(int n,int m)int i,j,len,t;memset(G,NoEdge,sizeof(G);/将图的加权邻接矩阵初始化为-1cout请输入城市间的路程endl;for(t=1;tij;cinlen;Gij=len;/给加权邻接矩阵赋值Gji=len;for(i=1;i=n;i+) xi=i;开始T=iI=jJ=t结束bestc=-1;/0x7fffffff表示赋权值无限大，也可以是INT_MAX常量cc=0;/当前路程void Swap(int &i,int &j)int t;t=i;i=j;j=t;开始I=n+1Gxn-1xn!=NoEdge& Gxn1!=NoEdge& (cc+Gxn1bestc|bestc=-1)J=1J=nansj=xjJ+bestc=cc+Gxn1J=iJ=nGxi-1xj!=NoEdge & (cc+Gxi-1xjbestc|bestc=-1)Swap(xi,xj);cc+=G xi-1 xi;Traveling(i+1,n);cc-=G xi-1 xi;Swap(xi,xj)J+结束void Traveling(int i,int n)int j;if(i=n+1)/递归到n+1层时xn已经确定了，没有其他可以选择的/如果与前一顶点有联系，与结点1有联系，并且总距离小于之前的最小值，那么更新if(Gxn-1xn!=NoEdge & Gxn1!=NoEdge & (cc+Gxn1bestc|bestc=-1)for(j=1;j=n;j+) ansj=xj;bestc=cc+Gxn1;elsefor(j=i;j=n;j+)/如果有边与前一顶点相连且此点之前距离和仍小于最小值，那么可以选择这条路径if( Gxi-1xj!=NoEdge & (cc+Gxi-1xjbestc|bestc=-1)Swap(xi,xj);cc+=G xi-1 xi;Traveling(i+1,n);开始Bestc=-1找不到符合条件的路径最短旅行路程bestcI=1I=nAnsiI+Ans1结束cc-=G xi-1 xi;Swap(xi,xj);void print(int n)if(bestc=-1)cout找不到符合条件的路径endl;elsecout最短旅行路程为bestcendl;cout最佳路径是;for(int i=1;i=n;i+)coutansi;coutans1endl;void main()int n,m;开始输入城市个数n输入城市间通路条数minit(n,m);Traveling(2,n);print(n)结束while(1)cout请输入城市的个数n;cout请输入城市间通路的条数m;init(n,m);Traveling(2,n);print(n);2-8测试及说明：2-9总结在此次实验中，我进一步练习了图的邻接矩阵的存储方式，在无向图的存储中，邻接矩阵是关于主对角线对称的，在初始化的过程中要注意双向初始化。当两城市间无通路时，要用特殊数值进行标记，方便进行判断。在今后的学习中，要学会将问题抽象出来进行解决。实验题目33-1问题描述：设有A,B,C,D,E 5人从事J1，J2，J3，J4，J5 5项工作，每人只能从事一项，他们的效益如下图所示，求最佳安排使效益最高。J1J2J3J4J5A10111047B13101085C59774D151210115E10118843-2问题分析：该问题适合用递归回溯法解决，用一个标记变量来存储当前最优解，不断递归来找当前最优解，当找到当前最优解后回溯到根结点，决定是否进行剪枝。如此往复，直至找到最优解。3-3策略选择：采用递归回溯算法，递归出口为N5，当满足该条件时，就将此时的安排输出。递归公式为work(x+1,t)表示第x个人取第i个工作效益为t。同时用used数组来标记某个工作是否被安排人做，若usedi=1才能继续递归。3-4模型：采用递归公式的抽象和数组特性和数据抽象的方法，fx表示计算过程中第x个员工当前的安排，gi表示当前最佳安排方案中第i个员工的工作，used6表示五个工作，用过后置0。递归公式为work(x+1,t)，用来计算第x+1个工人的工作，层层递归直至找到最优解。3-5时间及空间复杂度分析时间复杂度：T(n)空间复杂度：S(n2)3-6算法描述（流程图）：开始XNBesttBest=tJ=1J=NJ+gj=fjI=1I=Nusedi=1usedi=0;fx=i;t=0J=1J=xt+=mapj-1fj-1J+work(x+1,t);usedi=1i+结束3-7算法实现：#includeusing namespace std;int best=0,f6=0,g6=0,used6=0,1,1,1,1,1;/best 当前的最佳安排时的收益/fx 计算过程中第x个员工当前的安排/gi 当前最佳安排方案中第i个员工的工作/used6五个工作，用过后置0char man100=ABCDE;/注意此处不能用A,B,C,D,F赋值int map55=10,11,10,4,7,13,10,10,8,5,5, 9,7,7,4,15,12,10,11,5,10,11,8 ,8,4;int N=5;void work(int x,int t)/按排第x个人时，已经取得的效益为t if(xN)/5个人已经全部安排好，可以计算并输出最终结果if(bestt)/出现更好的安排方案best=t;for(int j=1;j=N;j+)gj=fj;for(int i=1;i=N;i+)if(usedi=1)/第i个工作还没有人usedi=0;fx=i;t=0;for(int j=1;j=x;j+)t+=mapj-1fj-1;work(x+1,t);/第X个人取得第i个工作usedi=1;void main()开始work(1,0)J=1Manj-1从事gj项工作J+J=N最大收益为best结束work(1,0);for(int j=1;j=N;j+)coutm