當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

巴什博奕

發布時間：2023/11/27 生活经验 30 豆豆

生活随笔收集整理的這篇文章主要介紹了巴什博奕小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

巴什博奕（Bash Game）：只有一堆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）的倍數，就能最后獲勝。
? ? 這個游戲還可以有一種變相的玩法：兩個人輪流報數，每次至少報一個，最多報十
個，誰能報到100者勝。

HDU 1846

各位勇敢者要玩的第一個游戲是什么呢？很簡單，它是這樣定義的：
1、本游戲是一個二人游戲;
2、有一堆石子一共有n個；
3、兩人輪流進行;
4、每走一步可以取走1…m個石子；
5、最先取光石子的一方為勝；

如果游戲的雙方使用的都是最優策略，請輸出哪個人能贏。

Sample Input
2
23 2
4 3

Sample Output
first
second

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std ;
 4 
 5 int a[110] ;
 6 
 7 int main ()
 8 {
 9     int T ;
10     scanf("%d" , &T) ;
11     while (T--)
12     {
13         int n , m ;
14         scanf("%d %d" , &n , &m) ;
15         if (n % (m+1) == 0)
16           printf("second\n") ;
17         else
18           printf("first\n") ;
19     }
20     
21     
22     
23 }

View Code

HDU 2149 拍賣

剛開始底價為0，兩個人輪流開始加價，不過每次加價的幅度要在1～N之間，當價格大于或等于田地的成本價 M 時，主辦方就把這塊田地賣給這次叫價的人。第一次加價的時候，
Lele要出多少才能保證自己買得到這塊地呢？

思路：一堆數量為M的石子，每次只能拿1-N ，當N >= M 先手可以一次拿完

Sample Input
4 2 // m n
3 2
3 5

Sample Output
1
none
3 4 5

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std ;
 4 
 5 int a[110] ;
 6 
 7 int main ()
 8 {
 9 
10     int n , m ;
11     while (scanf ("%d %d" , &m , &n) != EOF )
12     {
13         int i ;
14         if (m > n)
15         {
16             if (m % (n + 1) == 0)
17                printf("none\n") ;
18             else
19                printf("%d\n" , m % (n + 1)) ;
20         }
21         else
22         {
23             for (i = m ; i < n ; i++)
24                printf("%d " , i) ;
25             printf("%d\n" , n) ;
26         }
27     }
28     
29     
30 }

View Code

HDU 2188 捐款

選拔規則如下：
1、最初的捐款箱是空的；
2、兩人輪流捐款，每次捐款額必須為正整數，并且每人每次捐款最多不超過m元(1<=m<=10)。
3、最先使得總捐款額達到或者超過n元（0<n<10000）的一方為勝者，則其可以親赴災區服務。
我們知道，兩人都很想入選志愿者名單，并且都是非常聰明的人，假設林隊先捐，請你判斷誰能入選最后的名單？

如果林隊能入選，請輸出字符串"Grass"，如果徐隊能入選，請輸出字符串"Rabbit"

Sample Input
2
8 10 // n m
11 10

Sample Output
Grass
Rabbit

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std ;
 4 
 5 int a[110] ;
 6 
 7 int main ()
 8 {
 9 
10     int T ;
11     scanf("%d" , &T) ;
12     while (T--)
13     {
14         int n , m ;
15         scanf("%d %d" , &n , &m) ;
16         if (n <= m)
17           printf("Grass\n") ;
18         else
19         {
20             if (n % (m + 1) == 0)
21               printf("Rabbit\n") ;
22             else
23               printf("Grass\n") ;
24         }
25     }
26     
27     
28     
29 }

View Code

HDU 2147 走棋盤

題目的意思是從棋盤的最右上角到左下角,其中只可以走三個方向，左邊，下邊，左下邊,不能移動著失敗，問先手是否勝利

Sample Input
5 3
5 4
6 6
0 0

Sample Output
What a pity!
Wonderful!
Wonderful!

//一切博弈都是找規律
//題目的意思是從棋盤的最右上角到左下角,其中只可以走三個方向，左邊，下邊，左下邊,不能移動著失敗，問先手是否勝利
//根據博弈論的理論，先從左下角開始分析
/*
* 博弈論：組合博弈
* 必敗點(P點) :前一個選手(Previous player)將取勝的位置稱為必敗點。
* 必勝點(N點) :下一個選手(Next player)將取勝的位置稱為必勝點。
* 必敗（必勝）點的屬性：
* (1) 所有終結點是必敗點（P點）；
* (2) 從任何必勝點（N點）操作，至少有一種方法可以進入必敗點（P點）；
* (3)無論如何操作，從必敗點（P點）都只能進入必勝點（N點）.
* 由上面的屬性得到該題的算法：
* 步驟1:將所有終結位置標記為必敗點（P點）；
* 步驟2: 將所有一步操作能進入必敗點（P點）的位置標記為必勝點（N點）
* 步驟3:如果從某個點開始的所有一步操作都只能進入必勝點（N點），則將該點標記為必敗點（P點）；
* 步驟4: 如果在步驟3未能找到新的必敗（P點），則算法終止；否則，返回到步驟2。
* 由上面的算法計算一個例子：
* 我們可以把問題轉換成從（1，1）走到（n，m） (方便等下得出結論）
* 但n=8，m=9的情況
* NNNNNNNNN
* PNPNPNPNP
* NNNNNNNNN
* PNPNPNPNP
* NNNNNNNNN
* PNPNPNPNP
* NNNNNNNNN
* PNPNPNPNP
*初始點（1，1）為N所以輸出Wonderful!
*從這里例子就可以很清楚得看出當n和m都為奇數時，初始點（1，1）才會是P。
*因此該題只需判斷n，m是否同時為奇數即可。
*/

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std ;
 4 
 5 int main ()
 6 {
 7 
 8     int n , m ;
 9     while (scanf("%d %d" , &n , &m) )
10     {
11         if (n == 0 && m == 0)
12            break ;
13         if (n & 1 && m & 1)
14           printf("What a pity!\n") ;
15         else
16           printf("Wonderful!\n") ;
17     } 
18     
19     
20     
21 }

View Code

HUD 2897 變形BASH

大意：一堆石子共有n個，A,B兩人輪流從中取，每次取的石子數必須
在[p,q]區間內，若剩下的石子數少于p個，當前取者必須全部取完。
最后取石子的人輸。給出n,p,q，問先取者是否有必勝策略？

Bash博弈的變形
假設先取者為A,后取者為B,初始狀態下有石子n個，除最后一次每次取的石子個數必須在[p,q]區間內，則：
1.若當前石子共有n = (p+q)*r個，則A必勝，必勝策略為：
A第一次取q個，以后每次若B取k個，A取（p+q-k）個，如此最后必剩下p個給B,A勝
2.若n = (p+q)*r+left,(1<left<=p),則B必勝，必勝策略為：
每次取石子活動中，若A取k個，則B取（p+q-k）個，那么最后必剩下left個給A，
此時left<=p,A只能一次取完，B勝
3.若n = (p+q)*r+left,(p<left<p+q),則A必勝，必勝策略為：
A第一次取t(1<left-t<=p)個，以后每次若B取k個，A取（p+q-k）個，
那么最后必剩下1<left-t<=p個給B,A勝

Sample Input
7 2 4
6 2 4

Sample Output
LOST
WIN

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cmath>
 4 # include <algorithm>
 5 using namespace std ;
 6 
 7 int main ()
 8 {
 9     int n , p , q ;
10     while (scanf("%d %d %d" , &n , &p , &q) != EOF)
11     {
12         int t ;
13         t = n % (p + q) ;
14         
15         if (t <= p && t > 0)
16           printf("LOST\n") ;
17         else
18           printf("WIN\n") ;
19     }
20     
21     return 0 ;
22 }

View Code

HDU 1847 拿牌的時候只能2的冪次（找規律法也可用SG大法）

作為計算機學院的學生，Kiki和Cici打牌的時候可沒忘記專業，她們打牌的規則是這樣的：
1、總共n張牌;
2、雙方輪流抓牌；
3、每人每次抓牌的個數只能是2的冪次（即：1，2，4，8，16…）
4、抓完牌，勝負結果也出來了：最后抓完牌的人為勝者；
假設Kiki和Cici都是足夠聰明（其實不用假設，哪有不聰明的學生~），并且每次都是Kiki先抓牌，請問誰能贏呢？

Sample Input
1 //n
3

Sample Output
Kiki
Cici

這題如果你是先手，考慮你的必勝態。注意，因為任何正整數都能寫成若干個2的整數次方冪之和。由于規定只能取2的某個整數次方冪，只要你留給對手的牌數為3的倍數時，那么你就必贏，因為留下3的倍數時，對手有兩種情況：
1：如果輪到對方抓牌時只剩3張牌，對方要么取1張，要么取2張，剩下的你全取走，win！
2：如果輪到對方抓牌時還剩3*k張牌，對手不管取多少，剩下的牌數是3*x+1或者3*x+2。輪到你時，你又可以構造一個3的倍數。所以無論哪種情況，當你留給對手為3*k的時候，你是必勝的。
題目說Kiki先抓牌，那么當牌數為3的倍數時，Kiki就輸了。否則Kiki就能利用先手優勢將留給對方的牌數變成3的倍數，就必勝。

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std ;
 4 
 5 int main ()
 6 {
 7     
 8     int n ;
 9     while (scanf("%d" , &n ) != EOF)
10     {
11         if (n % 3 == 0)
12           printf("Cici\n") ;
13         else
14           printf("Kiki\n") ;
15         
16     } 
17     
18     
19     
20 }

View Code

HDU 4764 寫數字

題意：
兩個人寫數字，要求當前個寫的數字Y與前一個寫的數字X滿足：
1. 1 <= Y - X <= k
2. Y要求小于N(第一次取只需滿足1<=Y<=k)；
不都滿足則輸。
思路：
可將題目意思理解為取石子(題目有提示)，取的石子是有規定的，誰能取到第N-1個，那么就能贏得比賽。
寫的數字>=N就輸了所以總石子數為N-1

Sample Input
1 1
30 3
10 2
0 0

Sample Output
Jiang
Tang

Jiang

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std ;
 5 
 6 
 7 
 8 int main ()
 9 {
10     int n , k ;
11     while(scanf("%d %d" , &n , &k) )
12     {
13         if (n == 0 && k == 0)
14            break ;
15         if ((n - 1) % (k + 1) == 0)
16           printf("Jiang\n") ;
17         else
18           printf("Tang\n") ;
19     }
20     
21     
22     return 0 ;
23 }

View Code

轉載于:https://www.cnblogs.com/mengchunchen/p/4490713.html

總結

以上是生活随笔為你收集整理的巴什博奕的全部內容，希望文章能夠幫你解決所遇到的問題。

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

巴什博奕