【前言】

今天才算是搞明白了（？？）最基本的四種博弈

【小結(jié)】

1.巴什博奕（Bash Game）

一堆中取石子，兩個(gè)人輪流取石子，每次取石子量至少為1，至多為m，先取完者勝利。

當(dāng)n%(m+1)==0，后手勝。

2.斐波那契博弈（Fibonacci Game）

一堆中取石子，兩個(gè)人輪流取石子，第一次可以取任意多個(gè)，但不能全部取完，以后每次取的石子數(shù)不能超過(guò)上次的兩倍，先取完者勝。

當(dāng)n為斐波那契數(shù)時(shí)，先手必?cái)　?/span>

3.威佐夫博奕（Wythoff Game）

兩堆中取石子，兩個(gè)人輪流取石子，每次從一堆中取任意數(shù)量石子或者同時(shí)從兩堆中取相同數(shù)量石子，先取完者勝利。

當(dāng)形成奇異局勢(shì)時(shí)后手勝。

即令兩堆石子量分別為a、b(a<b)，c=b-a,當(dāng)a=(c*(1+sqrt(5))/2)時(shí)，后手勝。

4.尼姆博奕（Nimm Game）

若干堆中取石子，兩個(gè)人輪流從某一堆取任意多的物品，規(guī)定每次至少取一個(gè)，多者不限，先取完者勝利。

所有堆石子的數(shù)量異或?yàn)?時(shí)后者勝。

【題目】

1122: 取石子游戲II

Time Limit: 1 Sec??Memory Limit: 128 MB
Submit: 234??Solved: 122
[Submit][Status][Web Board]

Description

一堆石子有n個(gè),兩人輪流取.每次取最少取1個(gè),最多取m個(gè)。取完者勝.先取者負(fù)輸出"Second win".先取者勝輸出"First win"

Input

多組測(cè)試數(shù)據(jù)。

每組測(cè)試數(shù)據(jù)包含2個(gè)正整數(shù)n,m。(n,m<=10000000)

Output

對(duì)于每組測(cè)試數(shù)據(jù)，輸出誰(shuí)獲勝.

Sample Input

2 1

3 2

3 1

Sample Output

Second win

Second win

First win?

【題解】

巴什博奕

【代碼】

#include<stdio.h> int main() {int n,m;while(~scanf("%d%d",&n,&m)){if(n%(m+1)==0)printf("Second win\n");elseprintf("First win\n");}return 0; }

【題目】

?

?

1121: 取石子游戲I

Time Limit: 1 Sec??Memory Limit: 128 MB
Submit: 276??Solved: 156
[Submit][Status][Web Board]

Description

一堆石子有n個(gè),兩人輪流取.先取者第1次可以取任意多個(gè)，但不能全部取完.以后每次取的石子數(shù)不能超過(guò)上次取子數(shù)的2倍。取完者勝.先取者負(fù)輸出"Second win".先取者勝輸出"First win".

Input

多組測(cè)試數(shù)據(jù)。

每組測(cè)試數(shù)據(jù)包含1個(gè)整數(shù)n。(1<n<=1000000000)

Output

對(duì)于每組測(cè)試數(shù)據(jù)，輸出誰(shuí)獲勝.

Sample Input

2

13

10000

Sample Output

Second win

Second win

First win?

【題解】

?

斐波那契博弈

【代碼】

#include<bits/stdc++.h> using namespace std; int main() {int f[50],i,n;f[0]=1,f[1]=2;for(i=2;i<50;i++)f[i]=f[i-1]+f[i-2];while(~scanf("%d",&n)){for(i=0;i<50;i++)if(n==f[i])break;else if(n>f[i])continue;if(i<50)printf("Second win\n");elseprintf("First win\n");}return 0; }

【題目】

?

Problem A: Return of the Nim

Time Limit: 1 Sec??Memory Limit: 128 MB
Submit: 11??Solved: 9
[Submit][Status][Web Board]

Description

Sherlock and Watson are playing the following modified version of Nim game:

• ? There are n piles of stones denoted as? piles0 ,?? piles1 ,...,?? pilesn-1 , and n is a prime number;
• ? Sherlock always plays first, and Watson and he move in alternating turns. During each turn, the current player must perform either of the following two kinds of moves: ?

1.? Choose one pile and remove k(k >0) stones from it;
??? 2.? Remove k stones from all piles, where 1≤k≤the size of the smallest pile. This move becomes unavailable if any pile is empty.

• ? Each player moves optimally, meaning they will not make a move that causes them to lose if there are still any better or winning moves.

Giving? the initial situation of each game, you are required to figure out who will be the winner

Input

The first contains an integer, g, denoting the number of games. The 2×g subsequent lines describe each game over two lines:
1. The first line contains a prime integer, n, denoting the number of piles.
2. The second line contains n space-separated integers describing the respective values of piles0, piles1,..., pilesn-1.

• 1≤g≤15
• 2≤n≤30, where n is a prime.
• 1≤pilesi≤10^5 where 0≤i≤n?1

Output

For each game, print the name of the winner on a new line (i.e., either “Sherlock” or “Watson”)

Sample Input

2 3 2 3 2 2 2 1

Sample Output

Sherlock Watson

【題解】

當(dāng)n=2時(shí)為威佐夫博奕，當(dāng)n>2時(shí)為尼姆博奕。

【代碼】

#include<bits/stdc++.h> using namespace std; int main() { int t,n,a[35],i; scanf("%d",&t); while(t--) { scanf("%d",&n); int f=1; for(i=0;i<n;i++) scanf("%d",&a[i]); if(n==2) { if(a[0]>a[1]) swap(a[0],a[1]); int b=a[1]-a[0]; if(a[0]==floor(b*(1+sqrt(5))/2)) f=0; } else{ int c=a[0]; for(i=1;i<n;i++) c^=a[i]; if(c==0) f=0; } if(f) printf("Sherlock\n"); elseprintf("Watson\n"); } return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的基础博弈论（巴什博奕、斐波那契博弈、威佐夫博奕、尼姆博奕）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。