常見的博弈論有巴什博弈，威佐夫博弈，尼姆博弈，斐波那契博弈等等，今天暫時講幾個

文章目錄

• 一.巴什博弈
• • 證明：
  • 代碼
• 二.威佐夫博奕
• • 結論：
  • 代碼：
• 三.環形博弈
• • 結論
  • 證明
  • 代碼：

一.巴什博弈

巴什博奕：只有一堆n個物品，兩個人輪流從中取物，規定每次最少取一個，最多取m個，最后取光者為勝。

證明：

顯然，如果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%(m+1）==0，則先手必輸
變形：
如果條件不變，改成最后取光的人失敗
結論：若（n-1）%（m+1）== 0 ，則后手勝利

代碼

if(n%(m+1)==0) cout<<"后手必勝"<<endl; else cout<<"先手必勝"<<endl;

二.威佐夫博奕

有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，規定每次至少取一個，多者不限，最后取光者得勝。
A無論怎么取，B總是可以 針對著來

結論：

奇異局勢下先手必敗，非奇異局勢下先手必勝。
（a，b）表示兩堆物品的數量，也稱之為局勢
奇異局勢：就是當A面對這個局勢時就已經輸了。你也可以理解成必輸局面。比如（0,0）或者（1,2）（3,5）等等
那怎么知道一個局勢是否為奇異局勢
a與b滿足這個條件：
ak =[k（1+√5）/2]，bk= ak + k
（k=0，1，2，…,n 方括號表示取整函數）ak<bk

整合一下
ak = [ ( bk - ak ) （ 1 + √5 ） / 2 ]

證明：略（其實我也不是很明白）

代碼：

if(a>b) swap(a,b); ans=floor((b-a)*(1+sqrt(5.0))/2.0); if(ans==a) cout<<"后手必勝"<<endl; else cout<<"先手必勝"<<endl;

三.環形博弈

n個石子圍成一圈，每次只能取相鄰的k（1<=k<=n）個石子，取完者勝。
今天一個同學問我，我才想起來這個。。。

結論

如果n<=k,先手必贏（也就是如果先手能一次拿完就輸）
當k等于1時，n為奇先手勝，n為偶后手勝。

證明

因為是環形，假如說A第一次沒去完，那B只要取與A相對的石頭，也就是A拿完后，還剩奇數個石頭，B就拿與A對應位置的一個石頭，如果剩偶數個，就拿對應位置的兩個
這樣就把一個環拆分成兩個鏈，且每個鏈都是相等的
用sg定理，sg[x] ^ sg[x]= 0
這就是必敗態，所以先手A輸了
當k=1時，這就不用我講了吧。。。

代碼：

bool circle_game(int n,int k){if(k>=n||k==1&&(n&1)) return 1;return 0; }

例題 HDU - 3951

總結

以上是生活随笔為你收集整理的博弈论讲解（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。