首页 > ACM题库 > HDU-杭电 > HDU 1846 Brave Game-博弈论-[解题报告] C++
2013
12-23

HDU 1846 Brave Game-博弈论-[解题报告] C++

Brave Game

问题描述 :

十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫《勇敢者的游戏》(英文名称:Zathura),一直到现在,我依然对于电影中的部分电脑特技印象深刻。
今天,大家选择上机考试,就是一种勇敢(brave)的选择;这个短学期,我们讲的是博弈(game)专题;所以,大家现在玩的也是“勇敢者的游戏”,这也是我命名这个题目的原因。
当然,除了“勇敢”,我还希望看到“诚信”,无论考试成绩如何,希望看到的都是一个真实的结果,我也相信大家一定能做到的~

各位勇敢者要玩的第一个游戏是什么呢?很简单,它是这样定义的:
1、  本游戏是一个二人游戏;
2、  有一堆石子一共有n个;
3、  两人轮流进行;
4、  每走一步可以取走1…m个石子;
5、  最先取光石子的一方为胜;

如果游戏的双方使用的都是最优策略,请输出哪个人能赢。

输入:

输入数据首先包含一个正整数C(C<=100),表示有C组测试数据。
每组测试数据占一行,包含两个整数n和m(1<=n,m<=1000),n和m的含义见题目描述。

输出:

如果先走的人能赢,请输出“first”,否则请输出“second”,每个实例的输出占一行。

样例输入:

2
23 2
4 3

样例输出:

first
second

博弈问题除了有趣之外,我也想不到有什么可以形容了,知识有用之余,又可以骗下那些无知的小朋友(奸笑ing…………)

这个又是经典的说,叫做巴什博弈,英文叫Bash Game。嗯嗯,大概又是一个叫Bash的人想到的

所谓的Bash Game就是说:在只有一堆n个的物品,两人轮流从中取物品,每次至少取一个,至多取m个,最后是谁取光物品谁就是胜利者。

        先假设,n = m+1.很明显无论当前玩家从中取多少物品,都无法否认他将要输的命运,这是一个必败点。我们的目的总是为了导致必败点,

假设 m+1 < n < 2(m+1),那么当前玩家只要从中取(n-(m+1))就可以导致必败点(m+1);又假设2(m+1) < n < 3(m+1),当前玩家只要从堆中取出

(n-2(m+1))的物品,堆中剩下2(m+1)的物品,无论对手接下来取多少物品(1 <= x <= m),剩下的物品数s,m+1 < s < 2(m+1),我们又可以取走相应数

量的物品使堆中剩下m+1 个物品,所以2(m+1)也是一个必败点;如此类推堆中物品数 S = k(m+1)(k = 1,2,3……)为必败点。

            最后得出在这个游戏中:

                            1.如果m >= n,先手者必胜

                             2.如果n = k(m+1)+x (k = 1,2,3……;x <= m),先手者胜

                             3.如果n = k(m+1),后手者胜

然后…………………………你懂的


#include<iostream>

using namespace std;

int main()
{
	int cCase;
	cin >>cCase;
	while(cCase--){
		int n,m;
		bool flag = true;
		cin >>n >>m;
		if(m >= n)
			flag = true;
		else if(n%(m+1))
			flag = true;
		else
			flag = false;
		if(flag)
			cout <<"first" <<endl;
		else
			cout <<"second" <<endl;
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/hzxph/article/details/6660317