当前访客身份:游客 [ 登录  | 注册加入尚学堂]
直播

flamen

拥有积分:3
这家伙太懒,还没有签名!

博客分类

笔记中心

课题中心

提问中心

答题中心

解答题中心

leetcode笔记:Nim Game

flamen 发表于 1年前 (2015-12-29 11:10:19)  |  评论(0)  |  阅读次数(630)| 0 人收藏此文章,   我要收藏   

一. 题目描述

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

二. 题目分析

题目的大意如下:

你正在和你的朋友们玩下面这个Nim游戏:有一堆石头放在桌上,你每次可以从中拿走1到3颗。谁消除掉最后一个石头即为赢家。假设你是第一轮开始取石头。

现在你们游戏中的每个人都有着非常聪明的头脑和绝佳的策略。写一个函数,对与一个给定的石头数目,算出你是否可以赢得这场比赛。

例如,如果石堆中有4颗石头,那么你永远也无法赢得比赛:无论你移除了1、2或3颗石头,最后1颗石头都会被你的朋友所拿走。

更多关于Nim Game的解释,可参照百科:http://baike.baidu.com/link?url=uxWV7mNdl-jkDWL6qj06zSX9Luvazbck4XqDo6IEcNgh2lNagWOmn7FyiN_YrjPHyaAyGeCF6yz2SwC-Irb2X_

其实对于这单一的问题,可以使用一行代码解决。因为例子中当且仅当出现了4的倍数,先手必输,其余情况先手都可以获胜。

三. 示例代码

class Solution
{
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
}

四. 小结

这道题可以说毫无难度,但也可以经过适当变化,变成复杂的题目。

分享到:0
关注微信,跟着我们扩展技术视野。每天推送IT新技术文章,每周聚焦一门新技术。微信二维码如下:
微信公众账号:尚学堂(微信号:bjsxt-java)
声明:博客文章版权属于原创作者,受法律保护。如果侵犯了您的权利,请联系管理员,我们将及时删除!
(邮箱:webmaster#sxt.cn(#换为@))
北京总部地址:北京市海淀区西三旗桥东建材城西路85号神州科技园B座三层尚学堂 咨询电话:400-009-1906 010-56233821
Copyright 2007-2015 北京尚学堂科技有限公司 京ICP备13018289号-1 京公网安备11010802015183