新浪博客

取石子游戏(斐波那契数列)

2016-03-14 15:31阅读：

http://blog.sina.cn/dpool/blog/u/3171881794

来源为今年的华为面试题，第二题。
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出'2'.先取者胜输出'1'.​
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
例子：输入3，输出2
【分析】
首先进行基本的分析，要不让后取者一次取完剩余所有的，先取者一次最多取剩余数-1的的1/3，即先取数<(n-1)/3​
然后进行枚举推导
n =3时，先取者只能取1，输出“2”
n=4时，先取者取1，此时角色转换，后取者变成先取者，剩下石子数为3，此时的后取者，也就是最初的先取者必定获胜，故输出'1'​
n=5 先取数<=1，取1，演变成上述n=4的情况，输出'2'
n=6 先取数<=1，取1，输出'1'
n=7 先取数可取​1或是2，若先取者取1，则输出'2'，若先取者取2，则输出'1'，既然存在能获胜的情况，先取者当然会选择能让自己获胜的取法（前提），故输出'1'
n=8时，先取者可取1或是2，若取1，n=7，输出'2'，若取2，n=6，也是输出2，故结果为'2'
n=9-11时，先取者分别可取1,2,3，使n=8，来达到获胜的条件
n=12时，先取者取1，从而限定了后取者只能取1和2两种情况，后取者此时无论取1还是2，先取者都可以对应的取2或是1，来达到n=8时后取者和先取者的角色转换，从而获胜。
n=13时，先取者可取1,2,3,4，达不到n=8，先取者必然负。​
......
​ps:本人在作答时，简单的考虑到了先取数<(
n-1)/3时才存在获胜的可能性，故而每次都强行取走理论上最大可取的值，导致了规律越推越远，在n=10时，只考虑了先取者取3的情况，也就是演变成n=7时，此时输出为'2'了，而未考虑到先取者应最大可能的去争胜，先取2，转变成n=8的情况，这时输出结果则为'1'，就此偏离正道。
通过以上的推导，可知在n=3,5,8,13时，先取者必败。观察可知，当n为斐波那契(Fibonacci)数时，先取者负，其他情况下，先取者胜。
【理论论证】（转载）
用第二数学归纳法证明：
为了方便，我们将n记为f[i]。
1、当i=2时，先手只能取1颗，显然必败，结论成立。
2、假设当i<=k时，结论成立。
则当i=k+1时，f[i] = f[k]+f[k-1]。
则我们可以把这一堆石子看成两堆，简称k堆和k-1堆。
（一定可以看成两堆，因为假如先手第一次取的石子数大于或等于f[k-1]，则后手可以直接取完f[k]，因为f[k] < 2*f[k-1]）
对于k-1堆，由假设可知，不论先手怎样取，后手总能取到最后一颗。下面我们分析一下后手最后取的石子数x的情况。
如果先手第一次取的石子数y>=f[k-1]/3，则这小堆所剩的石子数小于2y，即后手可以直接取完，此时x=f[k-1]-y，则x<=2/3*f[k-1]。
我们来比较一下2/3*f[k-1]与1/2*f[k]的大小。即4*f[k-1]与3*f[k]的大小，对两值作差后不难得出，后者大。
所以我们得到，x<1/2*f[k]。
即后手取完k-1堆后，先手不能一下取完k堆，所以游戏规则没有改变，则由假设可知，对于k堆，后手仍能取到最后一颗，所以后手必胜。
即i=k+1时，结论依然成立。
对于个数不是​Fibonacci数的，按照齐肯多夫定理：任何正整数可以表示为若干个不连续的Fibonacci数之和。即n = f[a1]+f[a2]+……+f[ap]。（a1>a2>……>ap），先取者取f[ap]，由于an不连续,故f[a(p-1)]>af[ap]，后取者只能取f[a(p-1)]这一堆，且不能一次取完。此时后取者相当于面临这个子游戏（只有f[a(p-1)]这一堆石子，且后手先取）的必败态，即先取者一定可以取到这一堆的最后一颗石子。以此递推，先取者一定能取到最后一颗。
【结论】
通过以上论证，最终得出结论，当n为Fibonacci数时，先取者负，反之，先取者胜。
故原问题转换成判断n是否为Fibonacci​数。
参考代码如下：
#include
#include
using namespace std;


int fib(int n)
{
if (n == 1 || n == 2)
return 1;
else return fib(n - 1) + fib(n - 2);


}
int main()
{
int n,i;
cin >> n;
for (i = 1; fib(i) < n; i++);


if (fib(i) == n)
cout << 'yes' << endl;
else
cout << 'no' << endl;
}


后来了解到取石子问题是属于博弈论中的一类问题。后续将继续更新更多的取石子类别




我的更多文章

下载客户端阅读体验更佳

APP专享