江西做网站哪家好,网页设计各个部分的尺寸,动力无限做网站怎样,重庆企业网络推广软件不要美化自己当初没有选择的那一条路 —— 24.4.7 Nim 游戏 你和你的朋友#xff0c;两个人一起玩 Nim 游戏#xff1a; 桌子上有一堆石头。你们轮流进行自己的回合#xff0c; 你作为先手 。每一回合#xff0c;轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者… 不要美化自己当初没有选择的那一条路 —— 24.4.7 Nim 游戏 你和你的朋友两个人一起玩 Nim 游戏 桌子上有一堆石头。你们轮流进行自己的回合 你作为先手 。每一回合轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢返回 true否则返回 false 。 示例 1 输入n 4
输出false
解释以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中你的朋友是赢家。示例 2 输入n 1
输出true示例 3 输入n 2
输出true提示 1 n 231 - 1 数学推理 思路与算法 让我们考虑一些小例子。显而易见的是如果石头堆中只有一块、两块、或是三块石头那么在你的回合你就可以把全部石子拿走从而在游戏中取胜如果堆中恰好有四块石头你就会失败。因为在这种情况下不管你取走多少石头总会为你的对手留下几块他可以将剩余的石头全部取完从而他可以在游戏中打败你。因此要想获胜在你的回合中必须避免石头堆中的石子数为 4 的情况。 我们继续推理假设当前堆里只剩下五块、六块、或是七块石头你可以控制自己拿取的石头数总是恰好给你的对手留下四块石头使他输掉这场比赛。但是如果石头堆里有八块石头你就不可避免地会输掉因为不管你从一堆石头中挑出一块、两块还是三块你的对手都可以选择三块、两块或一块以确保在再一次轮到你的时候你会面对四块石头。显然我们继续推理可以看到它会以相同的模式不断重复 n4,8,12,16,…基本可以看出如果堆里的石头数目为 4 的倍数时你一定会输掉游戏。 如果总的石头数目为 4 的倍数时因为无论你取多少石头对方总有对应的取法让剩余的石头的数目继续为 4 的倍数。对于你或者你的对手取石头时显然最优的选择是当前己方取完石头后让剩余的石头的数目为 4 的倍数。假设当前的石头数目为 x如果 x 为 4 的倍数时则此时你必然会输掉游戏如果 x 不为 4 的倍数时则此时你只需要取走 x mod 4个石头时则剩余的石头数目必然为 4 的倍数从而对手会输掉游戏。 class Solution {public boolean canWinNim(int n) {return n % 4 ! 0;}
}复杂度分析 时间复杂度O(1)。 空间复杂度O(1)。
