Nim游戏与阶梯Nim博弈

48 阅读 0 评论 32 点赞

我是靠谱客的博主大气耳机，最近开发中收集的这篇文章主要介绍Nim游戏与阶梯Nim博弈，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

nim游戏

问题描述
一共有N堆石子,编号1~n,第i堆中有个a[i]个石子。
每一次操作Alice和Bob可以从任意一堆石子中取出任意数量的石子,
至少取一颗,至多取出这一堆剩下的所有石子。
两个人轮流行动,取光所有石子的一方获胜。Aice为先手.
给定a,假设两人都采用最优策略,谁会获胜?
问题分析
从简单情况分析，如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。
如果是三堆石子……好像很难分析了
直接说结论好了。
当a1^a2^a3^......^an==0时先手输。
当a1^a2^a3^......^an!=0时先手赢。

数学问题很神奇，完全没有道理的和异或运算扯上了关系。记住就好了吧。

阶梯nim博弈

问题描述

佐治亚和鲍勃决定玩一个自己发明的游戏。他们在纸上画一排网格，将网格从左到右编号1，2，3，.并在不同的网格上放置N个棋子，例如，如下图所示：

佐治亚和鲍勃轮流移动棋子。每次玩家会选择一个棋子，然后把它移到左边，而不超过任何其他棋子，或者越过左边的边缘。玩家可以自由选择棋子移动的步骤数，限制棋子必须至少移动一步，而一个网格最多只能包含一个棋子。不能移动的玩家输掉了比赛。

自从“女士优先”之后，乔治亚一直是第一名。假设佐治亚和鲍勃在比赛中都尽了最大的努力，也就是说，如果他们中的一个知道赢得比赛的方法，他或她就能做到这一点。

考虑到棋手们最初的位置，你能预测谁将最终赢得这场比赛吗？
输入

输入的第一行包含一个整数T(1<=T<=20)，测试用例数。接下来是T个病例。每个测试用例包含两行。第一行由一个整数N(1<=N<=1000)组成，表示棋子的数量。第二行包含N个不同的整数P1，P2.Pn(1<=PI<=10000)，这是n个棋手的初始位置。
输出量

对于每个测试用例，打印一行，“佐治亚将赢”，如果佐治亚将赢得比赛；“鲍勃会赢”，如果鲍勃将赢得比赛；否则‘不确定’。
样本输入

2
3
1 2 3
8
1 5 6 7 9 12 14 17
样本输出

Bob will win
Georgia will win

代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

void sort(int a[])
{
	int len = 0;
	int i, j, t;
	while (a[len] != 0)
	{
		len++;
	}
	for (i = 0; i < len - 1; i++)
	{
		for (j = 0; j < len - 1-i; j++)
		{
			if (a[j] > a[j + 1])
			{
				t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}
	}
 }
int main()
{
	int t, n;
	int arr[20][1000] = { 0 };
	int i, j;
	scanf("%d", &t);
	for (i = 0; i < t; i++)
	{
		scanf("%d", &n);
		for (j = 0; j < n; j++)
			scanf("%d", &arr[i][j]);
	}
	for (i = 0; i < t; i++)
		sort(arr[i]);
	for (i = 0; i < t; i++)
	{
		int rec = 0;
		int len = 0;
		while (arr[i][len] != 0)
		{
			len++;
		}
		if (len % 2 == 1)
		{
			for (j = 0; j < len; j = j + 2)
			{
				if (j == 0)
					rec ^= arr[i][0] - 1;
				else
					rec ^= arr[i][j] - arr[i][j - 1] - 1;
			}	
		}
		else
		{
			for (j = 1; j < len; j = j + 2)
			{
				rec ^= arr[i][j] - arr[i][j - 1] - 1;
			}
		}
		if(rec!=0)
			printf("Georgia will winn");
		else
			printf("Bob will winn");
	}
	system("pause");
	return 0;
}