尼姆博弈（英文名：Nimm Game），是尼姆發明的數學遊戲。
基本介紹
- 中文名：尼姆博弈
- 外文名：Nimm Game
- 發明人：尼姆
- 領域：數學
尼姆博弈,例子,C++語言實現,
尼姆博弈
有三堆各若干個物品，兩個人輪流從某一堆取任意多的物品，規定每次至少取一個，多者不限，最後取光者得勝。
這種情況最有意思，它與二進制有密切關係，我們用（a，b，c）表示某種局勢，首先（0，0，0）顯然是奇異局勢，無論誰面對奇異局勢，都必然失敗。第二種奇異局勢是（0，n，n），只要與對手拿走一樣多的物品，最後都將導致（0，0，0）。仔細分析一下，（1，2，3）也是奇異局勢，無論自己如何拿，接下來對手都可以將其變為（0，n，n）的情形。
計算機算法裡面有一種叫做按位模2加，也叫做異或的運算，我們用符號⊕表示這種運算，先看（1，2，3）的按位模2加的結果：
1 =二進制01
2 =二進制10
3 =二進制11 ⊕
———————
0 =二進制00 （注意不進位）
對於奇異局勢（0，n，n）也一樣，結果也是0。
任何奇異局勢（a，b，c）都有a⊕b⊕c =0。
注意到異或運算的交換律和結合律，及a⊕a=0，:
a⊕b⊕(a⊕b)=(a⊕a)⊕(b⊕b)=0⊕0=0。
所以從一個非奇異局勢向一個奇異局勢轉換的方式可以是：
1）使 a = c⊕b
2）使 b = a⊕c
3）使 c = a⊕b
例子
例1。（14，21，39），14⊕21=27，39-27=12，所以從39中拿走12個物體即可達到奇異局勢（14，21，27）。
例2。（55，81，121），55⊕81=102，121-102=19，所以從121中拿走19個物品就形成了奇異局勢（55，81，102）。
例3。（29，45，58），29⊕45=48，58-48=10，從58中拿走10個，變為（29，45，48）。
例4。我們來實際進行一盤比賽看看：
甲:(7,8,9)->(1,8,9)奇異局勢
乙:(1,8,9)->(1,8,4)
甲:(1,8,4)->(1,5,4)奇異局勢
乙:(1,5,4)->(1,4,4)
甲:(1,4,4)->(0,4,4)奇異局勢
乙:(0,4,4)->(0,4,2)
甲:(0.4,2)->(0,2,2)奇異局勢
乙:(0,2,2)->(0,2,1)
甲:(0,2,1)->(0,1,1)奇異局勢
乙:(0,1,1)->(0,1,0)
甲:(0,1,0)->(0,0,0)奇異局勢
甲勝。
C++語言實現
// by Sirius_Ren 例題：POJ2234#include <cstdio>using namespace std;int main(){ int m,ans,n; while(~scanf("%d",&m)){ n=ans=0; while(m--) scanf("%d",&n),ans^=n,printf("ans=%d\n",ans); if(ans)printf("Yes\n"); else printf("No\n"); }}