三個博弈基礎

(一)巴什博奕(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者勝。
(二)威佐夫博奕(Wythoff Game):有兩堆各若干個物品,兩個人輪流從某一堆或同時從兩堆中取同樣多的物品,規定每次至少取一個,多者不限,最后取光者得勝。
???? 這種情況下是頗為復雜的。我們用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示兩堆物品的數量并稱其為局勢,如果甲面對(0,0),那么甲已經輸了,這種局勢我們稱為奇異局勢。前幾個奇異局勢是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。
???? 可以看出,a0=b0=0,ak是未在前面出現過的最小自然數,而 bk= ak + k,奇異局勢有如下三條性質:
???? 1。任何自然數都包含在一個且僅有一個奇異局勢中。
???? 由于ak是未在前面出現過的最小自然數,所以有ak > ak-1 ,而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性質1。成立。
???? 2。任意操作都可將奇異局勢變為非奇異局勢。
???? 事實上,若只改變奇異局勢(ak,bk)的某一個分量,那么另一個分量不可能在其他奇異局勢中,所以必然是非奇異局勢。如果使(ak,bk)的兩個分量同時減少,則由于其差不變,且不可能是其他奇異局勢的差,因此也是非奇異局勢。
???? 3。采用適當的方法,可以將非奇異局勢變為奇異局勢。
???? 假設面對的局勢是(a,b),若 b = a,則同時從兩堆中取走 a 個物體,就變為了奇異局勢(0,0);如果a = ak ,b > bk,那么,取走b?? - bk個物體,即變為奇異局勢;如果 a = ak ,?? b < bk ,則同時從兩堆中拿走 ak - ab - ak個物體,變為奇異局勢( ab - ak , ab - ak+ b - ak);如果a > ak ,b= ak + k,則從第一堆中拿走多余的數量a - ak 即可;如果a < ak ,b= ak + k,分兩種情況,第一種,a=aj (j < k),從第二堆里面拿走 b - bj 即可;第二種,a=bj (j < k),從第二堆里面拿走 b - aj 即可。
???? 從如上性質可知,兩個人如果都采用正確操作,那么面對非奇異局勢,先拿者必勝;反之,則后拿者取勝。
???? 那么任給一個局勢(a,b),怎樣判斷它是不是奇異局勢呢?我們有如下公式:
???? ak =[k(1+√5)/2],bk= ak + k?? (k=0,1,2,...,n 方括號表示取整函數)奇妙的是其中出現了黃金分割數(1+√5)/2 = 1。618...,因此,由ak,bk組成的矩形近似為黃金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1+ j + 1,若都不是,那么就不是奇異局勢。然后再按照上述法則進行,一定會遇到奇異
局勢。
(三)尼姆博奕(Nimm Game):有三堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規定每次至少取一個,多者不限,最后取光者得勝。
???? 這種情況最有意思,它與二進制有密切關系,我們用(a,b,c)表示某種局勢,首先(0,0,0)顯然是奇異局勢,無論誰面對奇異局勢,都必然失敗。第二種奇異局勢是(0,n,n),只要與對手拿走一樣多的物品,最后都將導致(0,0,0)。仔細分析一下,(1,2,3)也是奇異局勢,無論對手如何拿,接下來都可以變為(0,n,n)的情形。
???? 計算機算法里面有一種叫做按位模2加,也叫做異或的運算,我們用符號(+)表示這種運算。這種運算和一般加法不同的一點是1+1=0。先看(1,2,3)的按位模2加的結果:
1 =二進制01
2 =二進制10
3 =二進制11 (+)
———————
0 =二進制00 (注意不進位)
???? 對于奇異局勢(0,n,n)也一樣,結果也是0。
???? 任何奇異局勢(a,b,c)都有a(+)b(+)c =0。
如果我們面對的是一個非奇異局勢(a,b,c),要如何變為奇異局勢呢?假設 a < b< c,我們只要將 c 變為 a(+)b,即可,因為有如下的運算結果: a(+)b(+)(a(+)b)=(a(+)a)(+)(b(+)b)=0(+)0=0。要將c 變為a(+)b,只要從 c中減去 c-(a(+)b)即可。
???? 例1。(14,21,39),14(+)21=27,39-27=12,所以從39中拿走12個物體即可達到奇異局勢(14,21,27)。
???? 例2。(55,81,121),55(+)81=102,121-102=19,所以從121中拿走19個物品就形成了奇異局勢(55,81,102)。
???? 例3。(29,45,58),29(+)45=48,58-48=10,從58中拿走10個,變為(29,45,48)。
???? 例4。我們來實際進行一盤比賽看看:
???????? 甲:(7,8,9)->(1,8,9)奇異局勢
???????? 乙:(1,8,9)->(1,8,4)
???????? 甲:(1,8,4)->(1,5,4)奇異局勢
???????? 乙:(1,5,4)->(1,4,4)
???????? 甲:(1,4,4)->(0,4,4)奇異局勢
???????? 乙:(0,4,4)->(0,4,2)
???????? 甲:(0.4,2)->(0,2,2)奇異局勢
???????? 乙:(0,2,2)->(0,2,1)
???????? 甲:(0,2,1)->(0,1,1)奇異局勢
???????? 乙:(0,1,1)->(0,1,0)
???????? 甲:(0,1,0)->(0,0,0)奇異局勢
???????? 甲勝。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/444502.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/444502.shtml
英文地址,請注明出處:http://en.pswp.cn/news/444502.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

(十五)nodejs循序漸進-高性能游戲服務器框架pomelo之Protobuf模塊

消息壓縮 在實際編程中&#xff0c;為了減少數據傳輸帶寬的消耗&#xff0c;提高傳輸效率&#xff0c;pomelo提供了對消息的壓縮&#xff0c;包括基于字典的對route的壓縮和基于protobuf的對具體傳輸數據的壓縮。 route壓縮 在實際編程中&#xff0c;網絡帶寬的有效數據負載…

C++:13---多態和虛函數表

多態的意思為“以一個public基類的指針/引用,尋址一個派生類對象”。 “多態”的關鍵在于通過基類指針或引用調用一個虛函數時,編譯時不確定到底調用的是基類還是派生類的函數,運行時才確定。這是如何實現的呢?請看下面的程序,該程序演示了多態類對象存儲空間的大小。 #in…

leetcode96. 不同的二叉搜索樹 動歸vs數學?

給定一個整數 n&#xff0c;求以 1 ... n 為節點組成的二叉搜索樹有多少種&#xff1f; 示例: 輸入: 3 輸出: 5 解釋: 給定 n 3, 一共有 5 種不同結構的二叉搜索樹: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 …

Redis:06---數據庫管理

一、服務器中的數據庫Redis服務器將所有數據庫都保存在服務器狀態redis.h/redisServer結構的db數組中&#xff0c;db數組的每個項都是一個redis.h/redisDb結構&#xff0c;每個redisDb結構代表一個數據庫&#xff1a;struct redisServer {// ...redisDb *db; // 一個數組&#…

leetcode95. 不同的二叉搜索樹 II

給定一個整數 n&#xff0c;生成所有由 1 ... n 為節點所組成的二叉搜索樹。 示例: 輸入: 3 輸出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解釋: 以上的輸出對應以下 5 種不同結構的二叉搜索樹&#xff1a; 1 3 …

在同一局域網下連接共享文件夾失敗,提示:你不能訪問共享文件夾,因為你組織的安全策略阻止未經身份驗證的來賓訪問

1.嘗試打開guest訪問。 &#xff08;1&#xff09;使用鍵盤 win R 鍵&#xff0c;打開運行窗口&#xff0c;并輸入 gpedit.msc 打開本地組策略編輯器窗口 &#xff08;2&#xff09;選擇計算機配置------->管理模板-------->網絡-------->Lanman工作站。 &#…

(十五)深入淺出TCPIP之Hello CDN

什么是CDNCDN 其實是 Content Delivery Network 的縮寫&#xff0c;即“內容分發網絡”。CDN是將媒體資源&#xff0c;動靜態圖片(Flash) &#xff0c;HTML, CSS, JS等等內容緩存到距離你更近的互聯網數據中心&#xff0c;從而讓用戶進行共享資源&#xff0c;實現縮減站點間的響…

Redis:07---Redis數據結構

一、五大數據結構Redis可以存儲鍵與5種不同數據結構類型之間的映射&#xff0c;這5種數據結構類型分別為&#xff1a;STRING&#xff1a;字符串LIST&#xff1a;列表SET&#xff1a;集合HASH&#xff1a;散列ZSET&#xff1a;有序集合TYPE命令用來獲得鍵的數據類型&#xff0c;…

C++:14---虛繼承,虛函數,多態

一、多級混合繼承 下面先介紹菱形繼承 //菱形繼承 class A { public: int data; }; class B:public A { public: int data; }; class C:public A { public: int data; }; class D:public B,public C { public: int data; };int main() { D c; D.data=1; D.B::data=2;//訪問B中的…

(十四)nodejs循序漸進-高性能游戲服務器框架pomelo之開發Treasures游戲

#Tutorial 2 -- Treasures ##描述 Treasures 游戲是從 LordOfPomelo 中抽取出來&#xff0c;去掉了大量的游戲邏輯&#xff0c;用以更好的展示 Pomelo 框架的用法以及運作機制。 Treasures 很簡單&#xff0c;輸入一個用戶名后&#xff0c;會隨機得到一個游戲角色&#xff0c;…

leetcode243. 最短單詞距離(vip題)好像挺簡單?

給定一個單詞列表和兩個單詞 word1 和 word2&#xff0c;返回列表中這兩個單詞之間的最短距離。 示例: 假設 words ["practice", "makes", "perfect", "coding", "makes"] 輸入: word1 “coding”, word2 “practice”…

談談蘋果應用內支付(IAP)的坑

一、請求商品 下面是請求商品的代碼: - (void)validateProductIdentifier:(NSArray *)productIdentifier {SKProductsRequest *productRequest = [[SKProductsRequest alloc] initWithProductIdentifiers:[NSSet setWithArray:productIdentifier]];self.request = productRe…

leetcode204. 計數質數(vip題)

統計所有小于非負整數 n 的質數的數量。 示例: 輸入: 10 輸出: 4 解釋: 小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。 思路&#xff1a;篩法&#xff0c;見代碼。 class Solution {public int countPrimes(int n) {// 1. 給數加上標記byte[] nums new byte[n];for (i…

如何使得客戶端和服務器端完美配合做IOS應用內付費

配置Developer.apple.com 登錄到Developer.apple.com,然后進行以下步驟: 為應用建立建立一個不帶通配符的App ID用該App ID生成和安裝相應的Provisioning Profile文件。配置iTunes Connect 登錄到iTunes Connet,然后進行以下步驟: 用該App ID創建一個新的應用。在該應用中…

IOS內購流程從0-1手把手教會

蘋果掌握著可能是全球最重要的APP分發渠道,然而30%的抽成近年來也被人批評,現在蘋果似乎也看到反對意見了,從2021年1月1日開始,部分小型企業的分成費用降低到15%。 據報道,蘋果將于2021年1月1日啟動App Store小企業項目,會降低他們的抽成費用。針對年收入不足100萬美元的…

leetcode217. 存在重復元素(vip題)超簡單

給定一個整數數組&#xff0c;判斷是否存在重復元素。 如果任何值在數組中出現至少兩次&#xff0c;函數返回 true。如果數組中每個元素都不相同&#xff0c;則返回 false。 示例 1: 輸入: [1,2,3,1] 輸出: true 示例 2: 輸入: [1,2,3,4] 輸出: false 示例 3: 輸入: [1,1,…

訂單數據持久化和驗證相關解決方案

訂單數據持久化 有時候蘋果支付在支付完成后,從蘋果服務器返回收據的過程中可能會掉單(可能是網絡問題,可能是蘋果BUG,也有一部分是開發者自身埋的坑),因此我們需要一個訂單持久化的機制來保障。 首先根據內購商品ID(此商品ID是在蘋果后臺建好的內購商品)、用戶信息(…

IOS iap處理邏輯流程圖再次梳理

序言: 本文補全一下iOS iap處理邏輯。 iap處理邏輯 蘋果退單wiki:https://developer.apple.com/documentation/storekit/in-app_purchase/handling_refund_notifications 一、上圖主要處理了以下業務: 普通購買 自動續訂訂閱 補單處理 預防黑產 退單處理 二、除了上述業…

(十七)深入淺出TCPIP之HTTP和HTTPS

超文本傳輸協議HTTP協議被用于在Web瀏覽器和網站服務器之間傳遞信息&#xff0c;HTTP協議以明文方式發送內容&#xff0c;不提供任何方式的數據加密&#xff0c;如果攻擊者截取了Web瀏覽器和網站服務器之間的傳輸報文&#xff0c;就可以直接讀懂其中的信息&#xff0c;因此&…

leetcode283. 移動零 比官方更好的解法。

給定一個數組 nums&#xff0c;編寫一個函數將所有 0 移動到數組的末尾&#xff0c;同時保持非零元素的相對順序。 示例: 輸入: [0,1,0,3,12] 輸出: [1,3,12,0,0] 說明: 必須在原數組上操作&#xff0c;不能拷貝額外的數組。 盡量減少操作次數。 思路&#xff1a;記錄0的個…