由于博弈论算是一种比较玄学的东西，证明和思想也不是很好理解，这里只归纳几种常见博弈论的结论和相关题目。
巴什博奕（Bash Game）
只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为胜。
必定可以写成该式子 n=k*(m+1)+r；
结论：若r=0，则先手必败，否则先手必胜。
|
1 2 3 4 5 6 7 8 9 10 |
#include <iostream> using namespace std; int main() { int n,m; while(cin>>n>>m) if(n%(m+1)==0) cout<<"后手必胜"<<endl; else cout<<"先手必胜"<<endl; return 0; } |
例题：hdu 1846 2149
hdu 2147(NP图，列和行有一个为偶数则先手赢）
AC代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include<iostream> using namespace std; int main() { int n,m; while(cin>>m>>n&&m&&n) { if(n%2==0||m%2==0) cout<<"Wonderful!"<<endl; else cout<<"What a pity!"<<endl; } return 0; } |
斐波那契博弈：
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。
结论是：当n是斐波那契数则先手必败，当n不是斐波那契数则先手必胜（n为物品总数）
例题：hdu 2516
AC代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include<iostream> using namespace std; int main() { int fib[50]; fib[0]=2,fib[1]=3; for(int i=2;i<=50;i++) fib[i]=fib[i-1]+fib[i-2]; int n; int flag; while(cin>>n&&n) { flag=0; for(int i=0;i<=50;i++) { if(fib[i]==n) flag=1; if(fib[i]>n) break;//及时跳出 } if(flag) cout<<"Second win"<<endl; else cout<<"First win"<<endl; } return 0; } |
威佐夫博弈（Wythoff Game）
有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
结论：若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5）+1）/2）*z ]；（中间为熟知的黄金分割比）
若w=x，则先手必败，否则先手必胜。
例题：Poj 1067
AC代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include<iostream> #include<math.h> using namespace std; int main() { int x,y; while(cin>>x>>y) { if(x>y) swap(x,y); int c=floor((y-x)*(sqrt(5)+1)/2); if(c==x) cout<<0<<endl; else cout<<1<<endl; } return 0; } |
尼姆博奕(Nimm Game)
有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜.
结论：n堆石子全部做异或运算的结果为0则为必败结果
例题：hdu 1850
AC代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<iostream> using namespace std; int main() { int m; int a[105]; int ans,cnt; while(cin>>m&&m) { ans=0,cnt=0; for(int i=0;i<m;i++) { cin>>a[i]; ans^=a[i]; } if(ans==0) cout<<0<<endl; else{ int k; for(int i=0;i<m;i++) { k=ans^a[i]; if(k<a[i]) //当k小于a[i]时，有a[i]-x=k成立， //即拿走x个后， k^(a[i]-x)=k^k=0,即给了对手必败态 cnt++; } cout<<cnt<<endl; } } return 0; } |
Nim Staircase博奕:
这个问题是尼姆博弈的拓展：游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时
可以将楼梯j(1<=j<=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上（0号）的人获胜。
结论：将奇数楼层的状态异或，和为0则先手必败，否则先手必胜。
Post a new comment