今天，又一个关于Fibonacci的题目出现了，它是一个小游戏，定义如下：
1、  这是一个二人游戏;
2、  一共有3堆石子，数量分别是m, n, p个；
3、  两人轮流走;
4、  每走一步可以选择任意一堆石子，然后取走f个；
5、  f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量）；
6、  最先取光所有石子的人为胜者；

HDOJ 1848 Fibonacci again and again

http://acm.hdu.edu.cn/showproblem.php?pid=1848

又一博弈，用求SG的方法可轻易得解

view plaincopy to clipboardprint?
#include <iostream>  
using namespace std;  
    int enable[15];  
    int k = 15;             //enable的个数  
    int SG[1001];       //存放SG值  
    int SG_value(int n)         //求SG值  
    {  
        int i,temp;  
        int judge[16]={0};      //用于寻找最小的SG值做标记  
        for(i=0;i<k;i++)  
        {  
            temp = n - enable;  
            if(temp<0)  
                break;  
            if(SG[temp]==-1)    //寻找最小的SG数  
                SG[temp]=SG_value(temp);  
            judge[SG[temp]]=1;  //为后继点加上标记  
        }  
        for(i=0;;i++)           //找到每一个SG［i］的最小SG值  
        {  
            if(judge==0)  
                return i;  
        }  
    }  
int main()  
{  
    int m,i,j,l,n,t,p;  
    enable[0] = 1;  
    enable[1] = 2;  
    for (i=2;i<15;i++)  
    {  
        enable = enable[i-1] + enable[i-2];  
    }  
    int s;  
    while (scanf("%d %d %d",&m,&n,&p)!=EOF)  
    {  
        memset(SG,-1,sizeof(SG));//初始化  
        if (m == 0 && n == 0 && p == 0)  
        {  
            break;  
        }  
        s = SG_value(n)^SG_value(m)^SG_value(p);  
        if (s == 0)  
        {  
            printf("Nacci\n");  
        }  
        else
            printf("Fibo\n");  
    }  
    return 0;  
}
#include <iostream>
using namespace std;
int enable[15];
int k = 15;    //enable的个数
int SG[1001];  //存放SG值
int SG_value(int n)   //求SG值
{
  int i,temp;
  int judge[16]={0};  //用于寻找最小的SG值做标记
  for(i=0;i<k;i++)
  {
   temp = n - enable;
   if(temp<0)
    break;
   if(SG[temp]==-1) //寻找最小的SG数
    SG[temp]=SG_value(temp);
   judge[SG[temp]]=1; //为后继点加上标记
  }
  for(i=0;;i++)   //找到每一个SG［i］的最小SG值
  {
   if(judge==0)
    return i;
  }
}
int main()
{
int m,i,j,l,n,t,p;
enable[0] = 1;
enable[1] = 2;
for (i=2;i<15;i++)
{
  enable = enable[i-1] + enable[i-2];
}
int s;
while (scanf("%d %d %d",&m,&n,&p)!=EOF)
{
  memset(SG,-1,sizeof(SG));//初始化
  if (m == 0 && n == 0 && p == 0)
  {
   break;
  }
  s = SG_value(n)^SG_value(m)^SG_value(p);
  if (s == 0)
  {
   printf("Nacci\n");
  }
  else
   printf("Fibo\n");
}
return 0;
}

好复杂的样子啊！