(HDU - 2516)取石子游戏(斐波那契博弈)

题目链接:取石子游戏 - HDU 2516 - Virtual Judge (ppsucxtt.cn)

题目是中文的,我在这就不翻译了。

这道题目是斐波那契博弈的模板,当且仅当给定的石子数是斐波那契数时后手赢,其余情况均是先手赢。还不明白斐波那契博弈的小伙伴可以看下我之前写的博客,在这附上博客地址:

(34条消息) 博弈论总结_AC__dream的博客-CSDN博客

思路比较简单,直接上代码:

#include
#include
#include
#include
#include
using namespace std;
int main()
{
	int n;
	while(1)
	{
		scanf("%d",&n);
		if(n==0) break;
		bool flag=false;
		int a=1,b=1,c;
		while(a+b<=n)
		{
			if(a+b==n)
			{
				flag=true;
				break;
			}
			c=a+b;
			a=b;b=c;
		}
		if(flag) puts("Second win");
		else puts("First win");
	}
	return 0;
}

你可能感兴趣的