天津做再生资源交易的网站,外资企业可以在中国境内做网站吗,网站销售,音乐网站开发的目的尼姆游戏是一种两个人玩的回合制数学策略游戏。游戏者轮流从一堆棋子#xff08;一共有好几堆#xff0c;一次只能从其中一堆拿。#xff09;#xff08;或者任何道具#xff09;中取走一个或者多个#xff0c;最后不能再取的就是输家。当指定相应数量时#xff0c;一堆…尼姆游戏是一种两个人玩的回合制数学策略游戏。游戏者轮流从一堆棋子一共有好几堆一次只能从其中一堆拿。或者任何道具中取走一个或者多个最后不能再取的就是输家。当指定相应数量时一堆这样的棋子称作一个尼姆堆。
尼姆游戏有很多形式也可以说很多游戏的原型都是尼姆游戏。
单堆尼姆游戏
假设我们现在有一堆n枚棋子两个玩家轮流从堆中拿走至少1枚至多m枚棋子。每次拿走的棋子数都可以不同但能够拿走的上下限数量是不变的。如果每个玩家都做出了最佳选择哪个玩家能够拿到最后一枚棋子是先走的还是后走的
我们认为n0是一个败局因为接下来要走的人是第一个无路可走的人。
1. 任何1 s m(s为堆中剩余棋子)的局面都是胜局因为玩家A总能取走所有棋子同时得到最后一枚棋子
2. s m 1的局面是一个败局因为无论玩家A取走几枚棋子总能把对方推向胜局即第一种情况。
3. 那么任意 1 (m1) s m (m1)都是一个胜局因为无论玩家A怎么走都会给对面一个必输的局面。
根据数学归纳法当且仅当n不是m1的倍数时n个棋子的实例是一个胜局胜利的策略是每次拿走n mod (m1)个棋子如果背离这个策略则会将胜局留给对手。
总结如果棋子数量n为m1的倍数那么先手的人是一个败局否则先手的人是一个胜局当然前提是双方都知道最优策略。 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int m in.nextInt();if (n % (m1) 0) {System.out.println(后手赢);} else {System.out.println(先手赢);}}
}当然除了单堆尼姆游戏还有多对尼姆游戏巧妙的是对于多堆尼姆游戏的解来说它基于堆中棋子数的二进制表示。、多堆尼姆游戏
假设我们现在有数目分别为3、 4、 5的三堆棋子两个玩家轮流从其中拿走至少1枚至多为一整堆的棋子数。每次拿走的棋子数都可以不同但能够拿走的下限数量是不变的。如果每个玩家都做出了最佳选择哪个玩家能够拿到最后一枚棋子是先走的还是后走的
我们需要求出每堆棋子数的二进制数位和(也叫Nim和)即对每一位分别求和并忽略进制。
实际上当Nim和中包含至少一个1时该实例为一个胜局相应的当Nim和中只包含0时该实例为一个败局 所以对于先走的玩家来说这是一个胜局走法为改变三个位串中的一个使Nim和仅包含0例如从第一个堆中拿走2个。
