欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

博弈论入门

程序员文章站 2022-06-29 13:32:05
...

 【算法设计与分析】三个博弈论算法分析:这篇文章详细介绍了巴什博弈,尼姆博弈,威佐夫博弈,感觉不错!

hdu2147 kiki's game

下面介绍此类题目的通用方法:P/N分析

P点:即必败点,某玩家位于该点,只要对方无误,则必败;

N点:即必胜点,某玩家位于该点,只要自己无误,则必胜。

三个定理:

1.所有终结点都是必败点P;

2.所有一步能走到必败点P的就是N点;

3.通过一步操作只能到N点的就是P点(hdu 1846,2147,2149 ,2188)

P/N分析:

 博弈论入门
由上图分析可知,当横纵全为奇数时,为必败点。

#include<iostream>
using namespace std;

int main(){
	int n,m;
	while(cin>>n>>m){
		if(n==0&&m==0) break;	
		if(n%2&&m%2) cout<<"What a pity!"<<endl;
		else cout<<"Wonderful!"<<endl;
	}
	return 0;
}

1.巴什博弈:同余理论

1.1.hdu1846.Brave Game

巴什博弈:只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个。最后取光者得胜。

显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。

#include<iostream>
using namespace std;
int main(){
	int c,n,m;
	cin>>c;
	while(c--){
		cin>>n>>m;
		if(n%(m+1)==0) cout<<"second"<<endl;
		else cout<<"first"<<endl;
	}
	return 0;
}

1.2.hdu2149 Public Sale

#include<iostream>
using namespace std;
int main(){
	int n,m;
	while(cin>>m>>n){
		if(m>n){
			if(m%(n+1)==0) cout<<"none"<<endl;
			else cout<<m%(n+1)<<endl;
		}else{
			cout<<m;
			for(int i=m+1;i<=n;i++)
				cout<<" "<<i;
			cout<<endl;
		}
	}
	return 0;
}

1.3. hdu2188 悼念512汶川大地震遇难同胞——选拔志愿者

#include<iostream>
using namespace std;

int main(){
	int n,m,c;
	cin>>c;
	while(c--){
		cin>>n>>m;	
		if(n%(m+1)==0) cout<<"Rabbit"<<endl;
		else cout<<"Grass"<<endl;
	}
	return 0;
}

2.Fibonacci's Game(斐波那契博弈)

有一堆个数为n的石子,游戏双方轮流取石子,满足:

1)先手不能在第一次将所有的石子取完;

2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。


 

3.威佐夫博弈:黄金分割

3.1.51nod 1072

博弈论入门

Input示例

3
3 5
3 4
1 9

Output示例

B
A
A
/*
Wythoff Game:黄金分割
每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取
若2堆石子的差值*(sqrt(5)+1)/2==最小值,后手赢,否则先手赢 
*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
	int n,a,b;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&a,&b);
		if(a<b) swap(a,b);
		int t=(a-b)*(sqrt(5)+1)/2;
		if(t==b) puts("B");
		else puts("A");
	}
	return 0;
}

3.2. 51nod 1185 威佐夫游戏 V2 (博弈+大数乘法模拟)

博弈论入门

Input示例

3
3 5
3 4
1 9

Output示例

B
A
A

参考:https://blog.csdn.net/liangzhaoyang1/article/details/72594221

博弈论入门

今天脑袋秀逗了吧,看了一下午没看懂大数乘法模拟,现在终于看懂啦,哈哈哈哈

这个大佬的题解写的很详细,我就直接贴过来了。

博弈论入门

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 //0.618033988749894848204586834... 拆成整数放进数组里,
 //拆成三部分即可 
ll tmp[3] = {618033988,749894848,204586834};
ll MOD = 1e9;

int main()
{
    int t;  
    scanf("%d",&t);
    while(t --)
    {
        ll a,b;
        scanf("%lld%lld",&a,&b);        
        if(a > b)
        {
            ll t = a;
            a = b;
            b = t;
        }
        ll diff = b - a;
        //把10^18分成两部分10^9
        ll ta = diff / MOD; 
        ll tb = diff % MOD;

        ll tp = tb * tmp[2];
        tp = ta * tmp[2] + tb * tmp[1] + tp / MOD;
        tp = ta * tmp[1] + tb * tmp[0] + tp / MOD;
        tp = ta * tmp[0] + tp / MOD + diff; 

        if(tp == a)
            printf("B\n");
        else
            printf("A\n");
    }
    return 0;
}

 

4.Nim博弈:异或理论

51nod1069 Nim游戏 博弈论入门

博弈论入门

Input示例

3
1
1
1

Output示例

A
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;

int main(){
	int n,a,res=0;
	scanf("%d",&n);
	while(n--){
		scanf("%d",&a);
		res^=a;
	}
	
	//res==0后手赢
	if(res==0) printf("B\n");
	else printf("A\n");
	return 0;
}

 

相关标签: 巴什博弈