MENU

斐波那契博弈(fibonacci Game)

April 15, 2018 • Read: 261 • 算法

简述

一堆石子有 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;
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code