减治法解决尼姆（Nim）游戏/拈游戏问题（JAVA）

编程基础 • 2024-12-21 23:27 • 阅读 13

尼姆游戏是一种两个人玩的回合制数学策略游戏。游戏者轮流从一堆棋子（一共有好几堆，一次只能从其中一堆拿。）（或者任何道具）中取走一个或者多个，最后不能再取的就是输家。当指定相应数量时，一堆这样的棋子称作一个尼姆堆。

尼姆游戏有很多形式，也可以说很多游戏的原型都是尼姆游戏。

单堆尼姆游戏：

假设我们现在有一堆n枚棋子，两个玩家轮流从堆中拿走至少1枚，至多m枚棋子。每次拿走的棋子数都可以不同，但能够拿走的上下限数量是不变的。如果每个玩家都做出了最佳选择，哪个玩家能够拿到最后一枚棋子？是先走的还是后走的？

我们认为n=0是一个败局，因为接下来要走的人是第一个无路可走的人。

1. 任何1 <= s <= m(s为堆中剩余棋子)的局面都是胜局，因为玩家A总能取走所有棋子，同时得到最后一枚棋子

2. s = m + 1的局面是一个败局，因为无论玩家A取走几枚棋子，总能把对方推向胜局，即第一种情况。

3. 那么任意 1 + (m+1) <= s <= m +(m+1)都是一个胜局，因为无论玩家A怎么走，都会给对面一个必输的局面。

根据数学归纳法，当且仅当n不是m+1的倍数时，n个棋子的实例是一个胜局，胜利的策略是每次拿走n mod (m+1)个棋子，如果背离这个策略，则会将胜局留给对手。

总结：如果棋子数量n为m+1的倍数，那么先手的人是一个败局，否则先手的人是一个胜局，当然前提是双方都知道最优策略。

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 % (m+1) == 0) { System.out.println("后手赢"); } else { System.out.println("先手赢"); } } }

当然除了单堆尼姆游戏，还有多对尼姆游戏，巧妙的是，对于多堆尼姆游戏的解来说，它基于堆中棋子数的二进制表示。、

多堆尼姆游戏：

假设我们现在有数目分别为3、 4、 5的三堆棋子，两个玩家轮流从其中拿走至少1枚，至多为一整堆的棋子数。每次拿走的棋子数都可以不同，但能够拿走的下限数量是不变的。如果每个玩家都做出了最佳选择，哪个玩家能够拿到最后一枚棋子？是先走的还是后走的？

我们需要求出每堆棋子数的二进制数位和(也叫Nim和)，即对每一位分别求和并忽略进制。

实际上，当Nim和中包含至少一个1时，该实例为一个胜局；相应的，当Nim和中只包含0时，该实例为一个败局

所以对于先走的玩家来说，这是一个胜局，走法为改变三个位串中的一个，使Nim和仅包含0，例如从第一个堆中拿走2个。

今天的文章减治法解决尼姆（Nim）游戏/拈游戏问题（JAVA）分享到此就结束了，感谢您的阅读。

减治法解决尼姆（Nim）游戏/拈游戏问题（JAVA）

相关推荐