（2017腾讯实习生校招笔试题）Calvin和David正在玩取纽扣游戏，桌上一共有16个纽扣，两人轮流来取纽扣，每人每次可以选择取1个或3个或6个(不允许不取)，谁取完最后的纽扣谁赢。Cavin和David都非常想赢得这个游戏，如果Cavin可以先取，Cavin的必胜策略下第一步应该取
A、1个
B、3个
C、6个
D、Cavin没有必胜策略
解析：这道题是Nim游戏的变种，Nim游戏是博弈论中最经典的模型（之一）。
根据博弈论的性质：对于巴什博弈，存在必胜点和必败点，是指在当前这个点上的先手玩家是“必胜”(指的是采取必胜策略下的必胜)还是必败。对于一个点，如果它的下一步全是必胜点，那么显然无论它如何走都是让对手进入必胜点，所以当前这个点就是必败点；如果下一步中存在一个必败点，那么当前这一步的玩家就可以选择让对手进入这个必败点的走法，所以当前这个点就是是必胜点。
对这题来说，显然0的时候是必败点；看1，只能选择拿走1个，变成0，0是必败点，1可以到达必败点，所以1是必胜点；然后看2，2的下一步只能选择拿走1个变成1，1是必胜点，2只能到达必胜点，所以2是必败点；3的下一步2和0，都是必败点，3可以到达必败点，所以3是必胜点.......同理，当推到16的时候，下一步有三种走法，分别是15,13,10,由前面推理过程，15和10都是必胜点，只有13是必败点。因此先手应该选择拿走3个棋子，让对手进入必败点。
详细推理过程如下表(自上而下)：
| 必败点 | 必胜点 |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
| 11 | |
| 12 | |
| 13 | |
| 14 | |
| 15 | |
| 16 |
我们还可以用程序验证我们的答案，C++源码如下：
#include "iostream"
#include "vector"
#include "string.h"
using namespace std; int main()
{
int button_num = ; // 共有16个纽扣
int legal_get[] = { ,, }; // 每人每次可以选择取1个或3个或6个
bool win_point[]; // 标识剩下i个纽扣的局面下,是否为必胜点
int win_to_get[]; // 必胜点下,采用必胜策略该取几个纽扣 win_point[] = false; // 0是必败点
for (int i = ; i <= button_num; i++)
{
win_point[i] = false; // 初始化均为必败点
for (int j = ; j < ; j++)
{
if (legal_get[j] <= i && !win_point[i - legal_get[j]])// 若下一步中存在一个必败点,则当前这个点就是是必胜点。
{
win_point[i] = true;
}
if (win_point[i])
{
win_to_get[i] = legal_get[j]; // 记录下必胜点下,采用必胜策略该取几个纽扣让对手进入必败点
break;
}
}
}
if (win_point[button_num]) // 16为必胜点
{
cout << "Calvin有必胜策略,制胜的第一步应该取" << win_to_get[button_num] << "个纽扣" << endl;
}
else
cout << "Cavin没有必胜策略" << endl;
return ;
}
参考资料:http://www.guokr.com/blog/777525/
https://www.zhihu.com/question/42098847/answer/93624200