{"rsdb":{"rid":"302582","subhead":"","postdate":"0","aid":"217747","fid":"49","uid":"1","topic":"1","content":"
\n

Fibonacci again and again\uff08http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=1848\uff09<\/h1> \n

Time Limit: 1000\/1000 MS (Java\/Others)    Memory Limit: 32768\/32768 K (Java\/Others)
Total Submission(s): 12753    Accepted Submission(s): 5563
<\/strong><\/span>

<\/p> \n

\n Problem Description\n <\/div> \n
\n \u4efb\u4f55\u4e00\u4e2a\u5927\u5b66\u751f\u5bf9\u83f2\u6ce2\u90a3\u5951\u6570\u5217(Fibonacci numbers)\u5e94\u8be5\u90fd\u4e0d\u4f1a\u964c\u751f\uff0c\u5b83\u662f\u8fd9\u6837\u5b9a\u4e49\u7684\uff1a\n
F(1)=1;\n
F(2)=2;\n
F(n)=F(n-1)+F(n-2)(n>=3);\n
\u6240\u4ee5\uff0c1,2,3,5,8,13\u2026\u2026\u5c31\u662f\u83f2\u6ce2\u90a3\u5951\u6570\u5217\u3002\n
\u5728HDOJ\u4e0a\u6709\u4e0d\u5c11\u76f8\u5173\u7684\u9898\u76ee\uff0c\u6bd4\u59821005 Fibonacci again\u5c31\u662f\u66fe\u7ecf\u7684\u6d59\u6c5f\u7701\u8d5b\u9898\u3002\n
\u4eca\u5929\uff0c\u53c8\u4e00\u4e2a\u5173\u4e8eFibonacci\u7684\u9898\u76ee\u51fa\u73b0\u4e86\uff0c\u5b83\u662f\u4e00\u4e2a\u5c0f\u6e38\u620f\uff0c\u5b9a\u4e49\u5982\u4e0b\uff1a\n
1\u3001  \u8fd9\u662f\u4e00\u4e2a\u4e8c\u4eba\u6e38\u620f;\n
2\u3001  \u4e00\u5171\u67093\u5806\u77f3\u5b50\uff0c\u6570\u91cf\u5206\u522b\u662fm, n, p\u4e2a\uff1b\n
3\u3001  \u4e24\u4eba\u8f6e\u6d41\u8d70;\n
4\u3001  \u6bcf\u8d70\u4e00\u6b65\u53ef\u4ee5\u9009\u62e9\u4efb\u610f\u4e00\u5806\u77f3\u5b50\uff0c\u7136\u540e\u53d6\u8d70f\u4e2a\uff1b\n
5\u3001  f\u53ea\u80fd\u662f\u83f2\u6ce2\u90a3\u5951\u6570\u5217\u4e2d\u7684\u5143\u7d20\uff08\u5373\u6bcf\u6b21\u53ea\u80fd\u53d61\uff0c2\uff0c3\uff0c5\uff0c8\u2026\u7b49\u6570\u91cf\uff09\uff1b\n
6\u3001  \u6700\u5148\u53d6\u5149\u6240\u6709\u77f3\u5b50\u7684\u4eba\u4e3a\u80dc\u8005\uff1b\n
\n
\u5047\u8bbe\u53cc\u65b9\u90fd\u4f7f\u7528\u6700\u4f18\u7b56\u7565\uff0c\u8bf7\u5224\u65ad\u5148\u624b\u7684\u4eba\u4f1a\u8d62\u8fd8\u662f\u540e\u624b\u7684\u4eba\u4f1a\u8d62\u3002\n <\/div> \n
\n  \n <\/div> \n

 <\/p> \n

\n Input\n <\/div> \n
\n \u8f93\u5165\u6570\u636e\u5305\u542b\u591a\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u6bcf\u4e2a\u6d4b\u8bd5\u7528\u4f8b\u5360\u4e00\u884c\uff0c\u5305\u542b3\u4e2a\u6574\u6570m,n,p\uff081<=m,n,p<=1000\uff09\u3002\n
m=n=p=0\u5219\u8868\u793a\u8f93\u5165\u7ed3\u675f\u3002\n <\/div> \n
\n  \n <\/div> \n

 <\/p> \n

\n Output\n <\/div> \n
\n \u5982\u679c\u5148\u624b\u7684\u4eba\u80fd\u8d62\uff0c\u8bf7\u8f93\u51fa\u201cFibo\u201d\uff0c\u5426\u5219\u8bf7\u8f93\u51fa\u201cNacci\u201d\uff0c\u6bcf\u4e2a\u5b9e\u4f8b\u7684\u8f93\u51fa\u5360\u4e00\u884c\u3002\n <\/div> \n
\n  \n <\/div> \n

 <\/p> \n

\n Sample Input\n <\/div> \n
\n
\n 1 1 1 \n <\/div> \n
\n 1 4 1\n <\/div> \n
\n 0 0 0\n <\/div> \n <\/div> \n
\n  \n <\/div> \n
\n Sample Output\n <\/div> \n
\n
\n Fibo \n <\/div> \n
\n Nacci\n <\/div> \n
\n  \n <\/div> \n
\n
\n 
#include <iostream>\r\n#include<\/span><string<\/span>.h>\r\n#include<\/span><cstdio>\r\nusing<\/span> namespace<\/span> std;\r\n<\/span>const<\/span> int<\/span> MAXN = 1005<\/span>;\r\n<\/span>int<\/span> f[MAXN];\r\n<\/span>int<\/span> s[MAXN];\r\n<\/span>int<\/span> sg[MAXN];\r\n<\/span>void<\/span> getSG(int<\/span> n)\r\n{\r\n    <\/span>int<\/span> i,j;\r\n    <\/span>for<\/span>(i=1<\/span>;i<=n;i++)\r\n    {\r\n        memset(s,<\/span>0<\/span>,sizeof<\/span>(s));\r\n        <\/span>for<\/span>(j=0<\/span>;f[j]<=i&&j<=20<\/span>;j++)\r\n                s[sg[i<\/span>-f[j]]]=1<\/span>;\r\n        <\/span>for<\/span>(j=0<\/span>;;j++)\r\n        {\r\n            <\/span>if<\/span>(!s[j])\r\n            {\r\n                sg[i]<\/span>=j;\r\n                <\/span>break<\/span>;\r\n            }\r\n        }\r\n    }\r\n}\r\n<\/span>int<\/span> main()\r\n{\r\n    f[<\/span>1<\/span>]=1<\/span>,f[0<\/span>]=1<\/span>;\r\n    <\/span>for<\/span>(int<\/span> i=2<\/span>;i<=16<\/span>;i++)\r\n        f[i]<\/span>=f[i-1<\/span>]+f[i-2<\/span>];\r\n        getSG(<\/span>1000<\/span>);\r\n    <\/span>int<\/span> m,n,p;\r\n    <\/span>while<\/span>(scanf("<\/span>%d%d%d<\/span>"<\/span>,&m,&n,&p),m||n||p)\r\n    {\r\n        <\/span>if<\/span>(sg[m]^sg[n]^sg[p])\r\n            cout <\/span><< "<\/span>Fibo<\/span>"<\/span> << endl;\r\n        <\/span>else<\/span>\r\n            cout <\/span><< "<\/span>Nacci<\/span>"<\/span> << endl;\r\n    }\r\n    <\/span>return<\/span> 0<\/span>;\r\n}<\/span><\/pre> \n   <\/div> \n   
 <\/p> \n  <\/div> \n  
\n    \n  <\/div> \n <\/div>\n<\/div>","orderid":"0","title":"\u535a\u5f08\u8bba\u4e4bSG\u51fd\u6570","smalltitle":"","mid":"0","fname":"c++\u7f16\u7a0b\u57fa\u7840","special_id":"0","bak_id":"0","info":"0","hits":"117","pages":"1","comments":"0","posttime":"2019-04-08 00:07:48","list":"1554653268","username":"admin","author":"","copyfrom":"","copyfromurl":"","titlecolor":"","fonttype":"0","titleicon":"0","picurl":"https:\/\/www.cppentry.com\/upload_files\/","ispic":"0","yz":"1","yzer":"","yztime":"0","levels":"0","levelstime":"0","keywords":"\u535a\u5f08\u8bba<\/A> \u51fd\u6570<\/A>","jumpurl":"","iframeurl":"","style":"","template":"a:3:{s:4:\"head\";s:0:\"\";s:4:\"foot\";s:0:\"\";s:8:\"bencandy\";s:0:\"\";}","target":"0","ip":"47.106.78.186","lastfid":"0","money":"0","buyuser":"","passwd":"","allowdown":"","allowview":"","editer":"","edittime":"0","begintime":"0","endtime":"0","description":"\u535a\u5f08\u8bba\u4e4bSG\u51fd\u6570","lastview":"1714221512","digg_num":"0","digg_time":"0","forbidcomment":"0","ifvote":"0","heart":"","htmlname":"","city_id":"0"},"page":"1"}