算法设计与分析 学号： 120410101 姓名： 陈颖萍 班级： 日期： 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策略选择：采用蛮力法，从右向左处理表达式一旦出现错误的情况直接输出不匹配退出，否则继续进行处理直至表达式结束用栈作为存储结构约定优先级Stack S,OP; S存储运算符，OP存储参与运算的数字遇到‘（’、数字，时直接压入相应的栈中，当遇到+、-、*、/操作符是先把栈S中的栈顶元素取出比较相应的优先级，若当前操作符的优先级低与栈顶的则进行一次运算不断计算直至符合结束条件1-4模型：采用信息数字化的方法，用栈作为存储结构约定优先级Stack S,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，lenG[i][j]=len;G[j][i]=lenT++T=1I<=nx[i]=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 G[MAX][MAX];int ans[MAX],x[MAX];int bestc,cc;void init(int n,int m){ int i,j,len,t; memset(G,NoEdge,sizeof(G));//将图的加权邻接矩阵初始化为-1 cout<<"请输入城市间的路程"<>i>>j; cin>>len; G[i][j]=len;//给加权邻接矩阵赋值 G[j][i]=len; } for(i=1;i<=n;i++) x[i]=i;开始T=iI=jJ=t结束 bestc=-1;//0x7fffffff表示赋权值无限大，也可以是INT_MAX常量 cc=0;//当前路程}void S &i,int &j){ int t; t=i; i=j; j=t;}开始I=n+1G[x[n-1]][x[n]]!=NoEdge&& G[x[n]][1]!=NoEdge&& (cc+G[x[n]][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策略选择：采用递归回溯算法，递归出口为N>5，当满足该条件时，就将此时的安排输出递归公式为work(x+1,t)表示第x个人取第i个工作效益为t同时用used数组来标记某个工作是否被安排人做，若used[i]=1才能继续递归3-4模型：采用递归公式的抽象和数组特性和数据抽象的方法，f[x]表示计算过程中第x个员工当前的安排，g[i]表示当前最佳安排方案中第i个员工的工作，used[6]表示五个工作，用过后置0递归公式为work(x+1,t)，用来计算第x+1个工人的工作，层层递归直至找到最优解。
3-5时间及空间复杂度分析时间复杂度：T(n)空间复杂度：S(n2)3-6算法描述（流程图）：开始X>NBestusing namespace std;int best=0,f[6]={0},g[6]={0},used[6]={0,1,1,1,1,1};//best 当前的最佳安排时的收益//f[x] 计算过程中第x个员工当前的安排//g[i] 当前最佳安排方案中第i个员工的工作//used[6]五个工作，用过后置0char man[100]="ABCDE";//注意此。