西安市高新区建设局网站,网站开发个人技能,aspnet东莞网站建设,做百度推广效果怎么样这道题的结论就是#xff0c;石子的个数为斐波那契数列某一项的时候#xff0c;先手必败#xff1b;否则#xff0c;先手必胜。 结论很简单#xff0c;但是证明却不是特别容易。找了好几篇博客#xff0c;发现不一样的也就两篇#xff0c;但是这两篇给的证明感觉证得不清…这道题的结论就是石子的个数为斐波那契数列某一项的时候先手必败否则先手必胜。 结论很简单但是证明却不是特别容易。找了好几篇博客发现不一样的也就两篇但是这两篇给的证明感觉证得不清不楚的没看太懂。 首先证明要依赖一个邓肯多夫定理(Zeckendorfs Theorem)任何一个正整数一定能分解成若干个不重复且不相邻的斐波那契数之和。 首推维基百科上的英文证明很严谨也能看懂证明的过程中还用到了一条引理但是很容易用数学归纳法证明所以整个过程都是十分严谨的http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem 然后对于一个必胜状态则这个数可以分解成多个斐波那契数之和或者可以对应地将这堆石子分成若干堆来看而且每堆石子的数量都是一个斐波那契数。 先手取完最小的那个石子堆其数量为Fi由于邓肯多夫定理定理第二小的石子堆Fj ≥ Fi2 Fi Fi1 2Fi所以后手面对的局面就是若干个斐波那契数而且不能一次取完最小的石子堆。然后等后手取完以后再继续将剩下的石子数分解再取最小的斐波那契数即可。 对于一个先手必败状态也就是一个斐波那契数局面证明不太会证。 这有一篇证明但是感觉不严谨啊http://blog.csdn.net/acm_cxlove/article/details/7835016 里面说 如果先手第一次取的石子数yf[k-1]/3则这小堆所剩的石子数小于2y即后手可以直接取完 这是对的但是他为什么没有讨论y f[k-1]/3的情况嘞 然后又找到一篇证明http://yjq24.blogbus.com/logs/46150651.html 前面还好但是最后那个不等式我又是看得不明不白的。不知道i,j分别代表什么的下标_ 于是还是感慨一下看论文找证明还是“帆 樯”看英文资料里面的证明十分简洁严谨。 1 #include cstdio2 #include algorithm3 using namespace std;4 typedef long long LL;5 6 const LL maxn (1LL 31);7 LL a[50];8 9 int main()
10 {
11 a[0] 1, a[1] 2;
12 for(int i 2; a[i-1] maxn; i)
13 a[i] a[i-1] a[i-2];
14 LL n;
15 while(scanf(%lld, n) 1 n)
16 {
17 int i lower_bound(a, a 45, n) - a;
18 printf(%s\n, a[i] n ? Second win : First win);
19 }
20
21 return 0;
22 } 代码君 转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4418186.html
