博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分支，也是运筹学的一个重要学科。（摘自百度百科）

引言

不知大家是否还记得这道题目？

一、什么是博弈？

博弈的英文为game，我们可以简单把它理解为“做游戏”。

只是这个游戏有一定的规则，并且有至少两个参加者，参加者需要在遵守游戏规则的前提下想方设法让自己获取胜利。对于两名参加者，两人都足够聪明且不会出现失误。
通俗的讲，博弈就是对于游戏中一种选择策略的研究。

二、巴什博奕（Bash Game）

巴什博奕是博弈论中最基础的问题，是合作博弈的一种。只要找出其必胜态，那么问题就解决了。

题目：两个顶尖聪明的人在玩游戏，有n个石子，每人最少拿1个，最多拿m个，两人轮流取石子，谁先把石子拿完谁就获得胜利。

从简单情况开始分析，进而推广到一般情况

简单情况

1. 当剩余石子有1—m个时，则先手必赢

2. 当剩余m+1个石子时，先手不论拿走多少个，后手都可以一次拿完所有石子，后手必赢

3. 当剩余m+2（m+1+1）个石子时，由于先手足够聪明，使用策略，先拿走1个，对于剩余的m+1个石子，不论后手怎么取，对于取剩下的石子先手都能一次性取完，先手必赢

4. 当剩余m+3（m+1+2）个石子时，由于先手足够聪明，使用策略，先拿走2个，对于剩余的m+1个石子，不论后手怎么取，对于取剩下的石子先手都能一次性取完，先手必赢

5. 当剩余2m+1（m+1+m）个石子时，由于先手足够聪明，使用策略，先拿走m个，对于剩余的m+1个石子，不论后手怎么取，对于取剩下的石子先手都能一次性取完，先手必赢

6. 当剩余m+2—2m+1 （m+1+1—m+1+m）个石子时，先手均可通过策略，赢得胜利

7. 当剩余2m+2（2(m+1)）个石子时，不论先手取1—m个，后手均可使用策略赢得游戏

8. 当剩余2m+3（2(m+1)+1）个石子时… … …先手必赢

9. 当剩余3m+2（2(m+1)+m）个石子时… … …先手必赢

10. 当剩余3m+3（3(m+1)）个石子时… … …后手必赢

推广到一般情况

1. 当n=k*(m+1)+x时，先手必赢（k=0,1,2,3… ，1<=x<=m）
2. 当n=k*(m+1)时，后手必赢（k=0,1,2,3…）

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	if(n%(m+1)==0){
		cout<<"后手赢";
	}else{
		cout<<"先手赢"; 
	} 
	return 0;
}

三、再来看一下引言这道题

随便举一个例子，比如这个字符串：00110

不难发现，在变成00000的前一步，字符串的最后一个字符都是‘1’。如此我们可以大胆的推测：如果末位字符为‘0’，则先手必败；否则先手必胜。

#include<iostream>
#include<string>
using namespace std;
int main() {
    int t;
    string a;
    cin >> t;
    while(t--){
        cin >> a;
        if(a[a.length()-1]=='0'){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }
}

四、再来试试某大学的招新赛的一道题

这道题也是博弈的一种，是纳什平衡（Nash equilibrium）问题，又称为非合作博弈均衡问题。每个参与者都只追求自身效益最大化，而不在乎其他参与者的策略，因此每个参与者的策略都具有竞争性和自私性。在纳什均衡状态中，每个参与者都不能通过单独改变其策略而获得更好的收益。

#include <iostream>
using namespace std;
int a[11]={1,2,4,8,16,32,64,128,256,512,1024};
int sg(int x,int step){
	int mmin,mmax;
	for(int i=0;i<=10;i++){
		if(a[i]==x)
			return step+1;
		if(a[i]>x){	
			mmin=x-a[i-1];
			mmax=a[i]-x;
			break;
		}
	}
	return min(sg(mmin,step),sg(mmax,step))+1;	
}
int main(){
	int x,y;
	cin>>x>>y;
	int xx=sg(x,0);
	int yy=sg(y,0);
	if(yy<=xx)
		cout<<"STO"<<endl;
	else
		cout<<"ORZ"<<endl; 
	return 0;
}

最后

以上就是怕孤独热狗为你收集整理的博弈论入门引言一、什么是博弈？二、巴什博奕（Bash Game）三、再来看一下引言这道题四、再来试试某大学的招新赛的一道题的全部内容，希望文章能够帮你解决博弈论入门引言一、什么是博弈？二、巴什博奕（Bash Game）三、再来看一下引言这道题四、再来试试某大学的招新赛的一道题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。