天津市建行网站,网站开发毕业设计周志,如何介绍自己的网页,建筑市场网给定n堆石子#xff0c;每次每人能从一堆石子中取若干个石子#xff08;不能不取#xff09;#xff0c;最后不能取石子者败 对于这个游戏#xff0c;我们要判断的是#xff0c;给定局势下#xff0c;先手者胜还是败 设先手胜的局势为N-postion#xff0c;先手败的局势… 给定n堆石子每次每人能从一堆石子中取若干个石子不能不取最后不能取石子者败 对于这个游戏我们要判断的是给定局势下先手者胜还是败 设先手胜的局势为N-postion先手败的局势为P-postion 可以移动到P-postion的局势叫做N-postion只能移动到N-postion的局势叫做P-postion。 1、只有一堆的情况下先手胜 2、只有两堆 a、数目相等的局势先手败因为不管先手怎么取后手都能在另一堆中复制先手的取法 b、数目不相等的局势先手胜先手可以在石子多的那一堆取走一定的石子使得两堆的石子数相等然后参考情况a分析可知先手胜 3、两堆以上的情况。将局势分为两个子局势xy 那么来分析一下局势的加法与异或之间的关系 将局势分为两个子局势n和m如果两个子局势相同则表示nm将局势如果可以先手胜利成为n胜或m胜 局势异或等于0表示先手败不等于0表示先手胜 若n胜m胜 如果nm ,n^m0, 如果n!m, n^m!0 ,说明该情况下的局势加法满足异或 若n胜m负 先手者在n局势先手获得胜利然后使得后手者在m局势先手获得失败所以先手胜 n!0,m0, n^m!0,说明该情况下的局势加法满足异或 若n负m胜 同上 若n负m负 先手者在n局势取得失败然后又在m局势先手取得使得所以最终失败。 n0,m0,n^m0, 说明该情况下的局势加法满足异或 所以Nim游戏的判断是否先手胜就变成了判断n堆石子的异或是否不等于0 那么怎么获得必胜策略是怎么走的呢即将某堆得石子取走k个使得的石子异或等于0 设有n堆石子a1,a2,...ai...an 对于ai取得另外n-1堆得石子的异或s 如果 ai s , 那么k ai - s 这样子 ai-k)s 即 ai^s0 转载于:https://www.cnblogs.com/justPassBy/p/4366524.html
