※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益
有別於一般網頁架設公司，除了模組化的架站軟體，我們的營業主軸還包含：資料庫程式開發、網站建置、網頁設計、電子商務專案開發、系統整合、APP設計建置、專業網路行銷。
博弈論的題目有如下特點：
-
1：博弈模型為兩人輪流決策的博弈。並且兩人都使用最優策略來取得勝利。
- 兩個玩家，都會採取最優的決策，那麼如果存在一個局面為必勝局面，某玩家位於此局面。只要自己無失誤，則必勝。那麼同樣又一個局面為必敗局面，某玩家位於此局面。只要對手無失誤，則必敗。
- 那也就是說，針對這樣的遊戲，我們關注點應該在局面上。
-
2：博弈是有限的。即無論兩人如何決策，都會在有限步決出勝負。
-
3：博弈是公平的。即兩人進行決策的規則相同。
-
相關概念：
- 先手必勝狀態：先手可以從這個狀態走到某一個必敗狀態。
- 先手必敗狀態：先手走不到任何一個必敗狀態。
- 也就是說先手必勝狀態，那麼先手一定能採取某些操作，讓後手面對必敗態。如果是先手必敗態，無論先手怎麼操作，都無法讓後手面對必敗態。
簡單博弈的基本題型
1：bash博弈；2：nim博弈；3：威佐夫博弈；5：Fibonacci博弈；6：sg函數；
bash博弈 (巴什博奕)
-
假設一堆石子有n個，每次最多取m個，甲乙兩個玩家輪流取石子，最後把石子取完的人獲勝，保證甲乙每一步的決策都是最優的，請問給定n和m，問甲勝還是乙勝。
-
不妨假設剛剛開始
n = m + 1，那麼後手必勝，有如下結論：
- 令
n = ( m + 1 ) * r + s其中(r > 1，0 <= s < m + 1)。如果s=0的話，先手每次取k個，後手只要取(m+1-k)個即可，後手必贏。如果s!=0的話，先手者第一次取s個，後手第一次取k個，接下來先手只要取(m + 1 - k)個即可，先手必贏。 - 所以只需考慮 是否為0就可以判定結果。余為0，先手必敗，反之必勝。
- 令
-
-
例題：
- hdu_2188
#include<bits/stdc++.h> using namespace std; int c, m, n;//總捐款數，每次最多m int main() { //freopen("in.txt","r",stdin); cin >> c; while (c--) { cin >> n >> m; if (n % (m + 1) == 0) cout << "Rabbit\n"; else cout << "Grass\n"; } return 0; } -
hdu_1846
-
hdu_1847
Nim遊戲
-
假設有n堆石子，每堆石子分別有\(a_1,a_2,…,a_n個\),每次可以選擇任意一堆且至少取1枚石子, 甲乙兩個玩家輪流取石子, 最後把石子取完的人獲勝, 保證甲乙每一步的決策都是最優的, 甲為先手操作, 問甲勝還是乙勝。
-
結論:
- 設若\(a_1^{ ∧ }a_2^{∧}…^{∧}a_n = 0\)則先手必敗, 反之必勝。
-
證明
-
當\(a\)不全為\(0\)時, 任意一個\(res!=0\)的局面, 先手可以通過一定的操作讓後手面對\(res=0\)的局面。
-
對於任意一個\(res=0\)的局面, 先手無法通過任何操作讓後手面對\(res=0\)的局面。
-
得出結論, 當\(res=0\)時先手必敗, 反之必勝。
Nim博弈拓展-台階Nim
-
問題描述: 有一個\(n\)級台階的樓梯, 每級台階上有若干個石子, 其中第i級台階上有\(ai\)個石子\((i≥1)\)。兩位玩家路輪流操作, 每次操作可以從任意一級台階上拿若干個石子放到下一級台階上(不能不拿)。
-
已經拿到地面的石子不能再拿, 最後無法進行操作的人視為失敗。
-
問如果兩人都採取最優策略, 先手是否必勝.
-
結論
- \(res=a_1∧a_3∧a_5∧,…,∧a_n=0\)(當然這裏的n是奇數)先手必敗, 反之先手必勝。
-
證明
-
1): 考慮極端情況, 當\(a1,a3,…,an\)全為0時, \(res=0\), 此時先手只能將偶數級台階往下搬, 後手只需要將先手從偶數級台階上搬下來的石子全部搬到下一級偶數級台階, 先手必敗。
-
2): 當\(res=x≠0\)時, 通過經典\(Nim\)遊戲的證明, 我們知道一定有一種方法搬一定的石子到下一級讓後手面對res為0的局面。
-
3):當\(res=x=0\)且\(a\)不全為\(0\)時, 我們無法通過任何操作讓下一個狀態的\(res\)也為\(0\)。
※Google地圖已可更新顯示潭子電動車充電站設置地點!!
日本、大陸，發現這些先進的國家已經早就讓電動車優先上路，而且先進國家空氣品質相當好，電動車節能減碳可以減少空污
-
即對於\(res\)不為\(0\)的情況, 先手總能通過一定的操作讓後手面對\(res\)為\(0\)的情況,。
-
然而\(res\)為\(0\)時, 先手無論做什麼操作都無法讓後手面對\(res\)為\(0\)的情況。
-
那麼此刻我們就將題目轉化為在奇數台階上的經典Nim遊戲。
-
思考題:
-
為什麼不用\(res=a_2∧a_4∧a_6∧,…,∧a_n=0\)(n為偶數)來判定勝負？
- 因為當先手搬去一定的石子讓後手面對res=0res=0的情況, 後手可以搬去一號台階的石子到地面讓先手重新面對res=0res=0的情況
例題:
-
hdu_1850(經典Nim)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;
int n, a[maxn], res;
int main() {
//freopen("in.txt","r",stdin);
while (cin >> n,n)
{
res = 0;
for (int i = 1; i <= n; i++){
cin >> a[i];
res ^= a[i];
}
if (res == 0) puts("0");
else{
int ans = 0;
for (int i = 1; i <= n; i++)
if ((res ^ a[i]) < a[i]) ans++;
cout << ans << endl;
}
}
return 0;
}
- hdu_1730(經典Nim)
#include<bits/stdc++.h>
using namespace std;
int main() {
//freopen("in.txt","r",stdin);
int n, m;
while (cin >> n >> m) {
int res = 0;
for (int i = 1; i <= n; ++i) {
int a, b; cin >> a >> b;
res = res ^ (abs(a - b) - 1);
}
if (res == 0) puts("BAD LUCK!");
else puts("I WIN!");
}
return 0;
}
- poj_1704(台階Nim)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1000 + 10;
int a[N];
int main() {
//freopen("in.txt", "r", stdin);
int t, n;
cin >> t;
while (t--) {
int ans = 0;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
if (n % 2)
{
ans ^= (a[1] - 1);
for (int i = 3; i <= n; i += 2)
ans ^= (a[i] - a[i - 1] - 1);
}
else for (int i = 2; i <= n; i += 2)
ans ^= (a[i] - a[i - 1] - 1);
if (ans) printf("Georgia will win\n");
else printf("Bob will win\n");
}
return 0;
}
- hdu_4315(台階Nim)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn];
int n, k;
int main() {
//freopen("in.txt","r",stdin);
while(cin >> n >> k)
{
memset(a, 0, sizeof a);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
if(k == 1) puts("Alice");
else
{
int res = 0;
if(n & 1)
{
if(k == 2) res ^= a[1] - 1;
else res ^= a[1];
for(int i = 3; i <= n; i += 2)
res ^= a[i] - a[i - 1] - 1;
}
else
{
for(int i = 2; i <= n; i += 2)
res ^= a[i] - a[i - 1] - 1;
}
if(res) puts("Alice");
else puts("Bob");
}
}
return 0;
}
Wythoff 遊戲 (威佐夫博弈)
-
兩堆石子各有若干個, 兩人輪流從一堆取至少一個石子或從兩堆取同樣多的物品, 最後一名取完石子者勝利。
-
結論:
- 當兩堆石子各有\(n\)和\(m\)個且不妨設\(n<m\)。
- 當(m−n)(√5+1)/2=n時, 先手必敗。
-
證明
-
•首先考慮最(zhao)極(gui)端(lv)的情況, (0, 0), (1, 2), (3, 5)局面為先手必敗局面。而且這樣的数字對被稱為奇異局勢。
-
奇異局勢的定義如下：
- 設数字對為\(a[(i),b(i)]\)
- 1:\(a(0)=b(0)=0\);
- 2: \(a(k)\)是前面数字對中未出現的最小的自然數, 且\(a(k)+k=b(k)\)。
-
接下來我們看奇異局勢的幾個性質:
-
性質1: 任何自然數都包含在一個且僅有一個奇異局勢中。
-
性質2: 任意操作都能將奇異局勢轉變為非奇異局勢.
-
性質3: 採取適當的方法, 可將非奇異局勢轉變為奇異局勢。
證明略
-
-
結論：奇異局勢必敗
例題
- hdu_2177
#include<bits/stdc++.h>
using namespace std;
int n, m;
bool check(int n, int m) {
int x = min(n, m), y = max(n, m);
double c = (sqrt(5.00000) + 1) / 2;
double d = (double)(y - x);
if(x == int(c*d)) return 1; // 必敗 return 0;
}
void work() {
if(n > m) swap(n, m); // (n, m) //第一個模塊 我們能一起減去讓他成為必敗態 {
int tem = m - n;
double c = (sqrt(5.00000) + 1) / 2;
int a = double(tem) * c;
int b = a + tem;
if(n - a == m - b) cout << a << " " << b << endl;
}
//第二個模塊 我們求出當前n的奇異局勢, 如果m比他大 拿走就行 //如果m比他小我們求出(x, n) 然後拿走m {
double c = (sqrt(5.00000) + 1) / 2;
int x = n;
double d = x / c;
int y = n + d;
if(m > y) cout << x << " " << y << endl;
else
{
double x = double(n) * 2 / (sqrt(5.000000) + 1);
cout << int(x) << " " << n << endl;
}
}
}
int main() {
while(cin >> n >> m)
{
if(!(n + m)) break;
if(check(n, m)) puts("0");
else
{
puts("1");
work();
}
}
return 0;
}
斐波那契博弈(Fibonacci Nim Game)
-
一堆石子有nn個,兩人輪流取.先取者第1次可以取任意多個，但不能全部取完。以後每次取的石子數不能超過上次取子數的22倍。取完者勝。給定nn,問先手必勝還是必敗。
-
結論：
- 當\(n\)為\(fibonacci\)數的時候,先手必敗
-
證明：
例題：
- hdu_2516
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
unordered_map<int, int> mp;
ll f[50];
void fib() {
f[0] = f[1] = 1;
for(int i = 2; i <= 50; i++)
{
f[i] = f[i - 1] + f[i - 2];
mp[f[i]]++;
}
}
int main() {
int n;fib();
while(cin >> n)
{
if(n == 0)break;
if(!mp[n]) puts("First win");
else puts("Second win"); //如果是fibonacci數, 則先手必敗
return 0;
}
SG函數
-
\(mex\)運算:
- 定義\(mex(S)\)為不屬於集合S的最小非負整數運算。
- •舉個栗子: \(S=1,2,3,mex(s)=0\);
-
SG函數:
- •\(SG\)函數: 設對於每個節點x, 設從x出發有k條有向邊分別到達節點\(y1,y2,…,yk\), 定義SG(x)函數為後繼節點\(y1,y2,…,yk\)的SG函數值構成的集合再執行
mex運算的結果。 - 特別的, 整個有向圖GG的SGSG函數被定義為有向圖起點
s的SG函數值, 即\(SG(G)=SG(s)\) - 有向圖終點的
SG函數為0。
- •\(SG\)函數: 設對於每個節點x, 設從x出發有k條有向邊分別到達節點\(y1,y2,…,yk\), 定義SG(x)函數為後繼節點\(y1,y2,…,yk\)的SG函數值構成的集合再執行
-
結論:
- •先手必敗, 則該局面對應\(SG函數=0\)。反之必勝。
例題
- hdu_1524
#include<bits/stdc++.h> using namespace std;
const int maxn = 1e3 + 10;
int n, num;
int sg[maxn];
int head[maxn], ver[maxn], nex[maxn], tot;
void add(int x, int y) {
ver[++tot] = y; nex[tot] = head[x]; head[x] = tot;
}
int GetSg(int x) {
if(sg[x] != -1) return sg[x];
bool vis[maxn];
memset(vis, 0, sizeof(vis));
for(int i = head[x]; i; i = nex[i]) // 掃描所有出邊 {
int y = ver[i];
sg[y] = GetSg(y);
vis[sg[y]] = 1; //所有出邊的sg函數值 }
for(int i = 0; i < n; i++)
if(!vis[i]) return sg[x] = i; // mex運算 return 0;
}
void init() {
memset(head, 0, sizeof(head));
memset(nex, 0, sizeof nex);
memset(ver, 0, sizeof ver);
memset(sg, -1, sizeof sg);
tot = 0;
}
int main() {
while(cin >> n)
{
init();
for(int i = 0; i < n; i++)
{
cin >> num;
while(num--)
{
int x; scanf("%d", &x);
add(i, x);
}
}
while(cin >> num)
{
if(!num) break;
int res = 0;
while(num--)
{
int x; scanf("%d", &x);
res ^= GetSg(x);
}
if(res) puts("WIN");
else puts("LOSE");
}
}
return 0;
}
- hdu_1536
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
int s[maxn], sg[maxn];
int k;
void init() {
memset(sg, -1, sizeof(sg));
}
int GetSg(int x) {
if(sg[x] != -1) return sg[x];
bool vis[maxn]; memset(vis, 0, sizeof(vis));
for(int i = 1; i <= k; i++)
if(x >= s[i])
{
sg[x - s[i]] = GetSg(x - s[i]);
vis[sg[x - s[i]]] = 1;
}
for(int i = 0; ; i++)
if(!vis[i]) return sg[x] = i;
return 0;
}
int main() {
ios::sync_with_stdio(false);
while(cin >> k)
{
init();
if(k == 0) break;
for(int i = 1; i <= k; i++) cin >> s[i];
int num; cin >> num;
while(num--)
{
int x, res = 0; cin >> x;
for(int i = 1; i <= x; i++)
{
int y; cin >> y;
res ^= GetSg(y);
}
if(res) cout << "W";
else cout << "L";
}
cout << endl;
}
return 0;
}
參考
【博弈論】關於三姬分金(五海盜分贓)的博弈論問題分析
李永樂老師對三姬分金視頻講解
ACM集訓隊講解
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
※超省錢租車方案
商務出差、學生出遊、旅遊渡假、臨時用車!GO 神州租賃有限公司!合法經營、合法連鎖、合法租賃小客車!