game theory博弈论全文翻译_john nash博弈论

233 5 111

John
Brother

这一题有点类似于NIM游戏，当符合一定条件的时候，先手可必胜。这里用到了一个规律。把每一堆的数目进行异或运算（每一堆的数目都是1除外），最后的结果有两种，为0或不为0，若为0则各堆的二进制位相加不进位以后所得到的数的各位数一定是一个偶数。我们称结果为0的情况为平衡状态，如果刚开始局面是一个不平衡状态，即各堆的各位二进制数的和不全为偶数，可判定为先手的必胜残局。 举个例子：下面应用此获胜策略来考虑4-堆的Nim取子游戏。其中各堆的大小分别为7，9，12，15枚硬币。用二进制表示各数分别为：0111，1001，1100和1111。于是可得到如下一表：大小为7的堆  0 1 1 1 大小为9的堆  1 0 0 1 大小为12的堆 1 1 0 0 大小为15的堆 1 1 1 1  由Nim取子游戏的平衡条件可知，此游戏是一个非平衡状态的取子游戏，因此，游戏人I在按获胜策略进行取子游戏下将一定能够取得最终的胜利。具体做法有多种，游戏人I可以从大小为12的堆中取走11枚硬币，使得游戏达到平衡（如下表），  大小为7的堆  0 1 1 1 大小为9的堆  1 0 0 1 大小为12的堆 0 0 0 1 大小为15的堆 1 1 1 1  之后，无论游戏人II如何取子，游戏人I在取子后仍使得游戏达到平衡。同样的道理，游戏人I也可以选择大小为9的堆并取走5枚硬币而剩下4枚，或者，游戏人I从大小为15的堆中取走13枚而留下2枚。归根结底，Nim取子游戏的关键在于游戏开始时游戏处于何种状态（平衡或非平衡）和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。 做这题很容易被英文描述给弄晕，说白了就是这你懂不懂这个游戏，可是文章却描述的很烂不知道在说什么，做了好些英文题感觉这种题目挺多的，这种题目指定要靠你什么知识定理什么的，要是之前做过，那么就会容易理解题意，那么完成这题也就是不需要理会它题目是怎么描述的了…… #include<iostream>#include<stdio.h>using namespace std;int main(){	int T,N,a[48],i,flag,sum;	scanf("%d",&T);	while(T--)	{		sum=0;		flag=0;		memset(a,0,sizeof(a));		scanf("%d",&N);		for(i=1;i<=N;i++)		{			scanf("%d",&a[i]);			sum+=a[i];		}		if(sum==N)//全是1的时候分开考虑。		{			if(sum%2==0)				cout<<"John"<<endl;			else				cout<<"Brother"<<endl;		}		else		{			for(i=1;i<=N;i++)				flag=flag^a[i];			if(flag==0)//分为等于零和不等于零两种				cout<<"Brother"<<endl;			else				cout<<"John"<<endl;		}	}	return 0;}  下面补充下：  §

 下面再举一例子：来自北大oj，http://acm.pku.edu.cn/JudgeOnline/problem?id=1704 
Description 
 Georgia and Bob decide to play a self-invented game. They draw a row of  grids on paper, number the grids from left to right by 1, 2, 3, ..., and place N 
 chessmen on different grids, as shown in the following figure for example: 
 
 
 
Georgia and Bob move the chessmen in turn. Every time a player will choose a chessman, and move it to the left without going over any other chessmen or across the left edge. The player can freely choose number of steps the chessman moves, with the constraint that the chessman must be moved at least ONE step and one grid can at most contains ONE single chessman. The player who cannot make a move loses the game. 
 
Georgia always plays first since "Lady first". Suppose that Georgia and Bob both do their best in the game, i.e., if one of them knows a way to win the game, he or she will be able to carry it out. 
 
Given the initial positions of the n chessmen, can you predict who will finally win the game? 
 
Input 
 The first line of the input contains a single integer T (1 <= T <= 20), the number of test  cases. Then T cases follow. Each test case contains two lines. The first line consists  of one integer N (1 <= N <= 1000), indicating the number of chessmen. The second line  contains N different integers P1, P2 ... Pn (1 <= Pi <= 10000), which are the initial  positions of the n chessmen.Output 
 For each test case, prints a single line, "Georgia will win",  if Georgia will win the game; "Bob will win", if Bob will win the game;  otherwise 'Not sure'.Sample Input 
2
3
1 2 3
8
1 5 6 7 9 12 14 17

Sample Output
Bob will win
Georgia will win

这题的思想就是把它转换成博弈思想，和上面的吃糖那题类似。这种就是石头有多堆的情况，而下面
讲的取石游戏是一堆的情况。这种类型的题目运用比较广，叫 尼姆博弈……
 

 § 这题我们还是可以通过转化成尼姆博弈来求解。  § 通过两两配对做成堆  § 如何分堆  § 如果偶数个（1.2）,（3，4）,……（n-1，n）；  
 § 
  
 
 § 设各堆中的间隔为a1，a2，a3……an；  § 则s=a1^a2&^a3…….^an  § 判断s是否为0
奇数时则需在左边添加一个与第一个配对,之后一样两两配对 
  

   巴什博弈：两人取石头游戏   
 石头总数为n，每人每次最少取1个，最多取m个，最后取完者胜。 
 

 
 § 
   当n%（m+1）=s时不等于0. 我第一次取s个。 从现在开始，我只要每次拿的个数与前面另一个人拿的个数和等于m+1， 
          其实我们只需要判断n%（m+1）是否等于0即可知道谁胜谁负。            
 § 到最后另一个拿的时候肯定是剩t（t<m）个给我，傻瓜也知道我赢了，嘿嘿！ 
          用个例子来说，假设n=k*（m+1）+s，那我先把那个S个拿掉，然后让另外一个人拿，           
如： 
§假设有66个石头，我们每次最多拿6个，则mod（66，7）=3 

 §
 第一次：3    1          62  §
 第二次：6    2          54  §
 第三次：5    4          45  §
 第四次：3    2          40  §
 第五次：5    6          29  §
 第六次：1    5          23  §
 第七次：2    6          15  §
 第八次：1    5           9  §
 第九次：2    6           1  §
 第十次：1                 0 

 §
 当然我也有输的情况，那就是n=k*（m+1）=0时，而另外一个人每次都拿（m+1）减我拿的个数   //测试数据里应该没有间隔全为1的情况，或者说这个特殊已经被包含在内了……
#include<iostream>
#include<stdio.h>
using namespace std;
int a[1000],b[1000];
int main()
{
int i,j,n,T,flag;
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)//对输入的数进行冒泡排序
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
flag=a[j];
a[j]=a[j+1];
a[j+1]=flag;
}
if(i%2==0)//偶数个时
{
j=0;flag=0;
for(i=1;i<n;i=i+2,j++)
b[j]=a[i]-a[i-1]-1;
for(i=0;i<j;i++)
flag=b[i]^flag;
}
else//奇数个时
{
j=1;flag=0;
b[0]=a[0]-1;
for(i=2;i<n;i+=2,j++)
b[j]=a[i]-a[i-1]-1;
for(i=0;i<j;i++)
flag=b[i]^flag;
}	
if(flag==0)
cout<<"Bob will win"<<endl;
else
cout<<"Georgia will win"<<endl;	
}
}
return 0;
}