Fibonacci again and again

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

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

假設(shè)雙方都使用最優(yōu)策略，請(qǐng)判斷先手的人會(huì)贏還是后手的人會(huì)贏。 ? Input 輸入數(shù)據(jù)包含多個(gè)測(cè)試用例，每個(gè)測(cè)試用例占一行，包含3個(gè)整數(shù)m,n,p（1<=m,n,p<=1000）。
m=n=p=0則表示輸入結(jié)束。 Output 如果先手的人能贏，請(qǐng)輸出“Fibo”，否則請(qǐng)輸出“Nacci”，每個(gè)實(shí)例的輸出占一行。 Sample Input 1 1 1 1 4 1 0 0 0 Sample Output Fibo Nacci ? 題意：類(lèi)似于Nim博弈 題解：組合游戲，SG函數(shù)每個(gè)SG[n]可以由前面的推出 #include<bits/stdc++.h> #define N 4500 #define mes(x) memset(x, 0, sizeof(x)); #define ll __int64 const long long mod = 1e9+7; const int MAX = 0x7ffffff; using namespace std; int a[20], SG[1050], dir[20]; int main() {int i, n;a[1] = 1;a[2] = 2;for(i=3;i<=16;i++)a[i] = a[i-1]+a[i-2];SG[0] = 0;for(n=1;n<=1000;n++){mes(dir);for(i=1;a[i]<=n;i++)dir[SG[n-a[i]]] = 1;for(i=0;;i++)if(!dir[i]){SG[n] = i;break;}} int b[3], ans;while(~scanf("%d%d%d", &b[0], &b[1], &b[2])&&(b[0]||b[1]||b[2])){ans = 0;for(int i=0;i<=2;i++)ans ^= SG[b[i]];if(ans == 0)printf("Nacci\n");else printf("Fibo\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Noevon/p/6240417.html

總結(jié)

以上是生活随笔為你收集整理的HDU1848 Fibonacci again and again SG函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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