巴什博弈(巴什博弈小学奥数题及解答)干货满满

简介： 算法面试真题详解：硬币排成线描述有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一

简介： 算法面试真题详解：硬币排成线描述有 n 个硬币排成一条线两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止拿到最后一枚硬币的人获胜请判定 先手玩家 必胜还是必败?若必胜, 返回 true, 否则返回 false.。

样例1:输入:1输出:true样例2： 输入: 4输出: true解释: 先手玩家第一轮拿走一个硬币, 此时还剩三个. 这时无论后手玩家拿一个还是两个, 下一次先手玩家都可以把剩下的硬币拿完.挑战O(1) 时间复杂度且O(1) 存储。

算法博弈（巴什博弈）算法分析有 nn 个硬币排成一条线两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止拿到最后一枚硬币的人获胜本题要求判断先手玩家必胜还是必败我们可以根据 nn 的取值不同分为必败态和必胜态。

不妨先从小规模分析：(1)n=1n=1或n=2n=2时，先手玩家可以1次将所有硬币拿走，先手必胜(2)n=3n=3时，先手玩家拿走1个，则后手玩家拿走2个；先手玩家拿走2个，则后手玩家拿走1个；先手必败。

(3)n=4n=4时，先手玩家先拿走1个，此时对于后手玩家来说，他剩下3个，面临着(2)的情况根据(2)的分析，先手必胜(4)n=5n=5时，先手玩家先拿走2个，此时对于后手玩家来说，他面临着(2)的情况。

根据(2)的分析，先手必胜(5)n=6n=6时,无论先手玩家怎么取x个，后手玩家都可以取3-x个，另先手玩家剩下3个，面临着(2)的情况根据(2)的分析，先手必胜由上述分析当n=1,2,4,5n=1,2,4,5时为必胜态，当n=3,6n=3,6时为必败态。

同时，必胜态和必败态之间是有关联的对于先手玩家而言，只要他一开始面临的不是必败态，他每一步都可以将必败态留给后手玩家，最后获得胜利对于这个游戏来说，必败态是 n%3==0n%3==0，必胜态是 n%3≠0n%3≠0。

先手玩家每次取后都令 n%3==0n%3==0即可胜利拓展知识：* 这道题目属于 巴什博弈 模型：一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个最后取光者得胜先手玩家要必胜，则一开始 n%(m+1)≠0n%(m+1)≠0。

在本题中，m=2m=2复杂度分析时间复杂度：O(1)O(1)空间复杂度：O(1)publicclassSolution{ /** * @param n: An integer *

@return: A boolean which equals to true if the first player will win */publicbooleanfirstWillWin

(int n){ if (n % 3 != 0) returntrue; elsereturnfalse; } }原文：https://developer.aliyun.com/article/780282?spm=

5176.8068049.0.0.55746d19rtnqyn&groupCode=ai