菜单

ACM 暑期培训题解 HDU-2516

八月 2, 2018 - 算法
ACM 暑期培训题解 HDU-2516

前言

一道斐波那契博弈的题目,SG函数理解有点困难,这个类型又很有特点,于是记录一下。

HDU-2516 取石子游戏

题目描述:

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出”Second win”.先取者胜输出”First win”.

Input

输入有多组.每组第1行是2<=n<2^31. n=0退出.

Output

先取者负输出”Second win”. 先取者胜输出”First win”.
参看Sample Output.

Sample Input

2
13
10000
0

Sample Output

Second win
Second win
First win

题目分析

这道题是很典型的斐波那契博弈问题,直接给出结论,如果n是斐波那契数,那么先手必输,如果不是,先手必胜。
代码里用到了斐波那契数列的通项公式来处理数据

代码实现

总结

关于这个博弈的证明有些复杂,于是干脆当成结论记下来吧。

标签:, ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注