Nim_Game

Nim游戏问题描述有N堆石子，每堆石子各有N1，N2，....，Nn个棋子，两个玩家轮流从堆中拿走最少1个、最多m个石子，每次只能在一堆中取石子。拿走最后一枚石子的玩家获胜，什么情况下能保证玩家必胜？N堆石子中能否找到一个非平衡状态使得玩家一取走若干石子之后，将状态转化为平衡状态，玩家二任意操作都将平衡打破，最终玩家一取走最后一颗石子获得胜利。美国数学家C.L.Bouton解题关键如何确定当前状态是平衡状态还是非平衡状态？如何将非平衡状态转化为平衡状态？平衡定义把每堆石子个数Ii表示为二进制数：I1=as...a1a0I2=bs...b1b0·····In=es...e1e0Nim游戏的平衡只有当且仅当as+bs+...+es是偶数，...，ai+bi+...+ei是偶数，....，a0+b0+...+e0是偶数，第i位平衡指的是ai+bi+...+ei是偶数，否则为非平衡。Nim游戏平衡即0-S位都是平衡，第i位1的个数为偶数，即I1^I2^I3...In=0I13011I24100I35101Xor2010状态转换非平衡时：I1^I2...^Ii^...In=k(k!=0)，当Ii^kIi时改变Ii这堆石子使其成为ai^k即可达到平衡。证明：找到K二进制的最高位（若第x位为1），则必然能找到一个Ii(至少一个)的第x位也为1，此时有Ii^kIi(保证取走的石子个数小于该堆石子个数)，改变Ii这堆石子使其成为Ii^k,则有I1^I2^I3..^(Ii^k)^...In=I1^I2^I3..^Ii^...In^k=(I1^I2^I3..^Ii^...In)^k=k^k=0Nim游戏策略用I1^I2...^Ii^...In=k是否等于0判断当前状态是否平衡，若为非平衡则玩家1必胜，否则玩家2必胜。找到第一个满足（Ii^kIi）条件的Ii，令Ii^=k，即可达到平衡Nim策略初始状态3堆石子对应为：3、4、5(3^4^5=2!=0玩家1必胜)301141005101K010I1^K=1第1堆取走2个石子100141005101K000平衡状态玩家2取走第2堆3个石子100110015101K101100110010000K000平衡状态玩家2取走第1堆1个石子000010010000K001玩家1胜利I3^K=0第3堆取走5个石子算法实现voidNim(){intk=0;forinti=0toHeap_numk^=Heap[i];if(k!=0){//游戏非平衡状态forintj=0toHeap_numif(Heap[j]^kHeap[j]){Heap[j]^=k;break;//找到更改堆中数据之后，退出循环}}else{//游戏平衡状态intk=0;while(Heap[k]==0){k++;}Heap[k]-=1;//找到堆中第一个石子数大于零的，并取走一个}Show_Heap();//输出当前堆的状态}算法性能分析本次实验选取的是用一维数组对堆数据进行存储，并没有用到复杂的数据结构，实验中，只需对数组元素进行N次内的异或计算，故时间复杂度在O（n）内，效率比较高。