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

巴什博弈：

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; }

测试结果

---

The second title:

思路解析

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

源码：

---

---

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; }

---

---

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; }