博弈论（入门学习+习题）

巴什博弈：

1. The first title:
   题目链接：Brave Game
   

思路分析

简要的巴什博弈公式的运用：
n == ((m + 1) * r + s

代码解析

#include<iostream>
using namespace std;
int main()
{
	int total,flag;
	cin >> total;  ///输入测试总数
	while (total--) {
		int n, m;
		flag = 0;
		cin >> n >> m;  //输入石头总数，每次允许拿的最多石头数
		for (int r = 0; r < n; ++r) {
			for (int s = 1; s <= m; ++s) {
				if (n == ((m + 1) * r + s)) {  //遍历值，寻找满足该的公式的解，即可。
					flag = 1;
					break;
				}
			}
			if (flag)
				break;
		}
		if (flag)
			cout << "first" << endl;
		else
			cout << "second" << endl;
	}
	return 0;
}

测试结果

---

2. The second title:
   

思路解析

根据输入的n和m的数据，当m或者n为偶数的时候，kiki获胜；当m与n为奇数的时候，zz获胜；
其中，根据每次移动的方向只有正左方和正下方与左下方，那么向左下方进行移动的时候，如果m或者n是偶数，那么即可保证在（n或者m都减少1时）每次都是kiki占据优先权。如果m与n都是奇数的时候，则最后会是zz占据优先权，并取得胜利。

源码：

---

---

3. The third title
   
   
   源码：

#include<iostream>
using namespace std;
int main()
{
	int n, m;
	while (cin >> m >> n) {
		if (m <= n)  //当可以一次性付完时
			for (int i = m; i <= n; ++i)
				cout << i << " ";
		else {
			//当不能凑成巴什博弈公式时
			if (m % (n + 1) == 0)
				cout << "none" << endl;
			//存在解时
			else
				cout << m % (n + 1) << endl;
		}
	}
	return 0;
}

---

---

4. The fourth title
   
   

代码解析

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

---

---

威佐夫博弈

概念：有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5）+1）/2）*z ]；
若w=x，则先手必败，否则先手必胜。

#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
int main()
{
	int m,n;
	while(cin >> m >> n){
		int a = min(m,n);
		int b = max(m,n);
		int temp = (int)(((sqrt(5) + 1) / 2)*(b - a));
		if(temp == a)
			cout << 0 << endl;
		else
			cout << 1 << endl;
	} 
	return 0;
}