|
特別預告:本周將發(fā)布 三月底春季訓練營,，五一信息學訓練營,，高考期間，暑假期間信息學訓練營 課程通知,，敬請關注,！ ◆ ◆ ◆ 博弈論 在生活中五子棋也是一種先手有必贏策略的游戲，有人會說五子棋先手我也會輸啊,，所以 博弈論問題都有個類似如“參與者足夠聰明”,，“兩人都不犯錯'的前提。 在此前提下,，討論幾種常見的博弈情形,。  一. 巴什博奕（Bash Game）： Bash Game   A和B一塊報數(shù),，每人每次報最少1個,，最多報4個，看誰先報到30,。這應該是最古老的關于巴什博奕的游戲了吧,。 其實如果知道原理，這游戲一點運氣成分都沒有,，只和先手后手有關,，比如第一次報數(shù)，A報k個數(shù),，那么B報5-k個數(shù),，那么B報數(shù)之后問題就變?yōu)椋珹和B一塊報數(shù),，看誰先報到25了,，進而變?yōu)?0,15,10,5，當?shù)?的時候,，不管A怎么報數(shù),，最后一個數(shù)肯定是B報的,，可以看出，作為后手的B在個游戲中是不會輸?shù)摹?/p> 那么如果我們要報n個數(shù),，每次最少報一個,，最多報m個，我們可以找到這么一個整數(shù)k和r,，使n=k*（m+1）+r,，代入上面的例子我們就可以知道，如果r=0,，那么先手必?。环駝t,，先手必勝,。 巴什博奕：只有一堆n個物品，兩個人輪流從中取物,，規(guī)定每次最少取一個,，最多取m個，最后取光者為勝,。 代碼如下：  例題有：HDU4764 Stone： 題目大意：Tang和Jiang輪流寫數(shù)字,，Tang先寫，每次寫的數(shù)x滿足1<><><><> 結論：r=（n-1）%（k+1）,，r=0時Jiang勝,，否則Tang勝。 詳解： Bash Game:同余理論 一堆n個物品,，兩人輪流取，每次取1至m個,，最后取完者勝 比如10個物品,，每次只能取1到5個，則先手方必贏 1.面對[1...m]個局面,，必勝 2.面對m+1個局面,，必輸 3.如果可以使對手面臨必輸局面，那么是必贏局面 4.如果不能使對手面臨必輸局面,，那么是必輸局面 基礎：1,2, ...,m是必贏局面,，m+1是必輸局面 遞推：m+2,m+3, ... ,2m+1是必贏局面，2m+2是必輸局面 ...k(m+1)是必輸局面,，應該允許k=0,因為0顯然也是必輸局面 在必輸局和必贏局中,，贏的一方的策略是： 拿掉部分物品，使對方面臨k(m+1)的局面 例如上例中10個物品，只能拿1到5個,，先手方拿4個即可,，對手無論拿多少個，你下次總能拿完 從另一個角度思考這個問題,，如果物品數(shù)量隨機,，那么先手一方勝利的概率是m/(m+1),，后手方勝利的概率是1/(m+1) 二. 威佐夫博弈 Wythoff Game 有兩堆各若干的物品,，兩人輪流從其中一堆取至少一件物品,，至多不限，或從兩堆中同時取相同件物品,，規(guī)定最后取完者勝利。 直接說結論了,，若兩堆物品的初始值為（x,，y）,，且x<> 記w=（int）[（（sqrt（5）+1）/2）*z ]； 若w=x,，則先手必敗,，否則先手必勝。 代碼如下：  詳解： NimGame:異或理論 m堆n個物品,，兩人輪流取,，每次取某堆中不少于1個，最后取完者勝 詳細分析見：POJ-2234:Matches Game 所有物品數(shù)目二進制異或為0,，則先手必輸 所有物品數(shù)目二進制異或不為0,，則后手必輸 從另一個角度思考這個問題,，如果物品數(shù)量隨機，那么每個數(shù)目的每一位上1或0概率相同,， 如果有奇數(shù)個堆,，那么1的個數(shù)為偶數(shù)或者奇數(shù)的概率相同， 如果有偶數(shù)個堆,，那么1的個數(shù)為偶數(shù)的概率略大1/(m+1),， 也就是說異或結果的每一位為0或1的概率幾乎差不多，而先手必輸要求異或結果每一位都為0，其實輸?shù)母怕屎苄?/p>  三. 尼姆博弈 Nimm Game 尼姆博弈指的是這樣一個博弈游戲：有任意堆物品,，每堆物品的個數(shù)是任意的,，雙方輪流從中取物品，每一次只能從一堆物品中取部分或全部物品,，最少取一件,，取到最后一件物品的人獲勝。 結論就是：把每堆物品數(shù)全部異或起來,，如果得到的值為0,，那么先手必敗，否則先手必勝,。 代碼如下： 詳解： Wythoff Game:黃金分割 兩堆（ak,bk）(ak<><> 1.面對(0,0)局面必輸 2.面對(1,1)(2,2)...(n,n)局面必贏 (0,1)(0,2)...(0,n)局面必贏 3.如果可以使對手面臨必輸局面,，那么是必贏局面 4.如果不能使對手面臨必輸局面，那么是必輸局面 基礎：(0,0)是必輸局面;(0,1)(0 ,2)...(0,n)是必贏局面, 遞推：(1,2)是必輸局面;(1,1)是必贏局面 (1,3)(1 ,4)...(1,n)是必贏局面 (2,2),(2,3)...(2,n)是必贏局面 (3,5)是必輸局面;(3,3)(3,4)是必贏局面 (3,6)(3,7)...(3,n)是必贏局面 (5,5)(5,6)...(5,n)是必贏局面 (4,7)是必輸局面;(4,4)(4,5)(4,6)是必贏局面 (4,8)(4,8)(4,9)...(4,n)是必贏局面 (7,7)(7,8)(7,9)...(7,n)是必贏局面 (6,10)是必輸局面;(6,6)(6,7)(6,8)(6,9)是必贏局面 (6,11)(6,12)(6,13)...(6,n)是必贏局面 (10,10)(10,11)(10,12)...(10,n)是必贏局面 首先發(fā)現(xiàn)規(guī)律：（必輸局面的規(guī)律比較容易找到） ak是前面必輸局未出現(xiàn)的數(shù)中最小者,， bk=ak+k( k=0,1,2,3,...n) 下面介紹必輸局（奇異局）的最重要性質： 1,2,...,n中每一個自然數(shù),，出現(xiàn)且只出現(xiàn)在一個奇異局中。 推導：1.由于ak總是選擇未出現(xiàn)的數(shù),，所以每個數(shù)總能出現(xiàn)在奇異局中 且ak不會選擇到重復的數(shù) 2.bk=ak+k,，所以bk總是比前面所有奇異局出現(xiàn)的數(shù)都大， 所以bk不會選擇到重復的數(shù) 必贏一方的策略是：始終讓對手面對必輸局（奇異局） 給定任意局勢（a,b）,，判定（a,b）是否為必輸局的方法是： k=0,1...n 記黃金比例是φ=1.618033 ak=[k*φ],，bk=ak+k=[k*φ*φ] 如k=0,ak=0,bk=0 k=1,ak=1,bk=2 k=2,ak=3,bk=5 k=3,ak=4,bk=7 更好的一種判斷策略是 k = bk-ak ,如ak=k*φ時，當前局勢為奇異局 從勝負概率角度,，如果堆中數(shù)量隨機,，先手一方優(yōu)勢很大 （相應經(jīng)典題目是POJ-1067） 四. 斐波那契博弈： 有一堆物品，兩人輪流取物品,，先手最少取一個,，至多無上限，但不能把物品取完,，之后每次取的物品數(shù)不能超過上一次取的物品數(shù)的二倍且至少為一件,，取走最后一件物品的人獲勝。 結論是：先手勝當且僅當n不是斐波那契數(shù)（n為物品總數(shù)） 如HDU2516 5,、自招相關文章參考： 18項高校認可度最高的自招賽事,，全年時間軸匯總！自招考什么,？看全國各大名校自主招生面試題匯總?。ǜ?017年復試模式）五大學科競賽獲省二、省三也可以報考的985/211高校,，不要錯過哦自主招生報名倒計時,，準備2018自主招生可以這樣做,！競賽生必讀！想進清華北大,，除了高考還有哪些路可以走,？2017年各大高校自主招生政策及降分標準參考！熱點 | 高校自主招生考核方式和時間點全匯總2018年九大熱門工科專業(yè)前景分析清華學長分享：如何準備自主招生自薦材料自主招生 | 2018各大高校自招報名在即,這些材料再不整理就晚了教育部2017學科評估結果：計算機科學與技術專業(yè)全國大學排行榜,！一個清華保送生媽媽對競賽的感受,，自主招生家長都要看看！2017年140所重點大學最新名單,，及重點專業(yè),！附招辦聯(lián)系方式解讀 | 清華、北大自主招生核心內(nèi)容全面解讀2018自主招生各高校計算機類專業(yè)解讀,！怎樣通過2018年自主招生初審,？都需要什么材料？ ◆ ◆ 好 消 息 由清北學堂信息學金牌教研團隊策劃的 |
|
|
