内容简介：假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。同时假设你和你的朋友都足够聪明，每次都能采取最优策略。
D64 292. Nim Game
题目链接
题目分析
假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。
同时假设你和你的朋友都足够聪明，每次都能采取最优策略。
现给定一个石头数量，判断你最终是否能取得胜利。
思路
我们先从少一点开始推广到n个石头。
如果有1～3颗石头，因为规定了是你开始、还假设会采取最优策略，那么你是能获胜的。也即，对方不会在拿走石头后剩下1
假设有4颗石头。
你拿1颗，会剩下3颗。对方全拿， 对方赢 。
你拿2颗，会剩下2颗。对方全拿， 对方赢 。
你拿3颗，会剩下1颗。对方全拿， 对方赢 。
即，怎么拿都是你输。
假设有5颗石头。
你拿1颗，会剩下4颗。
对方拿走1颗，剩下3颗给你，你全拿，你赢。
对方拿走2颗，剩下2颗给你，你全拿，你赢。
对方拿走3颗，剩下1颗给你，你全拿，你赢。
你拿2颗，会剩下3颗。对方全拿， 对方赢 。
你拿3颗，会剩下2颗。对方全拿， 对方赢 。
因此，这一轮你会选择拿1颗，剩下4颗。
假设有6颗石头。
你拿1颗，会剩下5颗。
对方拿走1颗，剩下4颗给你，参考一开始就只有4颗的情况， 对方赢 。
对方拿走2颗，剩下3颗给你，你全拿，你赢。
对方拿走3颗，剩下2颗给你，你全拿，你赢。
你拿2颗，会剩下4颗。
对方拿走1颗，剩下3颗给你，你全拿，你赢。
对方拿走2颗，剩下2颗给你，你全拿，你赢。
对方拿走3颗，剩下1颗给你，你全拿，你赢。
你拿3颗，会剩下3颗。对方全拿， 对方赢 。
因此，这一轮你会选择拿2颗，剩下4颗。
假设有7颗石头。
你拿1颗，会剩下6颗。
对方拿走1颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。
对方拿走2颗，剩下4颗给你， 对方赢 。
对方拿走3颗，剩下3颗给你，你全拿，你赢。
你拿2颗，会剩下5颗。
对方拿走1颗，剩下4颗给你， 对方赢 。
对方拿走2颗，剩下3颗给你，你全拿，你赢。
对方拿走3颗，剩下2颗给你，你全拿，你赢。
你拿3颗，会剩下4颗。
对方拿走1颗，剩下3颗给你，你全拿，你赢。
对方拿走2颗，剩下2颗给你，你全拿，你赢。
对方拿走3颗，剩下1颗给你，你全拿，你赢。
因此，这一轮你会选择拿3颗，剩下4颗。
假设有8颗石头。
你拿1颗，会剩下7颗。
对方拿走1颗，剩下6颗给你，参考一开始就只有6颗的情况，你赢。
对方拿走2颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。
对方拿走3颗，剩下4颗给你， 对方赢 。
你拿2颗，会剩下6颗。
对方拿走1颗，剩下5颗给你，你赢。
对方拿走2颗，剩下4颗给你， 对方赢。
对方拿走3颗，剩下3颗给你，你全拿，你赢。
你拿3颗，会剩下5颗。
对方拿走1颗，剩下4颗给你， 对方赢。
对方拿走2颗，剩下3颗给你，你全拿，你赢。
对方拿走3颗，剩下2颗给你，你全拿，你赢。
因此，必输无疑。
我们可以得出规律。当剩下的石头为4的整数倍、双方都采取最优策略时，先下手的一方为输家。
因此这个题目就很简单了，只要判断给定的数字是否是4的整数倍即可。
最终代码
<?php
class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function canWinNim($n) {
return $n%4!=0;
}
}
若觉得本文章对你有用，欢迎用 爱发电 资助。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
敏捷软件开发
Robert C.Martin,、Micah Martin / 邓辉、孙鸣 / 人民邮电出版社 / 2010-12 / 79.00元
要想成为一名优秀的软件开发人员，需要熟练应用编程语言和开发工具，更重要的是能够领悟优美代码背后的原则和前人总结的经验——这正是本书的主题。本书凝聚了世界级软件开发大师Robert C. Martin数十年软件开发和培训经验，Java版曾荣获计算机图书最高荣誉——Jolt大奖，是广受推崇的经典著作，自出版以来一直畅销不衰。 不要被书名误导了，本书不是那种以开发过程为主题的敏捷软件开发类图书。在......一起来看看 《敏捷软件开发》 这本书的介绍吧!
