前言
一道斐波那契博弈的题目，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是斐波那契数，那么先手必输，如果不是，先手必胜。
代码里用到了斐波那契数列的通项公式来处理数据
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <stdio.h> #include <math.h> int main(){ float n; int kase = 0; scanf("%f", &n); while(n != 0){ for(int i = 0;i < 50; i++){ float a = (1/sqrt(5))*(pow((1+sqrt(5))/2,i)-pow((1-sqrt(5))/2,i)); if(n == a){ printf("Second win\n"); kase = 1; break; } } if(!kase) printf("First win\n"); kase = 0; scanf("%f", &n); } return 0; } |
总结
关于这个博弈的证明有些复杂，于是干脆当成结论记下来吧。