博弈论（巴什博奕/尼姆博奕/威佐夫博奕）详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了博弈论（巴什博奕/尼姆博奕/威佐夫博奕）详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

博弈论，是经济学的一个分支，主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略

通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略

对于算法竞赛中的博弈问题，一般具有以下特征：

博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利
博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负
公平博弈。即两人进行决策所遵循的规则相同

（一）巴什博弈

术语:正经人称(m+1)的局面为奇异局势

1堆n个石子每次最多取m个、最少取1个--------（m+1的局势）

情形一：如果n=m+1，那么由于一次最多只能取m个，所以无论先者拿走多少个，后者都能够一次拿走剩余的物品，后者必胜

情形二：如果n=(m+1)*r+s，(r为任意自然数且s≤m)，那么先者要拿走s个物品，如果后者拿走k(1≤k≤m)个，那么先者再拿走m+1-k个，结果剩下(m+1)(r-1)个，以后保持这样的取法，那么先者必胜

情形三：如果n=(m+1)*r，先者拿走k(1≤k≤m)个，那么后者再拿走m+1-k个，结果剩下(m+1)(r-1)个，以后保持这样的取法，则后者必胜

总之，只要给对手留下（m+1）的倍数，就能获胜。（m+1）的倍数则后者比赛，反之先者必胜

变式

两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜（等价于从一堆100个石子中取石子，最后取完的胜）

例题：POJ2368 -- Buttons

解法一：数据为10^8，会TLE

#include<cstdio>
#include<iostream>
#define int long long 
using namespace std;

signed main(){
	int n;
	cin>>n;
	for(int i=2;i<n;i++){
		if(n%(i+1)==0){
			cout<<i;
			return 0;
		}
	}
	cout<<0;
	return 0;
}

解法二：遍历一遍n的所有因数并存起来，再输出最小大于等于3的因数减1

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

const int N=10005;
int a[N];
signed main(){
	int n,t=0;
	cin>>n;
	for(int i=1;i*i<=n;i++){
		if(n%i==0&&i*i!=n){
			a[++t]=i;
			a[++t]=n/i;
		}else if(n%i==0&&i*i==n){
			a[++t]=i;
		}
	}
	sort(a+1,a+t+1);
	for(int i=1;i<=t;i++){
		if(a[i]>=3){
			cout<<a[i]-1;
			break;
		}
	}	
	return 0;
}

（二）尼姆博弈

术语:正经人称(m,m)的局面为奇异局势

有n堆石子，每堆石子的数量是a1,a2,a3……，二个人依次从这些石子堆中的一个拿取任意的石子，至少一个，最后一个拿光石子的人胜利

情形一：n=1，先手全拿，先手必胜

情形二：n=2，有两种情况，一种可能相同，一种情况一堆比另一堆少或多

（1）(m,m) 按照“有一学一，照猫画猫”法，后手必胜

（2）(m,M)先手先从多的一堆中拿出(M-m)个，此时后手面对(m,m)的局面，先手必胜

情形三：n=3，(m,m,M)先手必胜，先手可以先拿M,之后变成了(m,m,0)的局面，是不是很熟悉~

(a1,a2,a3)的话，举个例子(1,2,3),先手取完之后可能的局面为(0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0)都是之前讲过的

异或为0，先手必输，后手必胜

(三)威佐夫博弈

有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜

先手必输局势的规律（奇异局势）无论先手怎么取，后手必胜

第一种（0，0）

第二种（1，2）

第三种（3，5）

第四种 (4，7）

第五种（6，10）

第六种 (8，13）

第七种 (9，15）

第八种 (11，18）

第n种（a，b）

他们的差值是递增的，分别是0,1,2,3,4,5,6,7......n

还有一个规律(正常人都发现不了):a=(b-a)*1.618向下取整！！！！！

a=int(b-a)*1.618

注：这里的int是强制类型转换，注意这不是简单的四舍五入，假如后面的值是3.9，转换以后得到的不是4而是3，也就是说强制int类型转换得到的是不大于这个数值的最大整数。

有些题目要求精度较高，我们可以用下述式子来表示这个值:

1.618=(sqrt(5.0)+1)/2;

头文件：include<math.h>

例题：POJ1067 -- 取石子游戏

#include<iostream>
#include<cmath>
#define int long long
using namespace std;

signed main(){
	double a,b;
	while(cin>>a>>b){
		if(a>b){
			swap(a,b);
		}
		double x=(int)((b-a)*((sqrt(5.0)+1)/2));
		if(a==x){
			cout<<0<<endl;
		}else{
			cout<<1<<endl;
		}
	}
	return 0;
}

文章来源地址https://www.toymoban.com/news/detail-603073.html

到了这里，关于博弈论（巴什博奕/尼姆博奕/威佐夫博奕）详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！