博弈论威佐夫博弈

关键词：

威佐夫博弈

    威佐夫博弈：有两堆石子，每次一个人可以两堆同时取相同数量的石子，也可以只取其中一堆的石子，最后谁取完谁获胜，请问先手还是后手胜？

      对于学过一些博弈论基础的来说，我们需要找到那些能让先手必输的局势，那么由这些局势在规定范围内拓展的局势也是先手必输的局势(但在这里双方自由选取，不适用)。我们可以得出一些局势使A必输：(0,0) (1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18)

(12,20)……我们称这些局势为奇异局势

$不难发现，如果我们标记(0,0)为第0项的话，那么ak是前面还没有出现过的最小数字，bk=ak+k$

      对于奇异局势来说，有以下性质：

1. 任何自然数都一定包含在一个奇异局势中。
2. 任意操作都可以将奇异局势转变为非奇异局势。
3. 可以将非奇异局势转变为奇异局势。

     那么，当我们面对下列情况时，可以这样应对：

     当a=b时，两堆同时取a

     当a=ak,b>bk时，2堆取b-bk个

     当a=ak,b<bk时，2堆取a-a(b-a)个

     当a>ak,b=bk(ak+k)时，1堆取a-ak个

     当a<ak,b=bk(ak+k)时，从2堆中拿走若干变成奇异局势

    如何判断一个数对是不是奇异局势呢？

    当a=(下取整)k*(1+√5)/2，b=ak+k时(k为任意非负整数)局势为奇异局势

4 5

1

3 8

1

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;
const int INF = 9999999;
#define LL long long

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;
	return x*f;
}
int N,M; 
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	N=read(),M=read();
	double t=(1.0+sqrt(5))/2.0;
	if(N>M) swap(N,M);
	int tmp=M-N;
	if(N==(int)(t*tmp)) printf("0");
	else printf("1");
	return 0;
}

博弈论-威佐夫博弈

理论分析问题：首先有两堆石子，博弈双方每次可以取一堆石子中的任意个，不能不取，或者取两堆石子中的相同个。先取完者赢。分析：首先我们根据条件来分析博弈中的奇异局势第一个（0，0），先手输，当游戏某一方面对... 查看详情

巴仕博弈+威佐夫博弈(代码片段)

...1到m个石子，不能拿的人为败者，问谁会胜利巴什博奕是博弈论问题中基础的问题它是最简单的一种情形对应一种状态的博弈博弈分析如果有m+1个石子，那么先手必定无法取完全部，但后手可以取完剩下的部分，使得先手没有石... 查看详情

poj1067威佐夫博弈

链接：http://poj.org/problem?id=1067题意：威佐夫博弈（WythoffGame）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。题解：威佐夫博弈（WythoffGame）：... 查看详情

博弈问题（巴什博弈威佐夫博弈尼姆博弈斐波拉契博弈）结论

巴什博弈有一堆n个石子从里面取，一次从里面取1~m个，最后取完者获胜。结论：如果n%（m+1）==0先手必败 n%（m+1）！=0为先手必胜。HDU4764#include<iostream>#include<algorithm>usingnamespacestd;intmain() intn,m; while(cin>>n>>m) 查看详情

85-取石子-威佐夫博弈

 http://poj.org/problem?id=1067　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　取石子游戏TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 45409 Accepted: 15533Description有两 查看详情

博弈论入门之威佐夫博弈(代码片段)

更好的阅读体验点这里威佐夫博弈威佐夫博弈是一类经典的博弈问题有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取得人输，分析谁会获得... 查看详情

基础博弈——威佐夫与尼姆不得不说的那些事(代码片段)

STEP1：首先了解规则与概念　　威佐夫博弈（Wythoff‘sgame）：有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。　　尼姆博弈（NimmGame）... 查看详情

51nod1185威佐夫游戏v2(威佐夫博弈)

1185 威佐夫游戏 V2 基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注有2堆石子。AB两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不... 查看详情

威佐夫博弈

同样威佐夫也有一个经典的例题：1.有两堆数量分别为n,m个石子的石子堆；2.两个人轮流取石子，可以在一堆石子中取任意个，或者，在两堆石子中每堆石子取相同数目的石子； 输出：如果先手赢，输出1，否则输出0。 题... 查看详情

威佐夫博弈

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。ab两堆a>=b奇异局势(a-b)*(1+sqrt(5))/2.0)==a黄金分割数（1+√5）/2=1.618...1#include<iostream>2#include<c... 查看详情

博弈论（巴什博奕，威佐夫博弈，尼姆博弈，斐波那契博弈）

一、巴什博弈（BashGame）有n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩... 查看详情

poj1067取石子游戏威佐夫博弈博弈论

http://poj.org/problem?id=1067有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石... 查看详情

博弈论——两人取子游戏与威佐夫博弈，隐藏在背后的黄金分割(代码片段)

...个关注今天是算法和数据结构专题第25篇文章，我们继续博弈论专题。在上一篇文章当中我们了解了最简单的巴什博奕，今天我们来看看另一个经典的博弈模型——威佐夫博弈。博弈论和机器学习有些类似，数学家们针对场景进... 查看详情

威佐夫博弈(代码片段)

博弈规则：有两堆各若干个物品，两个人轮流从某一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。a堆和b堆的个数用（a，b）表示奇异局势：面对的时候，就是输家，比如（0... 查看详情

博弈论（巴什博奕，威佐夫博弈，尼姆博弈，斐波那契博弈）

一.巴什博奕（BashGame）：A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。其实如果知道原理，这游戏一点运气成分都没有，只和先手后... 查看详情

hdu1527取石子游戏(威佐夫博弈)

TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):8509    AcceptedSubmission(s):4833ProblemDescription有两堆石子，数量任意，可以不 查看详情

hdu-5973gameoftakingstones（威佐夫博弈高精度）(代码片段)

题目描述：Twopeoplefacetwopilesofstonesandmakeagame.Theytaketurnstotakestones.Asgamerules,therearetwodifferentmethodsoftakingstones:Oneschemeisthatyoucantakeanynumberofstonesinanyonepilewhilethealternative 查看详情

hdu1527取石子游戏威佐夫博弈

题目来源：HDU1527取石子游戏题意：中文思路：威佐夫博弈必败态为（a,b）ai+i=bi    ai=i*(1+sqrt(5.0)+1)/2  这题就求出i然后带人i和i+1推断是否成立下面转自网上某总结有公式ak=[k（1+√5）/2]，bk=ak+k （k=0。1，... 查看详情