斐波那契博弈

佚名 6年前 (2019-04-13) 随笔 1316人围观抢沙发百度已收录

一堆个数为n的物品，双方轮流按如下规则取物品，取完最后物品的人胜利。

先手不可以第一次取完所有物品。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

之后每次可以取得物品个数1<=k<=对手上次取得个数的2倍。

结论：

先手胜当且仅当n不是Fibonacci数。（证明略，心累）

using namespace std;
int fib[50];
int main(){
    fib[0]=1;fib[1]=2;
    for(int i=2;i<45;i++)
        fib[i]=fib[i-1]+fib[i-2];//打表 int n;
    while(scanf("%d",&n)!=EOF&&n){
        int i=0;
        for(i=0;i<45;i++)
            if(fib[i]==n)
                break;
        if(i<45)
            puts("Second");
        else
            puts("First");
    }
    return 0;
}