前言

博弈論，博大精深啊~~
這里就是一個簡單博弈論的算法題，典型的入門級別，值得學習。

題目要求

P3150題目鏈接

分析

我們模擬一下勝負情況：

m=1時：
pb不能分割，所以zs贏了。

m=2時：
pb分割成1+1，對方拿走一份，必定是1。對于剩下的1，zs不能分割，pb贏了。

m=3時：
pb分割成2+1，對方為了續命，只能剩下2，zs對2進行1+1的分割，此時情況回到逆向的m=2，所以zs贏了。

m=4時：
pb有兩種選擇，3+1或者2+2。
3+1時，zs為了續命，只能剩下3，這是反向的m=3，pb贏了。
2+2時，zs只能剩下2，這是反向的m=2，zs就贏了。
但是pb先手，而且用最優策略，自然會選擇3+1方案，就贏了。

m=5時：
pb有兩種選擇，3+2或者4+1。
3+2時，zs選3就會輸，選2就會贏。
4+1時，zs選1就輸了，只能選4，然后他會為了勝利進行3+1方案，堵死pb獲勝的可能。
所以pb不論作何選擇，zs都有將其100%堵死的策略，zs必勝。

m=6時：
pb有三種可能，3+3或者4+2或者5+1。
3+3時，zs只能選3，就是逆向的m=3，pb贏。
4+2時，zs選2就肯定贏，選4的話就能選3+1方案，封死pb獲勝可能，這種情況下zs肯定能贏。
5+1時，zs不可能選1，因為會輸，必然選5，選5的話，那就反過來了，pb肯定能贏。
所以，pb選擇3+3或者5+1方案，避開4+2方案，即可戰勝zs，pb有選擇權，所以pb贏。

……

越往下分析越復雜，但是我們能發覺規律：
如果m為偶數, 那么先手贏(即pb), 如果m為奇數, 那么后手贏(即zs)。

繼續分析：
我們不管先手怎么走，為了所謂“勝利的目標”也好，為了“續命的事實”也好，
只要他手里是奇數，為了勝利，都不得不拆成奇數+偶數。那么后手只要選擇偶數，他就可以把這個數化成m = (m-1) + 1(后手的最優策略)，把奇數轉移給先手。這樣經過若干次轉移之后, 后手手里一定會是2，然后2 = 1 + 1，后手就贏了。

所以，其實手里是奇數的人是沒有勝算的，所以這個狀態是必敗態。而手里是偶數的人是有必勝的可能的，只有他才有最優策略而且只要他按照最優策略走，他一定會贏，因此這個狀態是必勝態。這里我們認為每個人一定能作出對自己當前和全局最有利的決策，所以其實在一開始給出數值的一瞬間，勝負已定。

而理解這個博弈論問題的關鍵，就是擁有偶數的策略：控制偶數的一方每次減一，給對方兩個奇數的選項，因而不論對方怎么切割這個奇數，最終一定會切成奇數+偶數，原先控制偶數的人再選偶數，就可以再次將偶數態(必勝態)轉移過來，就一定能一步一步走向勝利。

有位dalao這樣總結的這個問題：
其實這里的必敗態（不能控制偶數的一方）從來沒有最佳策略，博弈也不是雙方的博弈，而是處在必勝態的那方和自己博弈。而這場博弈，由于絕頂聰明的前提，是必勝的，而我們要做的，只是找出誰有跟自己博弈的機會。

我覺得這位大佬說的特別對，理解很Nice，OrzOrz……

那代碼就很簡單啦，這里我簡單的用了一下x&1，表示x%2，判斷奇偶數用的。

AC代碼（Java語言描述）

import java.util.ArrayList; import java.util.List; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();List<String> list = new ArrayList<>();for (int i = 0; i < num; i++) {if ((scanner.nextInt() & 1) == 0) {list.add("pb wins");} else {list.add("zs wins");}}scanner.close();for (String s : list) {System.out.println(s);}} }

總結

以上是生活随笔為你收集整理的用博弈论的思想玩游戏（洛谷P3150题题解，Java语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

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