博弈

2020-03-07

字数统计: 927字 | 阅读时长≈ 4分钟

纳什博弈、威佐夫博弈、尼姆博弈的总结

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

题目大意：

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

解题思路：

斐波那契博弈，n为斐波那契数时先手必败，用map记录一下斐波那契数即可。

题目大意：

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

解题思路：

威佐夫博弈，设（a，b），a < b，若a / b最接近（sqrt（5） - 1）/ 2，则（a，b）为必败态。

1	#include <bits/stdc++.h>
2	using namespace std;
3	int main()
4	{
5	double a, b, c;
6	while(scanf("%lf %lf", &a, &b) != EOF)
7	{
8	if(a > b){c = a; a = b; b = c;}
9	c = (sqrt(5) - 1.0) / 2.0;
10	if(abs((a + 1) / b - c) > abs(a / b - c) && abs((a - 1) / b - c) > abs(a / b - c))
11	{
12	printf("0\n");
13	}
14	else printf("1\n");
15	}
16	return 0;
17	}

题目大意：

m堆石子,两人轮流取.只能在1堆中取.取完者胜.先取者负输出No.先取者胜输出Yes,然后输出怎样取子.例如5堆 5,7,8,9,10先取者胜,先取者第1次取时可以从有8个的那一堆取走7个剩下1个,也可以从有9个的中那一堆取走9个剩下0个,也可以从有10个的中那一堆取走7个剩下3个.

解题思路：

尼姆博弈，即所有数异或和为0是必败态，否则为必胜态，首先异或一遍，为0输出No，不为零输出Yes，然后遍历石子数，sum ^= a[i]，则sum为除第i堆石子外的异或和，易知sum ^ sum = 0，故当sum < a[i]时，第i堆石子可已走a[i] - sum个石子，使对手必败。