动态规划法求解多边形游戏
![动态规划法求解多边形游戏_第1页](https://file5.zhuangpeitu.com/fileroot5/2022-8/18/8c4f9b0b-a651-47e5-bad3-28f3220e747d/8c4f9b0b-a651-47e5-bad3-28f3220e747d1.gif)
![动态规划法求解多边形游戏_第2页](/images/s.gif)
![动态规划法求解多边形游戏_第3页](/images/s.gif)
《动态规划法求解多边形游戏》由会员分享,可在线阅读,更多相关《动态规划法求解多边形游戏(5页珍藏版)》请在装配图网上搜索。
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;
7、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(i=0;i1000000000;i+) p=p+i;end=clock();printf(The time is %6.3f,(double)(end-start-over)/CLK_TCK); return 0;
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。