问题描述:
输入:
zp来到了草系道馆,馆主给了他一个另类挑战。场馆的草地长满了草,草一共n个单位zp和馆主一起清理,每个人一次可以清理1,2或3个单位的草,谁先把草清理完谁就获胜另一个就失败!两人轮流清理,并且zp先动手!(两人都是很强的,都会做出最优选择)
输出:
多实例,第一行输入T(T<10),第二行输入草的总单位数n(1<=n<=100)
样例输入:
1 5
样例输出:
zp is winner!
原因分析:
博弈论问题 公平组合游戏
巴什博弈 Bash Game
有 1 堆石子,总个数是 n ,两名玩家轮流在石子堆中拿石子,每次至少取 1 个,至多取 m 个。取走最后一个石子的玩家为胜者。判定先手和后手谁胜。
总结: 若 n%(m+1)==0 则后手赢
情况1:当 n ≤ m 时,显然先手获胜
情况2: n = m + 1 时,先手最多可取走 m个,无论其取走多少个,剩下的后手总能一次取完。
情况3: n%(m+1)==0 则无论先手拿多少(比如x),后手总可以拿出 (m+1)-x
凑成 m+1 个,即最后一轮 同样也是剩m+1个,即情况2 ,后手赢
否则,先手可以先拿,取余后的余数,即把n%(m+1)==0的局面给后手,即先手赢
解决方案:
#include<stdio.h>
int main()
{scanf("%d%d", &n, &m);if (n % (m + 1))puts("zp is winner!");elseputs("curator is winner!");}