多边形游戏精要.pptx

  1. 1、本文档共16页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
多边形游戏精要

多边形游戏 多边形信息 单人玩游戏 开始时有一个由n个顶点构成的多边形 所有边和顶点依次用整数从1到n编号 每个顶点被赋予一个整数值 每条边被赋予一个运算符“+”或“×” 首先删除一条边 游戏规则 随后n-1步按以下方式操作: 1、选择连接着2个顶点 和 的边 2、2个顶点 和 通过边上的运算符 计算得到结果赋予新的顶点 运算后得到新顶点 最后所有边都被删除,游戏结束,所剩顶点上的整数值就是游戏的得分 问题:对于给定的多边形,计算最高得分。 从顶点 开始,长度为 (链中有 个顶点) 的顺时针链 可表示为 如果这条链的最后一次合并运算在 处发生 ,则可在 处将链分割为2个子链 和 。 最优子结构性质 子链 ,任意一种合并方式 得到的值 , 分别为最大值和最小值 同理子链 ,任意一种合并方式得到的值 , 分别为最大最小值 最优子结构性质 (1)当 时,显然有 (2)当 时,有 主链的最大值和最小值 可由子链的最大值和最小值得到。 由上述分析可知欲求主链的最大值,必须同时计算子链的最大值和最小值,所以设链 的 最大值 最小值 于是有 递归求解 (1)当 时 (2)当 时, 综合得到 主链 在 处断开 最大值 最小值 由于断开的位置s有j-1中情况 ,可得 初始的边界值为 由于多边形是封闭的,所以当 时,顶点 的编号为 所以按上式递推 即为游戏首次删去第 i 条边得到的最大分数 /* 6 *6+12*21*2+3*5 7 +14*23+18+52+3*9*25 */ #include stdio.h #define N 100 int m[N][N][2]; char op[N]; void Min_max(int n,int i,int s,int j,int *minf,int *maxf)//求最小最大值 { int a=m[i][s][0],b=m[i][s][1],r=(i+s-1)%n+1,c=m[r][j-s][0],d=m[r][j-s][1]; if(op[r]==+){*minf=a+c;*maxf=b+d;}//加法时候,最大值最小值一目了然 else{ int e[5];//乘法时候最大值最小值在于此 e[1]=a*c; e[2]=a*d; e[3]=b*c; e[4]=b*d; *minf=e[1];*maxf=e[1]; for(r=2;r5;r++){ if(*minfe[r]) *minf=e[r]; if(*maxfe[r]) *maxf=e[r];} } } int poly_max(int n) { int flag=0; int minf,maxf; for(int j=2;j=n;j++){//j为长度 for(int i=1;i=n;i++){//i为起点 for(int s=1;sj;s++){//s为断点 Min_max(n,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; } } } int temp=m[1][n][1];flag=1;//求n种情况,最后 for(int i=2;i=n;i++

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档