多边形游戏问题-实验报告

2015-2016第2学期《算法设计与分析》实验报告1/4多边形游戏问题实验报告专业班级计算机科学与技术2014-2班学号2220142506姓名刘威威1、实验环境VisualC++6.02、实验目的和要求给定N个顶点的多边形，每个顶点标有一个整数，每条边上标有+(加)或是×(乘)号，并且N条边按照顺时针依次编号为1~N。下图给出了一个N＝4个顶点的多边形。游戏规则：(1)首先，移走一条边。(2)然后进行下面的操作：选中一条边E，该边有两个相邻的顶点，不妨称为V1和V2。对V1和V2顶点所标的整数按照E上所标运算符号(+或是×)进行运算，得到一个整数；用该整数标注一个新顶点，该顶点代替V1和V2。(3)持续进行此操作，直到所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。3、解题思路、伪代码3.1解题思路解决该问题可用动态规划中的最优子结构性质来解。2015-2016第2学期《算法设计与分析》实验报告2/4设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],op[3],…,op[n],v[n]其中，op[i]表示第i条边所对应的运算符，v[i]表示第i个顶点上的数值，i=1~n。在所给的多边形中，从顶点i（1=i=n）开始，长度为j（链中有j个顶点）的顺时针链p(i,j）可表示为v[i],op[i+1],…,v[i+j-1]。如果这条链的最后一次合并运算在op[i+s]处发生（1=s=j-1），则可在op[i+s]处将链分割为两个子链p(i,s)和p(i+s,j-s)。设m[i,j,0]是链p(i,j)合并的最小值，而m[i,j,1]是最大值。若最优合并在op[i+s]处将p(i,j)分为两个长度小于j的子链的最大值和最小值均已计算出。即：a=m[i,s,0]b=m[i,s,1]c=m[i+s+1,j,0]d=m[i+s+1,j,1](1)当op[i+s]=’+’时m[i,j,0]=a+c；m[i,j,1]=b+d(2)当op[i+s]=’*’时m[i,j,0]=min{ac,ad,bc,bd}，m[i,j,1]=max{ac,ad,bc,bd}由于最优断开位置s有1=s=j-1的j-1中情况。初始边界值为m[i,1,0]=v[i]1=i=nm[i,1,1]=v[i]1=i=n因为多边形是封闭的，在上面的计算中，当i+sn时，顶点i+s实际编号为(i+s)modn。按上述递推式计算出的m[i,n,1]记为游戏首次删除第i条边后得到的最大得分。主链的最大值和最小值可由子链的最大值和最小值得到。3.2伪代码#includestdio.h#defineMAX_VETEX_SIZE20intREAL_SIZE;intm[MAX_VETEX_SIZE][MAX_VETEX_SIZE+1][2];intv[MAX_VETEX_SIZE];charop[MAX_VETEX_SIZE];voidinit_m(){inti;for(i=0;iREAL_SIZE;i++){m[i][1][0]=v[i];m[i][1][1]=v[i];}}voidgetMin_Max(intn1,intn2,intn3,intn4,int*min,int*max){*min=(n1n2)?((n2n3)?(n3n4?n4:n3):(n2n4?n4:n2)):((n1n3)?(n3n4?n4:n3):(n1n4?n4:n1));*max=(n1n2)?((n2n3)?(n3n4?n4:n3):(n2n4?n4:n2)):((n1n3)?(n3n4?n4:n3):(n1n4?n4:n1));}voidminMax(inti,ints,intj,int*minf,int*maxf){inta,b,c,d,r;a=m[i][s][0];b=m[i][s][1];r=(i+s)%REAL_SIZE;2015-2016第2学期《算法设计与分析》实验报告3/4c=m[r][j-s][0];d=m[r][j-s][1];if(op[r]=='+'){*minf=a+c;*maxf=b+d;}else{getMin_Max(a*c,a*d,b*c,b*d,minf,maxf);}}intPoly_Max(){intminf,maxf,temp;inti,j,s;for(j=2;j=REAL_SIZE;j++){for(i=0;iREAL_SIZE;i++){for(s=1;sj;s++){minMax(i,s,j,&minf,&maxf);if(m[i][j][0]minf)m[i][j][0]=minf;if(m[i][j][1]maxf)m[i][j][1]=maxf;}}}temp=0;for(i=1;iREAL_SIZE;i++){if(m[i][REAL_SIZE][1]m[temp][REAL_SIZE][1]){temp=i;}}returnm[temp][REAL_SIZE][1];}voidmain(){inti=0;scanf(REAL_SIZE);for(i=REAL_SIZE-1;i=0;i--){scanf(%d%c,&v[i],&op[i]);}init_m();printf(Poly_Max());}4、实验步骤4.1输入：2015-2016第2学期《算法设计与分析》实验报告4/44.2输出：5、讨论和分析通过这次的实验我深刻了解到了采用动态规划策略的实用性、有效性、重要性。遇到的问题是遇到规模较大的时候很难继续进行求解和划分能够精简。采用动态规划策略是一个很重要的算法，因为它是把复杂的问题简单化了，但它的一个缺点就是算法的规模太大了，效率低。关于这次算法我觉得划分是一个难点，因为当问题进行细化的时候会出现很多的问题不会将问题分解抽象的概念进行设计。这是我以后需要重点学习的知识点。