ACM演算法之博弈

05-03

今天張科技終於為大家帶來第一篇高級語言相關的文章；

感謝關注張科技；

微信公眾號回復【博弈】可查看文章；

ACM省賽就在眼前了，那麼今天就跟大家簡要的說一下博弈的相關內容；

一：巴什博奕：

題目描述

一天，TT在寢室閑著無聊，和同寢的人玩起了取石子遊戲，而由於條件有限，他/她們是用旺仔小饅頭當作石子。遊戲的規則是這樣的。設有一堆石子，數量為N（1<=N<=1000000），兩個人輪番取出其中的若干個，每次最多取M個（1<=M<=1000000），最先把石子取完者勝利。我們知道，TT和他/她的室友都十分的聰明，那麼如果是TT先取，他/她會取得遊戲的勝利么？

輸入

第一行是一個正整數n表示有n組測試數據

輸入有不到1000組數據，每組數據一行，有兩個數N和M,之間用空格分隔。

輸出

對於每組數據，輸出一行。如果先取的TT可以贏得遊戲，則輸出「Win」，否則輸出「Lose」（引號不用輸出）

樣例輸入

1000 1

1 100

樣例輸出

Lose

Win

思路：

設N為石子的總數，M為一次最多可取的石子數，K為兩人取石子的總次數。

首先，若TT贏得了遊戲，則他先把石子取完了，也就是在TT第K次（最後一次）取石子時，剩餘的石子數小於等於M，可以是：1，2，3…M-1，M。為使第K-1次（倒數第二次）TT的室友取石子後，剩餘的石子數為上面所述情況，第K-1次取石子時的石子數應為M+1，這樣無論TT的室友取的是1至M中的任意一個數，剩餘石子數都小於等於M。

按照這個思想，推出最後的公式為：

N %(M+1) != 0時，TT可以贏得遊戲。

C代碼實現：

#include <stdio.h>

int main()

{

int test_num, stone_num, max_fetch;

scanf("%d", &test_num);

while (test_num--)

{

scanf("%d%d", &stone_num, &max_fetch);

if (stone_num % (max_fetch + 1) != 0)

printf("Win
");

else

printf("Lose
");

}

return 0;

}

二：威佐夫博弈：

有2堆石子。A B兩個人輪流拿，A先拿。每次可以從一堆中取任意個或從2堆中取相同數量的石子，但不可不取。拿到最後1顆石子的人獲勝。假設A B都非常聰明，拿石子的過程中不會出現失誤。給出2堆石子的數量，問最後誰能贏得比賽。

結果：

若兩堆物品的初始值為（x，y），且x < y，則另z=y-x；

記w=（int）[（（sqrt（5）+1）/2）*z ]；

C代碼實現：

#include <stdio.h>

#include <math.h>

int main ()

{

int x,y,t;

scanf("%d%d",&x,&y);

if(x>y)

{

t=x;x=y;y=t;

}

t=floor((y-x)*(1+sqrt(5.0))/2.0);//floor函數：向下取整

//例：floor(4.1); // 返回4，floor(5.9); // 返回5

if(t==x)

printf("B");

else

printf("A");

}

三，尼姆博弈：

有N堆石子。A B兩個人輪流拿，A先拿。每次只能從一堆中取若干個，可將一堆全取走，但不可不取，拿到最後1顆石子的人獲勝。假設A B都非常聰明，拿石子的過程中不會出現失誤。給出N及每堆石子的數量，問最後誰能贏得比賽。

結論：把每堆物品數全部異或起來，如果得到的值為0，那麼先手必敗，否則先手必勝。

關鍵代碼：

scanf("%d", &N);

while (N--)

{

scanf("%d", &stone);

tag ^= stone;

}

printf("%c
", tag == 0 ? B : A);

四，斐波那契博弈：有一堆物品，兩人輪流取物品，先手最少取一個，至多無上限，但不能把物品取完，之後每次取的物品數不能超過上一次取的物品數的二倍且至少為一件，取走最後一件物品的人獲勝。

結論是：先手勝當且僅當n不是斐波那契數（n為物品總數）

下面我們看一個例題("浪潮杯"山東省第八屆ACM大學生程序設計競賽題A)：

Return of the Nim

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

There are n piles of stones denoted as piles0,piles1,...,piles n-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:

Choose one pile and remove k(k >0) stones from it;
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,...,piles n-1.

1≤g≤15
2≤n≤30, where n is a prime.
1≤pilesi≤

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

232 3 222 1

Sample Output

SherlockWatson

解析及答案C代碼版本將在下期文章發布；

下期預告：快速冪的C代碼實現；

歡迎持續關注張科技；

微信公眾號回復【博弈】可查看文章；

http://weixin.qq.com/r/ISgiJgbEvc7BKUJFb32l (二維碼自動識別)