动态规划法求解多边形游戏

1、算法分析与设计实验报告第 次实验实验名称动态规划法求解多边形游戏实验目的通过上机实验，掌握动态规划法的适用条件和解决思路，求解多边形游戏问题，并查看程序运行时间。实验原理(1) 设两条子链分别为p(i,j)和p(i+s,j-s)，在所有合并方式中的最大值和最小值分别为a,b和c,d；(2) 若opi+s=+,a+cmn时，顶点i+s编号为（i+s）mod n；递推得到min1即为游戏首次删去第i条边后得到的最大值。实验步骤(1) 分别用v和op表示顶点的数字和每条边上的运算符号,mij0和mij1表示两条子链的最小值和最大值；min,max存储最终的最小值和最大值；(2) 从删去第1条边递推遍

2、历，子链合并，找到此时的最大值；然后删去第i条边，依次循环，更新max和min值，得到最终的最大值。即需要一个三重循环实现。关键代码int polymax(int n,int v,char op) int i,j,k,s1,r; int minnum,maxnum,maxf; int e4; for(i=1;i=n;i+) mi10=mi11=vi; for(j=2;j=n;j+) for(i=1;i=n;i+) for(s1=1;s1=j-1;s1+) r=(i+s1-1)%n+1; if(op(i+s1)%n=+) mins1=mis10+mrj-s10; maxs1=mis11+mrj-

3、s11; else e0=(mis10)*(mrj-s10); e1=(mis10)*(mrj-s11); e2=(mis11)*(mrj-s10); e3=(mis11)*(mrj-s11); mins1=e0; maxs1=e0; for(k=1;kek) mins1=ek; if(maxs1ek) maxs1=ek; mij0=min1;mij1=max1; for(k=2;kmink)/计算首次删去第i条边的得分 mij0=mink; if(mij1maxk) mij1=maxk; sij=s1; maxf=m1n1; /首次删去第1条边的最大得分 for(i=2;i=n;i+)/首次

4、删去第i条边的最大得分 if(maxfmin1) maxf=min1; return maxf;测试结果四边形测试：五边形测试：实验心得通过本次实验设计了动态规划法解决封闭多边形游戏求最大值问题，感觉最关键的还是分析清楚动态规划法的最优子结构和重叠子问题性质，才会更容易的写出相应的代码函数。另外就是，作为一个封闭的多边形，删除第一条边后，需要从每个边处断开一次分成两个子链，这里一定是每个都遍历一遍才可以得到最后最大值的。附录：完整代码#include#include#include #include #include #define num 50 using namespace std;int

5、 mnumnum2,snumnum;int polymax(int n,int v,char op) int i,j,k,s1,r; int minnum,maxnum,maxf; int e4; for(i=1;i=n;i+) mi10=mi11=vi; for(j=2;j=n;j+) for(i=1;i=n;i+) for(s1=1;s1=j-1;s1+) r=(i+s1-1)%n+1; if(op(i+s1)%n=+) mins1=mis10+mrj-s10; maxs1=mis11+mrj-s11; else e0=(mis10)*(mrj-s10); e1=(mis10)*(mrj-

6、s11); e2=(mis11)*(mrj-s10); e3=(mis11)*(mrj-s11); mins1=e0; maxs1=e0; for(k=1;kek) mins1=ek; if(maxs1ek) maxs1=ek; mij0=min1;mij1=max1; for(k=2;kmink)/计算首次删去第i条边的得分 mij0=mink; if(mij1maxk) mij1=maxk; sij=s1; maxf=m1n1; /首次删去第1条边的最大得分 for(i=2;i=n;i+)/首次删去第i条边的最大得分 if(maxfmin1) maxf=min1; return maxf;int main( )int i,p=0; double k=0.0; clock_t start,end,over; start=clock(); end=clock(); over=end-start; start=clock(); int n,max; int v50; char op50;cout-动态规划法-多边形游戏-endl; coutn;cout请依次输入符号和顶点：endl; for(i=1;iopivi; getchar(); max=polymax(n,v,op); coutmaxendl; for