拿火柴游戏

题目

桌子上有一堆火柴，游戏开始时共有n根火柴，两个玩家轮流拿走1、2、3、4根火柴（选择一种方案拿），拿走最后一根火柴的玩家为获胜方。请问先走的玩家设计一个制胜的策略（如果该策略存在）

思路

若桌子上只有只有1-4根火柴，那么先手必赢； 若桌子上只有5根火柴，那么无论先手拿几根都必输；

也就是意味着先手若要赢，那么快拿到最后的时候，要出现这样一种情况：先手一拿完，巧好剩5根，这才能保证先手必赢；

那么问题就成了怎么出现刚才说的那种情况，其实只需重复一下上面的过程： 若桌子上只有只有6-9根火柴，那么先手可以保证这堆火柴巧好剩5根，回到上面，先手必赢； 若桌子上只有10根火柴，那么无论先手拿几根都必输； …

所以，大家应该已经看出规律了，如果火柴数一开始就是5的整数倍，那么先手是没有必赢策略的（后手倒有），只有火柴数一开始就不是5的整数倍，那么先手只需要拿掉几根火柴，使剩余的火柴数是5的整数倍，就可以保证必赢；

然后有人可能会说，看是看懂了，问题是咋想到的了，emmm,我只能说我是根据化繁为简的原则，一开始考虑的火柴数先化到最简单的情形，然后逐步加深。

对于可能有些题目允许拿火柴的数量不一样，可自行调整修改。

代码

#include<iostream> #include<stdio.h> #include<stdlib.h> #include<time.h> using namespace std; int main(){ srand(time(NULL));//随机种子 printf("输入总得火柴数："); int n;//火柴数 scanf("%d", &n); if(n%5 == 0){ printf("先走玩家无法必赢"); } else{ printf("先走玩家可以必赢，下面是必赢策略：\n"); int m=n; while(m>0){ printf("先手拿：%d\n", m%5); m -= (m%5); if(m>0){//判断后手是否还有火柴可以拿 int temp = rand()%4 + 1;//后手随机拿1-4根火柴 printf("后手拿：%d\n", temp); m -= temp; } } return 0; }