内容简介：假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿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;
}
}
若觉得本文章对你有用，欢迎用 爱发电 资助。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Windows内核原理与实现
潘爱民 / 电子工业出版社 / 2010年4月 / 99.00元
本书从操作系统原理的角度，详细解析了Windows如何实现现代操作系统的各个关键部件，包括进程、线程、物理内存和虚拟内存的管理，Windows中的同步和并发性支持，以及Windows的I/O模型。在介绍这些关键部件时，本书直接以Windows的源代码（WRK, Windows Research Kernel）为参照，因而读者可以了解像Windows这样的复杂操作系统是如何在x86处理器上运行的。 ......一起来看看 《Windows内核原理与实现》 这本书的介绍吧!
