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 win\n");
else
printf("Bob will win\n");
}
system("pause");
return 0;
}