Fibonacci again and again

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8380????Accepted Submission(s): 3462

Problem Description 任何一個大學生對菲波那契數(shù)列(Fibonacci numbers)應(yīng)該都不會陌生，它是這樣定義的：
F(1)=1;
F(2)=2;
F(n)=F(n-1)+F(n-2)(n>=3);
所以，1,2,3,5,8,13……就是菲波那契數(shù)列。
在HDOJ上有不少相關(guān)的題目，比如1005 Fibonacci again就是曾經(jīng)的浙江省賽題。
今天，又一個關(guān)于Fibonacci的題目出現(xiàn)了，它是一個小游戲，定義如下：
1、??這是一個二人游戲;
2、??一共有3堆石子，數(shù)量分別是m, n, p個；
3、??兩人輪流走;
4、??每走一步可以選擇任意一堆石子，然后取走f個；
5、??f只能是菲波那契數(shù)列中的元素（即每次只能取1，2，3，5，8…等數(shù)量）；
6、??最先取光所有石子的人為勝者；

假設(shè)雙方都使用最優(yōu)策略，請判斷先手的人會贏還是后手的人會贏。

?

Input 輸入數(shù)據(jù)包含多個測試用例，每個測試用例占一行，包含3個整數(shù)m,n,p（1<=m,n,p<=1000）。
m=n=p=0則表示輸入結(jié)束。

?

Output 如果先手的人能贏，請輸出“Fibo”，否則請輸出“Nacci”，每個實例的輸出占一行。

?

Sample Input 1 1 1 1 4 1 0 0 0

?

Sample Output Fibo Nacci

?

Author lcy

?

Source ACM Short Term Exam_2007/12/13

?

Recommend lcy???|???We have carefully selected several similar problems for you:??1404?1730?1729?2509?1524? 直接用sg函數(shù)，記憶化搜索一個。 1 //15MS 5608K 685B G++ 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 int fibo[20]={1,2}; 6 int sg[1005]; 7 void init() 8 { 9 for(int i=2;i<20;i++){ 10 fibo[i]=fibo[i-1] + fibo[i-2]; 11 } 12 } 13 int mex(int x) 14 { 15 int flag[1005]={0}; 16 for(int i=0;i<20;i++){ 17 int temp = x-fibo[i]; 18 if(temp<0) break; 19 if(sg[temp]==-1)sg[temp]=mex(temp); 20 flag[sg[temp]]=1; 21 } 22 for(int i=0;;i++){ 23 if(!flag[i]){ 24 return i; 25 } 26 } 27 } 28 int main() 29 { 30 int a,b,c; 31 init(); 32 for(int i=0;i<1005;i++) 33 sg[i]=-1; 34 while(scanf("%d%d%d",&a,&b,&c)!=EOF) 35 { 36 if(a==0 || b==0 || c==0){ 37 break; 38 } 39 if(mex(a)^mex(b)^mex(c)){ 40 puts("Fibo"); 41 }else{ 42 puts("Nacci"); 43 } 44 } 45 return 0; 46 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/GO-NO-1/p/6344044.html

總結(jié)

以上是生活随笔為你收集整理的hdu 1848（Fibonacci again and again）（SG博弈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。