网站设计的基本步骤,商丘市有没有做网站,深圳高端网站建设,网站群建设公司排行榜6你和你的朋友#xff0c;两个人一起玩 Nim 游戏#xff1a;桌子上有一堆石头#xff0c;每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人#xff0c;每一步都是最优解。 编写一个函数#xff0c;来判断你是否可以在给定石头…你和你的朋友两个人一起玩 Nim 游戏桌子上有一堆石头每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人每一步都是最优解。 编写一个函数来判断你是否可以在给定石头数量的情况下赢得游戏。
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头那么你永远不会赢得比赛因为无论你拿走 1 块、2 块 还是 3 块石头最后一块石头总是会被你的朋友拿走。这道题是一道纯推理题最红的结果是如果剩余 n 为 4 的倍数则先手必输否则先手必赢。为什么呢
其实很简单如果剩余 4则无论先手如何取剩余都会在 1-3 之间后手可以一次取完结局注定失败
所以如果此时剩余数量为 4 的倍数则无论先手如何取后手都可以控制每次递减的数为 4。
而如果先手时数量为 4n k 1 k 3则先手可以直接将 k 去掉剩余 4n后手在取石头的时候面临的是 4n则其必输。
代码如下
class Solution {
public:bool canWinNim(int n) {if (n % 4 0) {return false;} else {0return true;}}
};
