博弈问题(巴什博弈 威佐夫博弈 尼姆博弈 斐波拉契博弈)结论
发布日期:2021-06-21 03:12:36 浏览次数:6 分类:技术文章

本文共 1273 字,大约阅读时间需要 4 分钟。

巴什博弈

有一堆n个石子从里面取,一次从里面取1~m个,最后取完者获胜。

结论:如果n%(m+1)==0 先手必败   n%(m+1)!=0为先手必胜。

HDU 4764

#include<iostream>

#include<algorithm>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
if((n-1)%(m+1)!=0)
cout<<"Tang"<<endl;
else
cout<<"Jiang"<<endl;
}
 } 

威佐夫博弈

有两堆石子,每次要么从一堆中取任意个,最少为1;要么从两堆中取出相同个,最后取完者获胜。

结论:用最大的一堆减去最小的一堆的值*(1+sqrt(5)/2) 如果等于较小的那堆个数,先手必败 否则先手必胜。

尼姆博弈

任意堆石子,每次从中取任意个石子,最少为一个,最后取完者获胜。

结论:将所有堆的石子异或起来,如果等于0先手必败,否则先手必胜。

HDU2176

#include<cstdio>

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,a[10005];
while(cin>>n)
{
int k,tmp=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
tmp^=a[i];}
if(tmp==0)
cout<<"No"<<endl;
else
{
cout<<"Yes"<<endl;
for(int i=0;i<n;i++)
{
int t=tmp^a[i];
   if(t<a[i])
{
cout<<a[i]<<" "<<t<<endl;
}
   }
}
}
return 0;

 } 

斐波拉契博弈

一堆物品轮流取,每次最少一个最多无上限,后一次最多为前一次的两倍,最少一个,最后取完者胜利。

结论:当n不是斐波拉契数,先取者胜利,反之后者。

HDU2516

#include <iostream>  

#include <string.h>  
#include <stdio.h>  
using namespace std;  
const int N = 55;    
int f[N];   
void Init()  
{  
    f[0] = f[1] = 1;  
    for(int i=2;i<N;i++)  
        f[i] = f[i-1] + f[i-2];  
}    
int main()  
{  
    Init();  
    int n;  
    while(cin>>n)  
    {  
        if(n == 0) break;  
        bool flag = 0;  
        for(int i=0;i<N;i++)  
        {  
            if(f[i] == n)  
            {  
                flag = 1;  
                break;  
            }  
        }  
        if(flag) puts("Second win");  
        else     puts("First win");  
    }  
    return 0;  

转载地址:https://blog.csdn.net/k_koris/article/details/80214487 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:pat1002
下一篇:Various Tree

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年04月16日 21时48分17秒