1 1 1 1 4 1 0 0 0
Fibo Nacci
#include <stdio.h>
#include <string.h>
#define MAX 1010
int fib[30] , sg[MAX];
void getSG()
{
bool visited[MAX] ;
for(int i = 1 ; i < MAX ; ++i)
{
memset(visited,false,sizeof(visited));
for(int j = 1 ; i-fib[j] >= 0 ; ++j)
{
visited[sg[i-fib[j]]] = true ;
}
for(int j = 0 ; j < MAX ; ++j)
{
if(!visited[j])
{
sg[i] = j ;
break ;
}
}
}
}
int main()
{
fib[1] = 1 ,fib[2] = 2 ;
for(int i = 3 ; i < 30 ; ++i)
{
fib[i] = fib[i-1]+fib[i-2] ;
if(fib[i]>1000)
{
break ;
}
}
int m , n , p ;
getSG() ;
while(~scanf("%d%d%d",&m,&n,&p) && (m||n||p))
{
int ans = sg[m]^sg[n]^sg[p] ;
if(ans)
{
puts("Fibo");
}
else
{
puts("Nacci") ;
}
}
return 0 ;
}hdu 1848 Fibonacci again and again 博弈论,求出SG函数,,什么问题都没有了
原文:http://blog.csdn.net/lionel_d/article/details/43991931