当前位置:编程学习 > C/C++ >>

编程之美1.12——“拈”游戏分析

问题:
有N块石头和两个玩家A和B,玩家A先将石头随机分成若干堆,然后按照BABA...的顺序不断轮流取石头,能将剩下的石头一次取光的玩家获胜,每次取石头时,每个玩家只能从若干堆石头中任选一堆,取这一堆石头中任意数目(大于0)个石头。
请问:
玩家A要怎样分配和取石头才能保证自己有把握取胜?

如果石头的个数N为偶数,A只要将其分为相同的两份,就一定能取胜。
初始:XOR(M1, M1) == 0
玩家B:XOR(M1, M2) != 0  (其中一堆的个数减少到M2)
玩家A:XOR(M2, M2) == 0  (玩家A将另一堆的个数也减少到M2)
结果:XOR(M2, M2) == 0  (直到结束状态(0, 0))

如果石头的个数N为奇数,B有必胜的方法。
初始:XOR(M1, M2, ... , Mn) != 0
玩家B:XOR(M1, ... , Mi', ... , Mn) == 0 (其中一堆Mi的个数减少到Mi')
玩家A:XOR(M1, ... , Mj', ... , Mn) != 0
玩家B:XOR(M1, ... , Mi', ... , Mn) == 0 (其中一堆Mi的个数减少到Mi')
结果:XOR(M1, ... , Mj' , ... , Mn) == 0 (直到结束状态(0,0))

这里就有个问题:已知XOR(M1, M2, ... , Mn) != 0,玩家B该改变那个Mi以使得XOR(M1, ... , Mi', ... , Mn) == 0呢?
对于这个问题的答案,书中并未准确的结论。

经过本人的分析,所得到的结论如下:
设k=XOR(M1, M2, ... , Mn),已知k!=0,取一个数Mi,其二进制表达中在k的最高二进制位上的数为1,且这个
数Mi肯定存在(k的这个最高位在异或运算中肯定来自某一个Mi)。在程序中满足(Mi&k) > (k>>1)条件的数即为Mi。

简单证明:即假设k的二进制表达是1xx,那么Mi的二进制表达是x...x1xx,这样玩家B将该Mi改成Xi'=XOR(Mi, k)后,
Mi'的二进制表达是x...x0yy,肯定小于Mi,并且有XOR(M1, ... , Mi', ... , Mn) == 0。

下面的程序模拟了石头个数N为奇数的情况,其中玩家B用我 I 表示,玩家A用She表示。
[cpp] 
#include <iostream> 
#include <cstdlib> 
#include <ctime> 
using namespace std; 
 
int A[10]; 
 
int main() 

    int n = 25; // 石头总数(可变) 
    int m = 5;  // 划分的堆数(可变) 
    int i, k, s; 
    int sum=0; 
    srand(time(0)); 
    // 模拟m堆的石头个数,A[i]表示第i堆石头的个数 
    for (i=1; i<m; i++) 
    { 
        A[i] = rand()%(5*i-sum); 
        sum += A[i]; 
    }   A[m] = n - sum; 
    while (true) 
    {    
        // 输出每个堆的石头个数 
        for (i=1; i<=m; i++) 
            cout << A[i] << " "; 
        cout << endl; 
 
        int xor = 0; 
        for (i=1; i<=m; i++) 
            xor = xor^A[i]; 
        for (i=1; i<=m; i++) 
            // 二进制表达中在k的最高二进制位上的数为1                      
            if ((A[i]&xor) > (xor>>1))  break;      
        printf("I: get %d stones from %d heap\n", A[i]-(A[i]^xor), i);       
        // 将Mi改为Mi' 
        A[i] = A[i]^xor; 
        // 对方随机取数据       
        for (i=1; i<=m && A[i]==0; i++); 
        if (i>m) break; 
        do 
        { 
            k = rand()%m + 1; 
        }while (A[k] == 0); 
        s = rand()%A[k] + 1; 
        printf("She: get %d stones from %d heap\n", s, k); 
        A[k] = A[k] - s; 
    } 
    return 0; 


作者:linyunzju
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,