巴什博弈 :
只有一堆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）的倍数，就能最后获胜.
也就是说,谁面对的物品数为 k*(m + 1)时,在 俩人 都不会犯错的前提下,谁就会必败.
假如 开始 时 物品数 为 m+1 的整数倍时.
先手拿走 a 个,后手只要保证下次 先手面对的情况还是 m+1 的整数倍. 直到最后剩下 m+1 个,先手不可能一次拿走,但至少要拿 1 个,剩下的 物品数 必定 <= m ,此时,后手可以一次拿走,即后手胜.
假如 开始 时 物品数 不是 m+1 的整数倍时, mod = n % (m + 1).
只要 先手拿走 mod 个,后手 面临 的物品数 就为 m + 1 的整数倍,之后同上.
例 : Brave Game
#include<cstdio>
using namespace std;
int main( )
{
int t;
scanf( "%d",&t);
while(t--)
{
int n,m;
scanf( "%d%d",&n,&m);
int mod = n%(m+1);
if(mod == 0) printf( "second\n");
else printf( "first\n");
}
}
斐波那契博弈:
有一堆个数为n的石子，游戏双方轮流取石子，满足：
1)先手不能在第一次把所有的石子取完；
2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。
约定取走最后一个石子的人为赢家，求必败态。
斐波那契 博弈 是 在 齐肯多夫定理的基础下 成立的
齐肯多夫定理 : 任何正整数都可以表示成若干个不连续的斐波那契数（不包括第一个斐波那契数）之和。
当 n = 2 时,先手只能拿 1 个,则 后手胜
当 n = 3 时,先手只能拿1或2 个,后手胜,
当 n = 4 时,先手 拿走 1 个时,后手面临的物品数 为 3 个,然后将 后手看做先手,先手 看做 后手, 同 n = 3,即 先首胜.
… …
因为 每一个 数都可以拆成若干个斐波那契数之和, 当 n 不是 斐波那契数 时, 先手拿走 k 个后,使 n - k 是斐波那契数,即后手面对的 物品数 是斐波那契数,不论 后手拿走多少个,先手只要保证 剩下的数 为 斐波那契数, 即 先手胜.
当n 是 斐波那契数是,不论先手拿走多少个,后手只要保证剩下的数是斐波那契数时,后手胜.
综上所述 : 当 物品数 为斐波那契数为 必败态.
例 : 取石子游戏
#include<cstdio>
using namespace std;
long long f[55];
int main( )
{
long long n;
while(scanf( "%lld",&n) && n)
{
int flag = 0;
f[0] = 2;
f[1] = 3;
if(n == f[0] || n == f[1]) flag = 1;
for(int i = 2;i <= 50;i++)
{
f[i] = f[i-1] + f[i-2];
if(f[i] == n)
{
flag = 1;
break;
}
}
if(flag == 1) printf( "Second win\n");
else printf( "First win\n");
}
}