zoj 2290 GAME 博弈

转的 一篇非常好的分析 http://www.stubc.com/thread-3747-1-1.html

A必输的情形形成菲波那契数列。

显然，2和3是A必输的情形。现在，设a和a[i+1]是连续两个A必输的状态，则a[i+2]=a

+a[i+1]也是A必输的状态。因为，根据菲波那契数列的特点，A不能一次取a个以上

（含a个），否则，因为a[i+1]<2*a，B可以一次把剩下的全取完(不超过a[i+1]块）。



剩下的问题就是，B能否在留下a[i+1]块stones的同时，保证A不能一次性拿完剩下的所有

stones。如果成立的话，这就回到了a[i+1]的状态。我们假设，对于a块stones，B可以

保证最后一把不会超过a[i-1]（2和3时都成立），而a[i+1]（=a+a[i-1]）>2*a[i-1]。

这就保证了剩下的a[i+1]块石头不会被A一次取完。注意到这时，B最后一把不会超过a[i+

1],其实也就归纳的证明了刚才的假设。



上述的证明其实也提示了A赢的情况下的策略。这也是一个递归的结果。设有n（n不是菲波

那契数）块stones，离它最近而比它小的菲波那契数是a。A拿掉n-a块后，留下a块给B先拿

，A就赢了。令n=n-a。若n是菲波那契数，则A必须一次性取n块。否则，重复上面过程，直

到n为菲波那契数（包括1）为止。

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int fib[45];
int is_that(int re)
{
    int i=0;
    while(fib[i]<re)i++;
    if(fib[i]==re)return re;
    else return is_that(re-fib[i-1]);
}
int main()
{
    int i;
    fib[0]=1;fib[1]=1;
    for(i=2;i<45;i++)
        fib[i]=fib[i-1]+fib[i-2];
    int n;
    while(~scanf("%d",&n))
    {
        i=0;
        while(fib[i]<n)i++;
        if(fib[i]==n)puts("lose");
        else printf("%d\n",is_that(n-fib[i-1]));
    }

}