斐波那契博弈（fibonacci Game）

简述展开目录

一堆石子有 n 个，两人轮流取，先取者第一次可以取任意多个，但不能全部取完，以后每次取石子的数目不能超过上次取子数的 2 倍，先取完者胜

分析展开目录

这个游戏叫做 Fibonacci Game，肯定和 Fibonacci 数列 f [n]：1，1，2，3，5，8，13，21，34，55，89，… 有密切关系，结论：先手胜，当且仅当 n 不是 fibonacci 数列

证明过程有点复杂，建议看这篇文章

那么当 n 不是斐波那契数列的时候，先手应该如何拿，才能胜呢？这里涉及到一个定理：任何正整数可以表示为若干个不连续的 Fibonacci 数之和，比方说分解 50，注意到 50 夹在 34 和 55 之间，于是 50 可以写成 50=34+16，然后再分解 16，16 被夹在 13 和 21 之间，于是 16 可以写成 16=13+3，所以 50 可以分解成 50=34+13+3

如果 n 不是 fibonacci 数，我们首先将 n 表示为 $n=f [a_1]+f [a_2]+...+f [a_{p-1}]+f [a_p]$，对于 50 就是 50=34+13+3。那么。我们令先手先取 $f [a_p]$ 个石子，即最少的 3，此时后手只能取 13 这一堆，且不能一次性取完，因为题目限定不能超过上次的两倍，即在这里不能超过 6，此时对手相当于面对这个游戏的子游戏（只有 $f [a_{p-1}]$，且后手先取）的必败态，即先手一定可以取到这一堆的最后一颗石子。同理可知，对于以后的每一堆，先手都可以取到这一堆的最后一颗，从而获得游戏胜利

题目链接：HDU2516 取石子游戏展开目录

题解展开目录

先用递推求出一系列 fibonacci 数，然后用输入跟这些 fibonacci 数一个一个比对，如果是 fibonacci 数，则后手胜，否则前者胜

代码展开目录

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int f[50] = {1,2};
    for(int i = 2;i < 50;i++)
        f[i] = f[i-1] + f[i-2];
    while(cin>>n&&n)
    {
        int cnt;
        for(cnt = 0;cnt < 50;cnt++)
            if(f[cnt] == n)
                break;
        if(cnt == 50)
            cout<<"First win"<<endl;
        else
            cout<<"Second win"<<endl;
    }
    return 0;
}