新浪微博 登陆  注册   设为首页 加入收藏

学PHP >> PHP >> NIM游戏(取m堆游戏)

NIM游戏(取m堆游戏)

查看次数2675 发表时间2013-06-04 23:41:38

  这个游戏是说,有m堆硬币,两个人分别来取,每人每次能从任意一堆中去任意多的硬币(但只能从一堆中取),现在告诉你具体每堆的数量,然后让你判断先取者胜,还是后取者胜。解:设每堆的数量为:a1, a2...

  这个游戏是说,有m堆硬币,两个人分别来取,每人每次能从任意一堆中去任意多的硬币(但只能从一堆中取),现在告诉你具体每堆的数量,然后让你判断先取者胜,还是后取者胜。

解:

设每堆的数量为:a1, a2, a3,.....am;

由于每一个整数都能表示成二进制数,那么将这些数表示成二进制:

a1 = b(m-1)b(m-2)b(m-3)....b0;

a2 = c(m-1)c(m-2)c(m-3)....c0;

..........(位数不够的用零补齐)

现在设 :   

 若  b(m-1) + c(m-1) + ...... == 偶数, 则称第 j 位是平衡的,否则是不平衡的。若在某状态下,所有位都是平衡的,则该状态为平衡状态,否则为非平衡状态。

现在,该问题的一个解释:初始状态为平衡状态时,后取者胜,否则先取者胜。

原因:

当初始状态状态为非平衡状态时,假设最大非平衡状态位为第 j 位,那么先取者一定能从第 j 位是1的某一堆中去一定数量的硬币使状态变为平衡状态。现在后取者无论怎么取都得给先取者留下不平衡的状态......然后先取者再将其变平衡即可,这样往复循环 先取者最终将状态变为 所有都为零的平衡状态。

当初始状态为平衡状态,调换顺序即可。

游戏在HDOJ上有一题http://acm.hdu.edu.cn/showproblem.php?pid=2176

代码如下:

#include <iostream>
using namespace std;

int main(){
	int a[200000], n, t;

	while( cin >> n, n ){
		t = 0;
		for( int i = 0; i < n; i++ ){
			cin >> a[i];
			t ^= a[i];
		}

		if( t == 0 ){
			cout << "No" << endl;
		}else{
			cout << "Yes" << endl;
			for( int i = 0; i < n; i++ ){
				if( ( t ^ a[i] ) < a[i] ){
					cout << a[i] << " " << ( t ^ a[i] ) << endl;
				}
			}
		}
	}
}


 


(转发请注明转自:学PHP)    


  相关推荐




  发表评论
昵称:
(不超过20个字符或10个汉字)
内容: