自己做网站需要什么,wordpress 怎么使用,亚马逊海外购官方网,html简单网页一、巴什博奕(Bash Game)
基本描述#xff1a;
只有一堆n个石子#xff0c;两个人轮流从这堆石子中取石子#xff0c;规定每次至少取一个#xff0c;最多取m个#xff0c;最后取完的人获胜。
分析#xff1a;
当n m的时候#xff0c;显然先手获胜#xff0c;因…一、巴什博奕(Bash Game)
基本描述
只有一堆n个石子两个人轮流从这堆石子中取石子规定每次至少取一个最多取m个最后取完的人获胜。
分析
当n m的时候显然先手获胜因为一次就能取完。当n m1 的时候由于先手最多取走m个无论其取走多少个剩下的后手均可以一次取完显然后手胜。根据以上分析我们可以将n写成 n (m1) * r s 的形式。对于先手玩家我们可以取走s个给对方造成剩下(m1) 整数倍的情形。此时无论对手取走多少个假设对手取走k个 我们一定可以做到取走 (m1-k)个此时剩下(m1) * (r-1)个那么留给对方又是(m1)的整数倍如此就可以保证 先手 取胜。
结论
当 n m 时先手必胜。当 n % (m1) 0时后手必胜。当 n % (m1) ! 0时先手必胜。
其中上述的情况1和3可以合并故
当 n % (m1) 0时后手必胜。当 n % (m1) ! 0时先手必胜。
注意
变形玩法两个人轮流报数每次至少1个数最多报10个数字谁先报到100取胜。
练习
HDU 1846HDU 2149HDU 2188HDU 4764
二、PN点分析
什么是PN点
P点即必败点。前一个选手(Previous player)将取胜的位置称为必败点。 N点即必胜点。下一个选手(Next player)将取胜的位置称为必胜点。
PN点的属性
所有终结点均为必败点(P点) 从任何必胜点(N点)操作至少有一种方法可以进入必败点(P点) 无论如何操作必败点(P点)都只能进入必胜点(N点)。
分析步骤
将所有终结位置标记为必败点(P点); 将所有一步能进入必败点(P点)的位置标记为必胜点(N点); 如果从某个点开始的所有一步操作都只能进入必胜点(N点)则将该位置标记为必败点(P点); 如果在步骤3中未能找到新的必败点(P点)算法终止否则返回步骤2.
结论
当行列都是奇数的时候一定是必败点否则为必胜点。
注意
至于结论怎么推出来的大家画一下3 * 4 4 * 4 3 * 3的PN分析图就知道了。
练习
HDU 2147
三、斐波那契博弈
基本描述
有一堆个数为n的石子游戏双方轮流取石子满足
先手不能再第一次把所有石子取完 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间包括1和对手取的石子数的2倍。 取最后石子的人为赢家。
结论
先说结论 当且仅当n不是Fibonacci数时先手必胜。换句话说先手必败构成Fibonacci数列。
分析
证明需要前置技能“Zeckendorf定理”齐肯多夫定理其表述为任何正整数可以表示为若干个不连续的Fibonacci数之和。
具体证明在这篇博文中给出有兴趣的读者可以自行学习。
练习
HDU 2516
四、威佐夫博弈
基本描述
有两堆各若干个石子两个人轮流从某一堆或者两堆中取同样多的物品规定每次至少取一个多着不限最后取完石子的人获胜。
分析
设这两堆石子分别有(A,B)个并且AB。我们先来看一下先手必败的局势。
(0,0) 先手必败很明显他没得取了。(1,2) 先手必败。具体分析一下先手有以下几种取法 取第一堆的1个后手取走第二堆的2个获胜。 从第一堆第二堆各取1个后手取走第二堆剩下的1个获胜。 取第二堆的1个后手从第一堆第二堆各取1个获胜。 取第二堆的2个后手取走第一堆的1和获胜。 综上所述先手必败。(3,5) 先手必败。 首先可以明确的一点是先手不能把任意一堆取完如果取完显然必败。 先讨论先手从第一堆中取的情况 先手可以从第一堆中取1个后手从第二堆中取4个转化为(1,2),先手必败。 先手可以从第一堆中取2个后手从第二堆中取3个转化为(1,2),先手必败。 再讨论先手从第二堆中取的情况 先手可以从第二堆中取1个后手从两堆中各取2个转化为(1,2)先手必败。 先手可以从第二堆中取2个后手从两堆中各取3个转化为(0,0)先手必败。 先手可以从第二堆中取3个后手从两堆中各取1个转化为(1,2)先手必败。 先手可以从第二堆中取4个后手从第一堆中取2个转化为(1,2)先手必败。 接着讨论先手从两堆中取的情况 先手可以从两堆中各取1个转化为(2,4)此时情况较多 后手足够聪明他从第二堆中取了1个转化为(2,3)先手也足够聪明他为了不直接输掉从第一堆中取了1个(其他取法直接输掉了)转化为(1,3)此时后手从第二堆中取1个转化为(1,2)先手必败。 先手可以从两堆中各取2个后手从第二堆中取一个转化为(1,2)先手必败。 综上所述先手必败。其他的先手必败局势 (4,7),(6,10),(8,13),(9,15),(11,18).我们将先手必败局势的集合称为奇异局势。
奇异局势的性质
任何自然数都包含在一个且仅有一个奇异局势中。 任意操作都可将奇异局势变为非奇异局势。 采用适当的方法可以将非奇异局势变为奇异局势。
Betty定理
我们可以发现将所有奇异局势按照第一堆的石子的数目从小到大排列每个奇异局势的差值是自然数列。 进一步观察发现对于一个奇异局势(A,B), A 下取整[ (B-A) * 1.618 ]更准确的说1.618 (sqrt(5) 1) / 2.
为什么会是这样的 具体的证明涉及到Betty的定理有兴趣的读者可以百度这里不再赘述。
常见的几类问题
给出一个局面判断先手输赢。 检查是否是奇异局势。给出局面判断先手输赢若赢求出首步取法。 由于差值是固定的根据差值计算。
练习
POJ 1067HDU 152751NOD 1072HDU 2177NYOJ 161
五、尼姆博弈
基本描述
有三堆石子 每堆有若干个两个人轮流从某一堆中任取石子每次至少取一个多者不限最后取完者获胜。
分析
用(A,B,C)来表示某一特定局势同时规定ABC。奇异局势表示先手必败。
显然(0,0,0)是奇异局势。(0,n,n)是奇异局势当先手拿走s个石子时我们对应拿走s个石子最终转化为(0,0,0)。(1,2,3)也是奇异局势无论先手如何取我们都可以转化为(0,n,n)的局势。
对于一个奇异局势(A,B,C),我们可以发现A(XOR)B(XOR)C 0。 下面一条需要的前置技能 设有数字a,ba(XOR)b(XOR)(a(XOR)b) (a(XOR)a)(XOR)(b(XOR)b) 0 对于一个非奇异局势(A,B,C),我们只需要将C转化为(A(XOR)B)即可而将C转化为(A(XOR)B)的操作为C C-(A(XOR)B)即可。
注
异或在C语言中的符号为^。对于此情景来说可以推广到N堆石子奇异局势的条件为A1(XOR)A2(XOR)A3(XOR)……AN(XOR) 0。A(XOR)B(XOR)B A可推广到N个变量A1(XOR)A2(XOR)A3(XOR)……(XOR)AN(XOR)AN(XOR)AN-1(XOR)……(XOR)A3(XOR)A2 A1;
练习
HDU 1850
六、SG函数
基本描述
SG函数为计算博弈状态的函数当SG[X] 0时说明先手必败。 为了求解SG函数首先定义mex(minimal excludant)运算这是施加于一个集合的运算表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}3、mex{2,3,5}0、mex{}0。 对于任意状态 x 定义 SG(x) mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)那么SG(x) mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集所以SG函数的终态为 SG(x) 0,当且仅当 x 为必败点P时。
说起来很抽象举一个具体的例子来说明一下。
实例取石子游戏
游戏规则
有1堆n个的石子每次只能取{ 1, 3, 4 }个石子先取完石子者胜利那么各个数的SG值为多少
SG分析
SG[0] 0(显然没有石子可取时必败) f[] {1,3,4}(表示每次取有3中方案取1个取3个取4个)
当石子x 1时可以取走1-f{1}个石子,SG[1] mex(SG[1-1]) mex(0) 1; 当石子x 2时可以取走2-f{1}个石子,SG[2] mex(SG[2-1]) mex(1) 0; 当石子x 3时可以取走3-f{1,3}个石子SG[3] mex(SG[3-1],SG[3-3]) mex(0,0) 1; 当石子x 4时可以取走4-f{1,3,4}个石子SG[4] mex(SG[4-1],SG[4-3],SG[4-4]) mex(1,1,0) 2;
以此类推…
我们可以打出SG函数的表根据表来判断是先手必胜还是先手必败。
练习
HDU 1847HDU 1848
七、更多的练习
POJ 2234HDU 4388POJ 2975HDU 1367POJ 2505ZOJ 3057POJ 2484POJ 2425POJ 2960POJ 1740POJ 1704POJ 2068POJ 3480POJ 2348HDU 2645POJ 3710POJ 3533
