博弈问题的一些想法（菜鸟，不喜勿喷。。。）

本文主要是介绍博弈问题的一些想法（菜鸟，不喜勿喷。。。），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于固定每次取值的博弈题目如bash和nim(每次取ai个可以先存进数组)，可以使用sg表来打表找规律。

#include<cstring>
#include<cstdio>
const int maxn=45;
bool vis[maxn];
int sg[maxn];
int a[5]={1,2,4,8,16};
void sgs()
{for(int i=0;i<maxn;i++){memset(vis,false,sizeof(vis));for(int j=0;j<3;j++){if(i>=a[j])vis[sg[i-a[j]]]=true;}for(int j=0;;j++){if(!vis[j]){sg[i]=j;break;}}printf("%d %d\n",i,sg[i]);}
}
int main()
{sgs();
}///a[]存取每次可取的值

对于像斐波那契博弈，威佐夫博弈等每次可取1到(n-1)个的题目，由于太菜不能写出SG表，所以建议自行找规律。。。。（根据N,P的关系）

如斐波那契博弈（51nod bash游戏v4)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=50;
long long f[50];
int main()
{f[1]=1,f[2]=2;for(int i=3;i<maxn;i++)f[i]=f[i-1]+f[i-2];///先通过递归把所有斐波那契数存入数组int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);int sign=1;for(int i=1;i<maxn;i++){if(f[i]>n)break;if(f[i]==n){sign=0;break;}}if(sign)printf("A\n");elseprintf("B\n");}return 0;
}

威佐夫博弈

#include<cstdio>
#include<cmath>
using namespace std;
//double ans=0.3;
int main()
{int casenum;scanf("%d",&casenum);for(int i=1;i<=casenum;i++){int n,k;scanf("%d%d",&n,&k);if(n>k){int t=n;n=k;k=t;}int t=k-n;//printf("r:%d\n",(int)(t*(1+sqrt(5))/2));if(n==(int)(t*(1+sqrt(5))/2))printf("B\n");elseprintf("A\n");}
}

gdu1186(找规律）

#include<cstdio>
using namespace std;
long long n;
int main()
{while(scanf("%d",&n)!=EOF&&n){printf("%s\n",(n&(n+1))==0? "Bob":"Alice");}return 0;}

这篇关于博弈问题的一些想法（菜鸟，不喜勿喷。。。）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---