- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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)