精华内容
下载资源
问答
  • 多边形游戏

    2017-04-25 14:45:58
    算法设计与分析>>这么课的动态规划中的多边形游戏PPT。内容详细,简单易懂,纯个人理解综合汇总之精华,比其他的资料要好
  • 算法思想:动态规划实际问题:多边形游戏编写语言:Java前言多边形游戏问题是矩阵连乘的最优计算次序问题与凸多边形最优三角剖分问题的推广。我在解决凸多边形最优三角剖分问题时偶然间看到了这个结论,便跳过了该...

    算法思想:动态规划

    实际问题:多边形游戏

    编写语言:Java

    前言

    多边形游戏问题是矩阵连乘的最优计算次序问题与凸多边形最优三角剖分问题的推广。我在解决凸多边形最优三角剖分问题时偶然间看到了这个结论,便跳过了该问题,直接解决其推广的问题,即多边形游戏问题。对于凸多边形最优三角剖分问题有兴趣的读者,可以自行百度。

    问题描述

    有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符。每条边被赋予一个运算符+或*。所有边依次用整数1到n编号。

    游戏规则:

    删去一条边

    后续步骤按以下方式操作:

    选择一条边E及边E的两个顶点v1和v2

    用一个新的顶点v取代边E及由E连接着的2个顶点,将2个顶点上的数值由E上的运算符获得结果,病赋值给新的顶点v。最后,所有的边都被删除,游戏结束,得到游戏分数(最后顶点上的整数值)

    问题:对于给定的多边形,计算最高得分

    关键特征

    设给定的多边形的顶点和边的顺时针序列为 op[1], v[1], op[2], v[2], ..., op[n], v[n]。其中 op[i] 表示第 i 边所对应的运算符,v[i] 表示第 i 个顶点上的数值,1 <= i <= n。

    在所给定的多边形中,从顶点 i 开始,长度为 j(链中有 j 个顶点) 的顺时针链 p(i, j) 可表示为 v[i], op[i + 1], ..., v[i + j - 1]。如果这条链的最后一次合并运算发生在 op[i + s] 处,则可在 op[i + s] 处将链分为两个子链 p(i, s) 和 p(i + s, j - s)。

    设 m1 是子链 p(i, s) 内部合并得到的值,设 a 和 b 是子链 p(i, s) 内部合并可能得到的最小值和最大值;设 m2 是子链 p(i + s, j - s) 内部合并得到的值,设 c 和 d 是子链 p(i + s, j - s) 内部合并可能得到的最小值和最大值。则有:a <= m1 <= b, c <= m2 <= d。而两个子链合并得到的结果 m = (m1)opi + s。分析运算符的情况可得:

    当op[i + s] = '+'时,显然有 a + c <= m <= b + d。即链 p(i, j) 合并的最优性可由子链 p(i, s) 和 p(i + s, j - s) 的最优性推出。且最大值对应子链的最大值,最小值对应子链的最小值。

    当op[i + s] = '*'时,考虑到 v[i] 可以取负整数,显然有 min{ac, ad, bc, bd} <= m <= max{ac, ad, bc, bd},亦可由子链的最有性推出原链的最优性。

    综上,可得多边形游戏问题满足最优子结构性质

    递归结构

    设 m[i, j, 0] 是链 p(i, j) 合并的最小值,m[i, j, 1] 是链 p(i, j) 合并的最大值,并设最优合并在 op[i+s] 处,为方便起见,记:a=m[i, i+s, 0], b=m[i, i+s, 1], c=m[i+s, j-s, 0], d=[i+s, j-s, 1],则关系式满足:

    当 op[i+s]='+', min(i, j, s) = a+c, max(i, j, s) = b+d

    当 op[i+s]='*', min(i, j, s) = min(ac, ad, bc, bd), max(i, j, s) = max(ac, ad, bc, bd)

    由此可知 m[i, j, 0]=min(min(i, j, s)), m[i, j, 1]=max(max(i, j, s)),其中 1 <= s <= j - 1,这是个循环求值的过程。

    Java代码

    //本代码所用示例为:+ -7 + 4 * 2 * 5

    public class PolygonGame

    {

    static int n; //边和点个数

    static int minf, maxf;

    static int[] v; //点集

    static char[] op; //边集

    static int[][][] m; //存储最终计算结果

    public static void main(String[] args)

    {

    n = 4;

    //以下所有数组下标为0的都不使用

    //构造出的多边形的最终结果:+ -7 + 4 * 2 * 5

    v = new int[]{Integer.MIN_VALUE, -7, 4, 2, 5};

    op = new char[] {' ', '+', '+', '*', '*'};

    m = new int[n + 1][n + 1][2];

    for(int i = 1; i <= n; i++)

    {

    //m[i][j][0]:表示链的起点为i,长度为j时的结果最小值

    m[i][1][0] = v[i];

    //m[i][j][1]:表示链的起点为i,长度为j时的结果最大值

    m[i][1][1] = v[i];

    }

    int result = polyMax();

    System.out.println(result);

    }

    /**

    * 参数含义:

    * i:链的起点

    * s:断开位置

    * j:链长度

    *

    */

    public static void minMax(int i,int s,int j)

    {

    int[] e = new int[n + 1];

    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

    {

    e[1] = a * c;

    e[2] = a * d;

    e[3] = b * c;

    e[4] = b * d;

    minf = e[1];

    maxf = e[1];

    for(int k = 2; k < 5; k++)

    {

    if(minf > e[k])

    minf = e[k];

    if(maxf < e[k])

    maxf = e[k];

    }

    }

    }

    public static int polyMax()

    {

    for(int j = 2; j <= n; j++) //链的长度

    //链的起点,多边形是封闭的,不会存在什么问题

    for(int i = 1; i <= n; i++)

    for(int s = 1; s < j; s++) //断开的位置

    {

    minMax(i, s, j);

    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];

    for(int i = 1; i <= n; i++)

    if(temp < m[i][n][1])

    {

    temp = m[i][n][1];

    }

    return temp;

    }

    }

    运行结果

    6b5dd9460b5c431ec8db4a9c023fdde2.png

    展开全文
  • 多边形游戏问题

    2018-03-26 13:10:08
    多边形游戏问题

    转自  https://blog.csdn.net/u013240812/article/details/23214239

    #include<iostream> 
    using namespace std;  
    int m[100][100][100]; 
    char op[100];//运算符 
    int v[100];//顶点数值  
    void minmax(int n,int i,int s,int j,int& minf,int& maxf,int m[100][100][100],char op[100])
    { 
        int e[4]; 
        int a=m[i][s][0],b=m[i][s][1]; 
        int r=(i+s-1)%n+1,c=m[r][j-s][0],d=m[r][j-s][1]; 
        if(op[r]=='t') 
        { 
            minf=a+c; 
            maxf=b+d; 
        } 
        else  
        { 
            e[1]=a*c; 
            //此链最后一次合并运算在op[i+s]处发生(1<=s<=j-1),则可在op[i+s]处将链分割成两个 
            //子链,p(i,s),p(i+s,j-s),设m1是对子链 p(i,s)的任意一种合并方式得到的值,而a,b分别是在所有可能的合并 
            //中得到的最小值和最大值,同理对m2,c,d;依此定义,a<=m1<=b,c<=m2<=d;  
            //由于子链 p(i,s),p(i+s,j-s)的方式决定了 p(i,s)在op[i+s]处断开后的合并方式,在 op[i+s]处合并后其值为 
            //m=(m1)op[i+s](m2) 
            //满足最优子结构性质,主链的最大值 最小值由子链的最大值最小值得到,由主链最优性可推出子链最优性  
            e[2]=a*d; 
            e[3]=b*c; 
            e[4]=b*d; 
            minf=e[1];maxf=e[1]; 
            for(int r=2;r<5;r++) 
            { 
                if(minf>e[r])minf=e[r]; 
                if(maxf<e[r])maxf=e[r];  
            } 
        } 
    } 
    int polymax(int n) 
    { 
        int minf,maxf; 
        for(int j=2;j<=n;j++) 
        { 
            for(int i=1;i<=n;i++) 
            { 
                for(int s=1;s<j;s++) 
                { 
                    minmax(n,i,s,j,minf,maxf,m,op); 
                    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]; 
        for(int i=2;i<=n;i++) 
        if(temp<m[i][n][1])temp=m[i][n][1]; 
        return temp; 
    }  
    int main() 
    { 
        int n;//顶点个数   
        while(cin>>n) 
        { 
            for(int i=1;i<=n;i++) 
            { 
                cin>>v[i]>>op[i]; 
            } 
            cout<<polymax(n)<<endl; 
        } 
    }  
    

     

    展开全文
  • 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。 游戏第1步,将一条边删除。 随后n-1步按以下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,470
精华内容 588
关键字:

多边形游戏