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

2015-2016第2学期算法设计与分析实验报告多边形游戏问题实验报告专业班级计算机科学与技术2014-2班学号姓名刘威威1、实验环境Visual C+ 6.02、实验目的和要求给定N个顶点的多边形，每个顶点标有一个整数，每条边上标有+(加)或是(乘)号，并且N条边按照顺时针依次编号为1N。下图给出了一个N4个顶点的多边形。游戏规则 ：(1) 首先，移走一条边。(2) 然后进行下面的操作： 选中一条边E，该边有两个相邻的顶点，不妨称为V1和V2。对V1和V2顶点所标的整数按照E上所标运算符号(+或是)进行运算，得到一个整数；用该整数标注一个新顶点，该顶点代替V1和V2 。 (3) 持续进行此操作，直到所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。3、解题思路、伪代码3.1解题思路解决该问题可用动态规划中的最优子结构性质来解。设所给的多边形的顶点和边的顺时针序列为op1,v1,op2,v2,op3,opn,vn 其中，opi表示第i条边所对应的运算符，vi表示第i个顶点上的数值，i=1n。在所给的多边形中，从顶点i（1=i=n）开始，长度为j（链中有j个顶点）的顺时针链p(i,j）可表示为vi,opi+1,vi+j-1。如果这条链的最后一次合并运算在opi+s处发生（1=s=j-1），则可在opi+s处将链分割为两个子链p(i,s)和p(i+s,j-s)。设mi,j,0是链p(i,j)合并的最小值，而mi,j,1是最大值。若最优合并在opi+s处将p(i,j)分为两个长度小于j的子链的最大值和最小值均已计算出。即：a=mi,s,0 b=mi,s,1 c=mi+s+1,j,0 d=mi+s+1,j,1(1) 当opi+s=+时 mi,j,0=a+c ；mi,j,1=b+d(2) 当opi+s=*时mi,j,0=minac,ad,bc,bd，mi,j,1=maxac,ad,bc,bd 由于最优断开位置s有1=s=j-1的j-1中情况。 初始边界值为 mi,1,0=vi 1=i=n mi,1,1=vi 1=in时，顶点i+s实际编号为(i+s)modn。按上述递推式计算出的mi,n,1记为游戏首次删除第i条边后得到的最大得分。主链的最大值和最小值可由子链的最大值和最小值得到。 3.2 伪代码#include#define MAX_VETEX_SIZE 20 int REAL_SIZE; int mMAX_VETEX_SIZEMAX_VETEX_SIZE+12; int vMAX_VETEX_SIZE; char opMAX_VETEX_SIZE; void init_m()int i;for(i=0;in2)?(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);void minMax(int i,int s,int j,int* minf,int* maxf) int a,b,c,d,r;a = mis0; b = mis1;r = (i+s)%REAL_SIZE;c = mrj-s0;d = mrj-s1;if(opr = +) *minf = a+c;*maxf = b+d;else getMin_Max(a*c,a*d,b*c,b*d,minf,maxf); int Poly_Max()int minf,maxf,temp;int i,j,s;for(j=2;j=REAL_SIZE;j+) for(i=0;iREAL_SIZE;i+)for(s=1;s minf) mij0 = minf;if(mij1 maxf) mij1 = maxf;temp = 0;for(i=1;i mtempREAL_SIZE1)temp = i;return mtempREAL_SIZE1;void main()int i =0;scanf(REAL_SIZE); for(i=REAL_SIZE-1;i=0;i-) scanf(%d %c,&vi,&opi); init_m(); printf(Poly_Max(); 4、实验步骤4.1输入：4.2输出：5、讨论和分析 通过这次的实验我深刻了解到了采用动态规划策略的实用性、有效性、重要性。遇到的问题是遇到规模较大的时候很难继续进行求解和划分能够精简。采用动态规划策略是一个很重要的算法，因为它是把复杂的问题