分享程序员开发的那些事...
更新时间：2022-08-20 20:18:34
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，如需转载请自行联系原作者