LeetCode 292. Nim游戏

2018-11-28 本文已影响0人逍遥ii

题目描述：

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:
输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

思路

简单题，巴什博弈。

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

对于巴什博弈，那么我们规定，如果最后取光者输，那么又会如何呢？

（n-1）%（m+1）==0则后手胜利

先手会重新决定策略，所以不是简单的相反行的

JAVA SOLUTION

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 == 0 ? false : true;
    }
}

扩展

威佐夫博奕

威佐夫博弈（Wythoff's game）：有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。

那么任给一个局势， (a，b)，怎样判断它是不是奇异局势呢？我们有如下公式：
$ak =\lfloor \frac{k}{2}(1+\sqrt{5}) \rfloor ，$

$bk= ak + k \space \space\space\space（k=0，1，2，...n)$

尼姆博奕

指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：
1)每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子；
2)如果谁取到最后一枚石子就胜。

判断当前局势是否为必胜（必败）局势：
把所有堆的石子数目用二进制数表示出来，当全部这些数按位异或结果为0时当前局面为必败局面，否则为必胜局面；

#include<iostream>  
using namespace std;  
int temp[ 20 ]; //火柴的堆数  
  
int main()  
{  
    int i, n, min;  
    while( cin >> n )  
    {  
        for( i = 0; i < n; i++ )  
            cin >> temp[ i ]; //第i个火柴堆的数量  
        min = temp[ 0 ];  
        for( i = 1; i < n ; i++ )  
            min = min^temp[ i ]; //按位异或  
        if( min == 0 )  
            cout << "Lose" << endl; //输  
        else  
            cout << "Win" << endl; //赢  
    }  
    return 0;  
}

斐波那契博弈

有一堆个数为n的石子，游戏双方轮流取石子，满足：
1)先手不能在第一次把所有的石子取完；
2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。
约定取走最后一个石子的人为赢家，求必败态。

这个游戏叫做斐波那契博弈，肯定和斐波那契数列： $f[n]：1,2,3,5,8,13,21,34,55,89,…$ 有密切的关系。如果试验一番之后，可以猜测：先手胜当且仅当n不是斐波那契数。换句话说，必败态构成斐波那契数列。