首页 > 其他 > 详细

LeetCode: Nim Game

时间:2016-11-21 23:32:01      阅读:253      评论:0      收藏:0      [点我收藏+]

这题其实不太好想,用到了博弈论

1,2,3 能赢

4 输

5,6,7 赢

8 输

9,10,11 赢

12 输

那么结论就是4的倍数就是输,其他情况就能赢。

为什么会是这样呢?很好解释,根源就在4会输,那么5,6,7就会凑到4,让对方输,那对方也会这么想,8的时候无论你拿1,2,3块对方都会凑4

如果是9,10,11,就拿1,2,3凑8,依次推论,只要第一次拿的时候凑到4的整数就行,下面对方拿多少还是凑到4的整数,最后到4对方还是要输。

1 public class Solution {
2     public boolean canWinNim(int n) {
3         return !(n % 4 == 0);
4     }
5 }

 

LeetCode: Nim Game

原文:http://www.cnblogs.com/yingzhongwen/p/6087241.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!