学步园

题目：题目链接

题目的意思：两个人轮流拿石子，其中每一个人拿的棋子数大于等于1小于等于对手上次拿的2倍，然后问你先手在胜利的情况下，第一步应该拿走多少？

分析：

加入石子数是2的话，那么先手只能拿走1个。这样先手必输。当n==3时，先手也是输。当是4个时。先手拿一个让对手面对3个，那么先手必胜，这样推下来，先手必输的数列数斐波那契数列。这样，当输入一个数字时，我们可以判断它是不是斐波那契数，是的话先手必败，当不是的时候，先手就需要通过拿走一定数量的石子，假设给出n，n不是菲波那契数，则A必胜的策略就是必须逼B走到离n最近且不大于n的菲波那契数x，同时使得B不能一次就把这个菲波那契数x取完。我们可以看出这个策略具有递归性。为了迫使B走到x，我们就变成了对于n-x块石头，且n-x不是菲波那契数，要使得符合题目规则的情况下，使得A能够拿走n-x中的最后一块石头。这时，就可以看出问题中的n变成了n-x了。然后就是递归的终结条件，对于某一步剩下的石头是菲波那契数，则A就可以全部拿走，这就是答案，这时B不能拿石头，进入必败状态。

代码：

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
using namespace std;

const int kMAX=1001;
const double kEPS=10E-6;
int  lose[kMAX];
int cnt=2;

int win(const int &x)
{
    int idx=0;
    for( ; idx < cnt && lose[idx]<=x; ++idx);
        --idx;
    if(lose[idx]==x)
        return x;
    else return win(x-lose[idx]);
}

int main()
{
    int n;
    memset(lose,true,sizeof(lose));
    lose[0]=1;
    lose[1]=2;
    while(1)//斐波那契数列
    {
        lose[cnt]=lose[cnt-2]+lose[cnt-1];
        if(lose[cnt]>100000001)
            break;
        ++cnt;
    }
    while(~scanf("%d",&n) && n)
    {
        int idx = 0;
        for( ; idx < cnt && lose[idx] <= n; ++idx);
        --idx;
        if(lose[idx]==n)
            printf("lose\n");
        else
        {
            printf("%d\n",win(n-lose[idx]));
        }
    }

    return 0;
}

努力努力...