【Game】找出游戏必胜态

//两人取硬币游戏 hard coins game int solve() { int win[MAX]; //定义轮到自己，当剩下j个时为必胜OR必败态/****j=0时，必败。对于某个a[i], j-a[i]为（对手）必败态，则 j 个时自己可以有必胜态对于任意a[i], j-a[i]为（对手）必胜态，则自己没机会胜利了******/ memset(win,false,sizeof(win)); win[0]=false;//a[] 是每次取硬币数应等于 a[i]. for(int j=1;j<=x;j++)//x是硬币总数 { for(int i=0;i<k;i++) if(j>=a[i]) { win[j]=!win[j-a[i]]; }//对手存在一个必败态，则自己可以有必胜态 } }

//****/Poj 2484

N枚硬币排成一圈，每次取连续的一枚或两枚。

先分析：后手取走一些币后，当这些币可以分成两组相同状态时，先手必败？！

显然先手在某一组做什么动作，后手在另一组采取相同策略，那么先手必定最先没币可取！

 

// hard coins gameint solve(){    int win[MAX];    //定义轮到自己，当剩下j个时为必胜OR必败态    memset(win,false,sizeof(win));    win[0]=false;//a[] 是每次取硬币数应等于 a[i].    for(int j=1;j<=x;j++)//x是硬币总数    {        for(int i=0;i<k;i++)            if(j>=a[i])            {                win[j]=!win[j-a[i]];            }//对手存在一个必败态，则自己可以有必胜态    }}

转载于:https://www.cnblogs.com/Airplus/p/3900166.html

相关资源：JAVA上百实例源码以及开源项目