首页 > 代码库 > 博弈问题-Alice与Bob拿牌游戏
博弈问题-Alice与Bob拿牌游戏
Description
Bob and Alice play a game, and Bob will play first.
Here is the rule of the game:
1) There are N stones at first;
2) Bob and Alice take turns to remove stones. Each time, they can remove p^k stones. p is prime number, such as 2, 3, 5, ..., and k is an non-negative integer.
3) The one who removes the last stone wins the game.
You have to tell Bob, if both Alice and Bob play perfectly, who will win the game.
Input
The first line of the input is a positive integer T (1<T<=10000). T is the number of the test case followed.
Each test case contains one line with an integer N (1<N<1000000) which is the number of the stones at the beginning.
Output
The output of each test case only contains the name of the winner: "Bob" or "Alice". No any redundant spaces is needed.
Sample Input
Copy sample input to clipboard256
Sample Output
BobAlice
大体意思就是Alice和Bob玩游戏，有n个牌，每人每次只能拿一个质数的幂次个，Bob先来，然后轮流拿，然后拿走最后一根的就赢，给定一个数n，判断在最佳策略下谁赢。
这个问题看起来有些复杂，其实只要从最简单情况出发，进行推导就可以得出答案，具体步骤如下：
1.显然可知，当n=1,2,3,4,5是Bob赢，当n=6时Alice赢，在这里把6称作”坏数“，因为谁拿它谁输；
2.那么当n=6+1,2,3,4,5=7,8,9,10,11时也是Bob赢，因为此时Bob只要再分别拿1,2,3,4,5张就可以使剩下的变为6，将6这个坏数抛给Alice，使Alice输；而当n=6+6=12时却做不到，因为此时最小唯一的小于12的“坏数”是6,而Bob却显然无法拿6（坏数）张牌。
3.当n=12+1,2,3,4,5=13,14,15,16,17时，也是Bob赢，因为Bob只要再分别拿1,2,3,4,5张就可以把12这个“坏数”抛给Alice（之前已经推导出，12是一个”坏数“（谁拿谁输））；当n=12+6=18时，Bob便无法拿12张，6张（坏数张），使得剩下为6,12而将坏数抛给Alice，一旦做不到这样，他就只能抛给Alice一个“好数”，在这之后Alice或者直接拿完剩下的牌，如果不行的话也可以产生一个坏数扔给Bob，无论怎样Bob都会输。
其实在这里还有一点，怎么证明Alice如果不能直接拿完剩下的牌，也一定可以产生一个坏数扔给Bob而使Bob输呢？因为从之前6,12,18可以看出1-18中，只有“坏数”不能产生减去质数的幂个从而产生坏数（所以才会输），“好数”是一定可以产生坏数的（所以才赢），当n>18时一样可证（后文有数学归纳法证明）。
4.相信到这里你已经看出来了，n=18+1,2,3,4,5=19,20,21,22,23时，同样是“好数”，Bob会赢，n=18+6时无法产生坏数，Bob又要输，直到这里，我们已经可以看出，6的倍数都为坏数，且坏数都为6的倍数就算你不信，我们至少可以手算出6,12这两个坏数是6的倍数，那么由数学归纳法，假设n=6m，当m<=k时已证6的倍数是坏数且坏数是6的倍数，那么当m=k+1，时，要证n为一好数（即推翻我的结论），便要让此时的n=6（k+1）减掉一个好数变为坏数，由之前假设得，由于之前坏数都为6的倍数，那么它只能减掉6的倍数才能产生6的倍数（因为他本身是6的倍数），而之前假设同样已证6的倍数是坏数，因而它是不能减的，得证。（说的有些啰嗦，请海涵）
到这里我们已经可以得出结论来了，if（n%6），Bob赢，else Alice赢（真是个令人难过的结论）。
总结：1.其实从以上推导可以看出，所有的数被分到两个集合：A（好数）和B（坏数），A集合的数满足以下特性：可以一次拿走或可以拿走一些后产生B集合的数；B集合的数具有以下特性：不可能一次拿走而且拿走一些数只能产生A集合的数而不能产生B集合的数（嵌套了，有些难理解）。只要这样，如果Bob一开始拿到B数，起码这回合不会马上赢，而且必须给Alice一个A数，而Alice得到A数就算不能一次拿光，可以再产生一个B数抛回来，这样Bob又没法赢，Alice可以一直持续这样做使Bob一直没法赢，直到Alice得到一个可以一次拿光的A数Alice就赢！如果Bob一开始得到一个A数就可以按Alice的做法故技重施直到自己赢，这就是经由以上归纳分析得出的最佳策略！
2.其实多看几道博弈问题就会发现，最优策略就是让对方“不得不做”，而我方却始终可以让对方陷入“不得不做”的境地 ，这样就会赢！进一步归纳，博弈问题一般的局面形势可分为两种：“不得不做”的形势，可以让对方陷入“不得不做”的形势的形势，只要玩家找到这两种形式的分界（这是最难的也是核心所在），就可在游戏开局可以看出自己处于那一种形势，从而立于不败之地！
3.笔者刚看到这道题的时候，老是把重点放在Bob先拿上，即使知道Bob怎样做才合适，然而觉得Alice的行为具有不确定性，因而感觉太难，不会做，但正如以上所说，博弈问题的最优策略便是消除对方行为的不确定性，使对方不得不做；此外老是纠结于“质数次幂”，结果质数次幂完全没用上，反而从1,2,3,4,5,6这几个最基本的数便可推导出结论！
4.从这道题可以看出，博弈问题的双方遵守同一个规则，因而他们是想着同一个方向努力，因而不必纠结于谁先谁后，也不必纠结于两个玩家，只看一个玩家即可，有时甚至不要太纠结于规则（比如题目中的质数次幂），如果不知道怎样做自己才必然赢的话，那么可以换个角度，只要想方设法让对方输即可，如果仍感觉无从下手，可以先从最简单的开始，然后推导，归纳或许就会有新发现！
（第一次写博客，有些啰嗦，请海涵）
博弈问题-Alice与Bob拿牌游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。