广西网站建设证件查询,网站登记备案 个人,网站开发团队工作总结,网站开发成本会计分录常见的博弈论有巴什博弈#xff0c;威佐夫博弈#xff0c;尼姆博弈#xff0c;斐波那契博弈等等#xff0c;今天暂时讲几个 文章目录一.巴什博弈证明#xff1a;代码二.威佐夫博奕结论#xff1a;代码#xff1a;三.环形博弈结论证明代码#xff1a;一.巴什博弈
巴什博…常见的博弈论有巴什博弈威佐夫博弈尼姆博弈斐波那契博弈等等今天暂时讲几个
文章目录一.巴什博弈证明代码二.威佐夫博奕结论代码三.环形博弈结论证明代码一.巴什博弈
巴什博奕只有一堆n个物品两个人轮流从中取物规定每次最少取一个最多取m个最后取光者为胜。
证明
显然如果nm1那么由于一次最多只能取m个所以无论先取者拿走多少个后取者都能够一次拿走剩余的物品后者取胜。 因此我们可以推算出如果nm1*rsr为任意自然数s≤m),那么先取者要拿走s个物品如果后取者拿走k≤m)个那么先取者再拿走m1-k个结果剩下m1r-1个以后保持这样的取法那么先取者肯定获胜。 总之要保持给对手留下m1的倍数就能最后获胜。 也就是若n%(m10则先手必输 变形 如果条件不变改成最后取光的人失败 结论若n-1%m1 0 则后手胜利
代码 if(n%(m1)0) cout后手必胜endl; else cout先手必胜endl; 二.威佐夫博奕
有两堆各若干个物品两个人轮流从某一堆或同时从两堆中取同样多的物品规定每次至少取一个多者不限最后取光者得胜。 A无论怎么取B总是可以 针对着来
结论
奇异局势下先手必败非奇异局势下先手必胜。 ab表示两堆物品的数量也称之为局势 奇异局势就是当A面对这个局势时就已经输了。你也可以理解成必输局面。比如0,0或者1,23,5等等 那怎么知道一个局势是否为奇异局势 a与b满足这个条件 ak [k1√5/2]bk ak k k012…,n 方括号表示取整函数akbk
整合一下 ak [ ( bk - ak ) 1 √5 / 2 ]
证明略其实我也不是很明白
代码
if(ab) swap(a,b); ansfloor((b-a)*(1sqrt(5.0))/2.0); if(ansa) cout后手必胜endl; else cout先手必胜endl; 三.环形博弈
n个石子围成一圈每次只能取相邻的k1kn个石子取完者胜。 今天一个同学问我我才想起来这个。。。
结论
如果nk,先手必赢也就是如果先手能一次拿完就输 当k等于1时n为奇先手胜n为偶后手胜。
证明
因为是环形假如说A第一次没去完那B只要取与A相对的石头也就是A拿完后还剩奇数个石头B就拿与A对应位置的一个石头如果剩偶数个就拿对应位置的两个 这样就把一个环拆分成两个链且每个链都是相等的 用sg定理sg[x] ^ sg[x] 0 这就是必败态所以先手A输了 当k1时这就不用我讲了吧。。。
代码
bool circle_game(int n,int k){if(kn||k1(n1)) return 1;return 0;
}例题 HDU - 3951
