首页 > 代码库 > Ferguson游戏
Ferguson游戏
考虑一个简单的游戏：
有两个盒子，其中一个装有m颗糖、另一个装有n颗糖，将这样的状态记为(m,n)。每次的移动是将其中一个盒子清空，把另一个盒子的一些糖拿到被清空的盒子里使得两个盒子至少各有一颗糖。两个操作者轮流进行操作，不能操作者败。需要判断一个状态是否先手必败。
按照k=m+n从小到大的顺序进行判断即可。
1 #include <cstdio> 2 // Ferguson，打印先手必败状态。 3 const int maxn = 100; 4 int winning[maxn][maxn]; // 1为先手必胜、0为先手必败 5 int main(){ 6 winning[1][1] = false; // (1,1)是游戏的唯一终态，此时先手必败 7 for(int k = 3 ; k < 20 ; k++) // k = n + m 8 for(int n = 1 ; n < k ; n++){ 9 int m = k - n;10 winning[n][m] = false;11 for(int i = 1 ; i < n ; i++) // 如果之后的存在一个状态是先手必败的12 if(!winning[i][n - i]) winning[n][m] = true;13 for(int i = 1 ; i < m ; i++)14 if(!winning[i][m - i]) winning[n][m] = true;15 if(n <= m && !winning[n][m])16 printf("%d %d\n",n,m);17 }18 return 0;19 }
Ferguson游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。