网站制作过程合理的步骤是,招标网站免费平台,天猫网站平面广告,做药材有什么好的网站博弈论总结
什么是博弈论#xff1a;
多人进行博弈#xff0c;假设每个人都采取最优策略#xff0c;一定有一个人胜出#xff0c;在知道初态及规则的情况下#xff0c;求解出
何人胜出的一类问题的理论及方法。
博弈论的一些性质
P点#xff1a;必败点#xff0c;N…博弈论总结
什么是博弈论
多人进行博弈假设每个人都采取最优策略一定有一个人胜出在知道初态及规则的情况下求解出
何人胜出的一类问题的理论及方法。
博弈论的一些性质
P点必败点N点必胜点
1无法进行任何移动的局面也就是terminal position是P-position
2可以移动到P-position的局面是N-position
3所有移动都导致N-position的局面是P-position。
巴什博奕
介绍只有一堆n个物品两个人轮流从中取物规定每次最少取一个最多取m个最后取光者为
胜。
必定可以写成该式子 nk*(m1)r
结论若r0则先手必败否则先手必胜。
if(n % (m 1) 0)cout后手必胜endl;elsecout先手必胜endl;
威佐夫博弈
介绍有两堆各若干的物品两人轮流从其中一堆取至少一件物品至多不限或从两堆中同时取相同
件物品规定最后取完者胜利。
结论若两堆物品的初始值为xy且xy则另zy-x
记wint[sqrt51/2*z ]中间为熟知的黄金分割比
若wx则先手必败否则先手必胜。
if(x y)swap(x, y);int c floor((y - x) * (sqrt(5) 1) / 2);if(c x)cout0endl;elsecout1endl;
尼姆博奕
介绍有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取
光者得胜.
结论n堆石子全部做异或运算结果为0则为必败结果
SG函数
首先定义mex(minimal excludant)运算这是施加于一个集合的运算表示最小的不属于这个集合的非
负整数。例如mex{0,1,2,4}3、mex{2,3,5}0、mex{}0。
对于任意状态 x 定义 SG(x) mex(F)其中F 是 x 后继状态的SG函数值的集合就是上述mex中的数
值。最后返回值也就是SG(X)为0为必败点不为零必胜点。
进一步解释一下F就是题意中给出的可以移动的次数。举个例子来说一堆石子每次只能拿13
57个那么S数组就是1357。
假如说是在一个游戏中有多个石子堆该怎么办了。我们只需要把对每个石子堆进行sg函数的调用将得
到的所有的值进行异或。得出来的结果为0则该情形为必败态。否则为必胜态。
int sg[MAXN];
int f[MAXM]; //可以取走的石子个数
bool Hash[MAXN];void getSG(int m)
{memset(sg, 0, sizeof(sg));for (int i 1; i MAXN; i) {//枚举石子的个数memset(Hash, false, sizeof(Hash));for (int j 0; j m f[j] i; j)Hash[sg[i-f[j]]] true;//枚举每次拿走的个数并标记for (int j 0; j MAXN; j) {if (!Hash[j]) {sg[i] j; //找到这个F[](该状态可以达到的状态)中不存在的最小的数break;}}}
} //例题hdu1847
int main()
{int n, num 1;for (int i 0; i MAXM; num 1, i)f[i] num;//这里的F数组就是可以移动的步数每次都是2的幂次getSG(MAXM);while (cin n){if (sg[n])cout Kiki endl;elsecout Cici endl;} return 0;
}
