模板|博弈基本介绍模板|c++

巴什博弈
这是一个很简单的博弈
举个例子
1、本游戏是一个二人游戏;
2、有一堆石子一共有n个；
3、两人轮流进行;
4、每走一步可以取走1…m个石子；
5、最先取光石子的一方为胜
必败点：下一个选手将取胜的位置称为必败点
【模板|博弈基本介绍】必胜点：下一个选手将必败的位置称为必胜点
first人可以去 1~m个，那m+1个 second人必胜
那么如果second想要胜利必须是m+1的倍数，只有这样second人才能保证自己胜利

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

斐波那契博弈

有一堆个数为 n ( n ≥ 2 ) n(n\ge 2)n(n≥2)的石子，游戏双方轮流取石子，规则如下：
先手不能在第一次把所有的石子取完，至少取 1 11 颗；
之后每次可以取的石子数至少为 1 11，至多为对手刚取的石子数的 2 22 倍。
约定取走最后一个石子的人为赢家，求必败态。
先手必败，当且仅当石子数为斐波那契数
先证明必要性，斐波那契数一定先手必败，可以用数学归纳法，大致思路就是一定能拆成两堆斐波那契数，不论先手怎样取，后手总能取到最后一颗
然后证明充分性，由定理：任何正整数可以表示为若干个不连续的Fibonacci数之和，那么就回到了斐波那契数列里

#include "bits/stdc++.h" using namespace std; int n,m,p; mapmp; int main() { int a = 1 , b = 2; mp[1]=mp[2]= true; for(int i=1; i<=50; i++){ int k = a+b; mp[k]= true; a=b; b=k; } while (cin >> n) { cout << (mp[n] ? "second" : "first") << endl; } return 0; }