LeetCode 292. Nim游戏
题目形容:
你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 – 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人,每一步都是最优解。 编写一个函数,来判断你能否可以在给定石头数量的情况下博得游戏。
示例:
输入: 4输出: false 解释: 假如堆中有 4 块石头,那么你永远不会博得比赛; 由于无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。
思路
简单题,巴什博弈。
显然,假如n=m+1,那么因为一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因而我们发现了如何取胜的法则:假如n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,假如后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者一定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。
对于巴什博弈,那么我们规定,假如最后取光者输,那么又会如何呢?
(n-1)%(m+1)==0则后手胜利
先手会重新决定策略,所以不是简单的相反行的
JAVA SOLUTION
class Solution { public boolean canWinNim(int n) { return n % 4 == 0 ? false : true; }}扩展
威佐夫博奕
威佐夫博弈(Wythoff’s game):有两堆各若干个物品,两个人轮流从任一堆取至少一个或者同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
两个人假如都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜。
那么任给一个局势, (a,b),怎么判断它是不是奇异局势呢?我们有如下公式:
尼姆博奕
指的是这样的一个博弈游戏,目前有任意堆石子,每堆石子个数也是任意的,双方轮流从中取出石子,规则如下:
1)每一步应取走至少一枚石子;每一步只能从某一堆中取走部分或者一律石子;
2)假如谁取到最后一枚石子就胜。
判断当前局势能否为必胜(必败)局势:
把所有堆的石子数目用二进制数表示出来,当一律这些数按位异或者结果为0时当前局面为必败局面,否则为必胜局面;
#include<iostream> using namespace std; int temp[ 20 ]; //火柴的堆数 int main() { int i, n, min; while( cin >> n ) { for( i = 0; i < n; i++ ) cin >> temp[ i ]; //第i个火柴堆的数量 min = temp[ 0 ]; for( i = 1; i < n ; i++ ) min = min^temp[ i ]; //按位异或者 if( min == 0 ) cout << "Lose" << endl; //输 else cout << "Win" << endl; //赢 } return 0; } 斐波那契博弈
有一堆个数为n的石子,游戏双方轮流取石子,满足:
1)先手不能在第一次把所有的石子取完;
2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。
商定取走最后一个石子的人为赢家,求必败态。
这个游戏叫做斐波那契博弈,一定和斐波那契数列:有密切的关系。假如实验一番之后,可以猜测:先手胜当且仅当n不是斐波那契数。换句话说,必败态构成斐波那契数列。
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode 292. Nim游戏