取石子

简介:

Tang和Jiang非常喜欢玩一种有趣的小游戏: 有N个石子,两人轮流从中取出1个, 3个或4个石子,当石子被取空时,游戏结束。最后一个取石子的人获胜, 第一次总是Tang取. 当然,他们俩都足够聪明,总会采取最优的策略。
Input
每行会有一个正整数N(N<=100000), 代表石子的个数, N=0 代表输入结束
Output
输出获胜人的名字。
Sample Input
1 //石头数量为1
2
0
Sample Output
Tang //石头数量为1的时候,总是Tang会赢
Jiang

 

分治法: 穷举出所有可能的取石头方案                                             

算法思想,假设两个玩家分别pid编号为0和1。f(n, pid)表示当前一轮获胜的玩家编号(如果f=0,表示获胜玩家是0),其中n表示当前一轮的石头总数,pid表示当前一轮的玩家标号。

      考虑分治算法的思想,当前一轮的胜负结果取决于对下一轮各种情况的结果的统计。这个统计有两种情况:

      1、当前一轮玩家pid=0,那么他取石头的可能性为1,3或4。则下一轮玩家pid=1的情况有三种: f(n-1, 1),f(n-3,1),f(n-4,1)。如果这三种情况的f()函数值至少有一个是0,不妨假设f(n-1, 1)=0,根据题目条件的"他们俩都足够聪明,总会采取最优的策略。" ,那么当前一轮pid=0的玩家一定会选择取1个石头,结果也一定是pid=0赢。

           因此当pid=0时, f(n ,0)=f(n-1, 1)&f(n-3, 1)&f(n-4, 1)

      2、当前一轮玩家pid=1,那么下一轮三种情况下只要有一个f()函数值为1,则结果一定是pid=1赢。即

           当pid=1是, f(n ,1)=f(n-1, 0)|f(n-3, 0)|f(n-4, 0)

代码                                                                                   

复制代码
public class RecurStonePlay {  
    private static final String[] PLAYER={"Tang","Jiang"};  
    /** 
     * 当前轮到第pIdx个PLAYER从剩下的stoneNum块石头中取石头获胜的情况 
     * @param stoneNum 当前石头总数 
     * @param pIdx 取石头的人的ID 
     * @return 在当前这种情况下,能够取胜的PLAYER的ID 
     */  
    public static int turn(int stoneNum,int pIdx){  
          
        //当前只有1,3,4块石头时,则当前PLAYER[pIdx]能够取胜  
        if(stoneNum==1||stoneNum==3||stoneNum==4) return pIdx;  
        //当前只有2块石头时,则PLAYER[(pIdx+1)%2]能取胜  
        if(stoneNum==2) return (pIdx+1)%2;  
          
        //如果当前是PLAYER[0]取石头,则只要取1,3,4块三种情况中一种情况下能够取胜,则PLAYER[0]获胜。  
        //使用&运算,如果有一个0,则结果为0  
        if(pIdx==0)  
            return turn(stoneNum-1,(pIdx+1)%2)&turn(stoneNum-3,(pIdx+1)%2)&turn(stoneNum-4,(pIdx+1)%2);  
        //与上面情况相反,如果有一个1,则结果为1  
        else  
            return turn(stoneNum-1,(pIdx+1)%2)|turn(stoneNum-3,(pIdx+1)%2)|turn(stoneNum-4,(pIdx+1)%2);  
    }  
      
       //测试  
    public static void main(String[] args) {  
                //石头总数为5块,PLAYER[0]开始先玩  
        System.out.println(PLAYER[RecurStonePlay.turn(5,0)]);  
    }  
}
复制代码

分析                                                                                   

上面的方法时间复杂度太高,那么 是否能够通过对当前一轮石头总数的判断,可以知道是当前玩家赢(先手赢),还是下一轮的玩家赢(后手赢)呢? 

我们假设先手玩家是Player1,后手玩家是Player2。用上面的程序运行1-30个石头,并输出赢的情况(其中0代表Player1赢,1代表Player2赢)。

1  2   3  4  5  6  7  8  9   10   11  12  13  14  15   16  17  18   19  20  21  22  23  24  25  26  27   28  29  30

0  1   0  0  0  0  1   0  1    0    0    0    0    1    0    1     0    0    0    0    1     0    1     0    0    0    0      1     0    1

我们可以发现,凡是mod 7 余2或0的石头数目,都是后手赢,其他情况都是先手赢。 我们来证明一下:

(1) stoneNum=1,2,3,4时就不证明了。

(2) 当stoneNum=2的时候,是Player2赢。我们能够想到,如果Player1抽取石头后,能使得Player2玩的时候手头上的石头数量为2。那么Player1一定赢。也就是说(2+1=3),(2+3=5),(2+4=6)的石头数量一定导致Player1赢。

(3) 当stoneNum=7的时候,Player1无论抽1,3,4块石头中的任意情况,都会使得Player2玩的时候手头上的石头数量为6,4,3。这三种石头数量都是当前玩家赢(Player2赢)。因此7块石头一定是Player2赢。

(4) 当stoneNum=7的时候,情况与(2)相同。因此(7+1=8),(7+3=10),(7+4=11)的石头数量一定是Player1赢。

(5) 当stoneNum=9的时候,情况与(3)相同。因此9块石头一定是Player3赢。

(6) 依次下去,我们就能够得出这个结论:

策略:如果当前石头数量stoneNum%7==2||stoneNum%7==0,那么一定是后手赢。除此之外是先手赢。




本文转自我爱物联网博客园博客,原文链接:http://www.cnblogs.com/yydcdut/p/3906100.html,如需转载请自行联系原作者

相关文章
|
3月前
报数
【7月更文挑战第4天】报数。
64 2
|
4月前
|
机器学习/深度学习 资源调度 算法
杜教筛
【6月更文挑战第9天】
24 2
|
5月前
|
JavaScript
线性dp之石子合并
线性dp之石子合并
|
11月前
一个求公约数和公倍数的有趣求法
一个求公约数和公倍数的有趣求法
48 0
|
人工智能
石子合并-区间dp
石子合并-区间dp
73 0
区间DP:合并石子
区间DP:合并石子
54 0
|
存储
欧拉筛&&埃氏筛
欧拉筛&&埃氏筛
|
C++
201912-1报数
201912-1报数
74 0
201912-1报数
|
算法
区间DP
复习acwing算法基础课的内容,本篇为讲解基础算法:动态规划——区间DP,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
103 0
区间DP