算法合集之《由感性認(rèn)識到理性認(rèn)識-透析一類搏弈游戲的解答過程》.doc
《算法合集之《由感性認(rèn)識到理性認(rèn)識-透析一類搏弈游戲的解答過程》.doc》由會員分享，可在線閱讀，更多相關(guān)《算法合集之《由感性認(rèn)識到理性認(rèn)識-透析一類搏弈游戲的解答過程》.doc（18頁珍藏版）》請在裝配圖網(wǎng)上搜索。
由感性認(rèn)識到理性認(rèn)識——透析一類搏弈游戲的解答過程 一、 游戲 2 二、 從簡單入手 2 三、 類比與聯(lián)想 6 四、 證明 8 五、 推廣 11 六、 精華 12 七、 結(jié)論 16 八、 總結(jié) 17 一、 游戲 2 游戲A： 2 甲乙兩人面對若干堆石子，其中每一堆石子的數(shù)目可以任意確定。例如圖1所示的初始局面：共n=3堆，其中第一堆的石子數(shù)a1=3，第二堆石子數(shù)a2=3，第三堆石子數(shù)a3=1。兩人輪流按下列規(guī)則取走一些石子，游戲的規(guī)則如下： 每一步應(yīng)取走至少一枚石子； 每一步只能從某一堆中取走部分或全部石子； 如果誰無法按規(guī)則取子，誰就是輸家。 第一堆：a1=3 第二堆：a2=3 第三堆：a3=1 圖 1 游戲的一個初始局面 2 游戲B： 甲乙雙方事先約定一個數(shù)m，并且每次取石子的數(shù)目不能超過m個； 其余規(guī)則同游戲A。 我們關(guān)心的是，對于一個初始局面，究竟是先行者（甲）有必勝策略，還是后行者（乙）有必勝策略。 下面，我們從簡單入手，先來研究研究這個游戲的一些性質(zhì)。 二、 從簡單入手 F 用一個n元組(a1, a2, …, an)，來描述游戲過程中的一個局面。 G 可以用3元組(3, 3, 1)來描述圖1所示的局面。 @ 改變這個n元組中數(shù)的順序，仍然代表同一個局面。 G (3, 3, 1)和(1, 3, 3)，可以看作是同一個局面。 @ 如果初始局面只有一堆石子，則甲有必勝策略。 & 甲可以一次把這一堆石子全部取完，這樣乙就無石子可取了。 @ 如果初始局面有兩堆石子，而且這兩堆石子的數(shù)目相等，則乙有必勝策略。 & 因為有兩堆石子，所以甲無法一次取完； & 如果甲在一堆中取若干石子，乙便在另一堆中取同樣數(shù)目的石子； & 根據(jù)對稱性，在甲取了石子之后，乙總有石子可??； & 石子總數(shù)一直在減少，最后必定是甲無石子可取。 G 對于初始局面(1)，甲有必勝策略，而初始局面(3, 3)，乙有必勝策略。 F 局面的加法：(a1, a2, …, an) + (b1, b2, …, bm) = (a1, a2, …, an, b1, b2, …, bm)。 G (3) + (3) + (1) = (3, 3) + (1) = (3, 3, 1)。 F 對于局面A, B, S，若S=A+B，則稱局面S可以分解為“子局面”A和B。 G 局面(3, 3, 1)可以分解為(3, 3)和(1)。 @ 如果初始局面可以分成兩個相同的“子局面”，則乙有必勝策略。 & 設(shè)初始局面S=A+A，想象有兩個桌子，每個桌子上放一個A局面； & 若甲在一個桌子中取石子，則乙在另一個桌子中對稱的取石子； & 根據(jù)對稱性，在甲取了石子之后，乙總有石子可?。? & 石子總數(shù)一直在減少，最后必定是甲無石子可取。 G 初始局面(2, 2, 5, 5, 5, 5, 7, 7)，可以分成兩個(2, 5, 5, 7)，故乙有必勝策略。 F 對于局面S，若先行者有必勝策略，則稱“S勝”。 F 對于局面S，若后行者有必勝策略，則稱“S負(fù)”。 G 若A=(1)，B=(3, 3)，C=(2, 2, 5, 5, 5, 5, 7, 7)，則A勝，B負(fù)，C負(fù)。 G 我們所關(guān)心的，就是如何判斷局面的勝負(fù)。 @ 如果局面S勝，則必存在取子的方法S→T，且T負(fù)。 @ 如果局面S負(fù)，則對于任意取子方法S→T，有T勝。 2 設(shè)初始局面S可以分解成兩個子局面A和B（分解理論）。 @ 若A和B一勝一負(fù)，則S勝。 & 不妨設(shè)A勝B負(fù)； & 想象有兩個桌子A和B，桌子上分別放著A局面和B局面； & 因為A勝，所以甲可以保證取桌子A上的最后一個石子； & 與此同時，甲還可以保證在桌子B中走第一步的是乙； & 因為B負(fù)，所以甲還可以保證取桌子B中的最后一個石子； & 綜上所述，甲可以保證兩個桌子上的最后一個石子都由自己取得。 @ 若A負(fù)B負(fù)，則S負(fù)。 & 無論甲先從A中取，還是先從B中取，都會變成一勝一負(fù)的局面； & 因此，乙面臨的局面總是“勝”局面，故甲面臨的S是“負(fù)”局面。 @ 若B負(fù)，則S的勝負(fù)情況與A的勝負(fù)情況相同。 @ 若A勝B勝，則有時S勝，有時S負(fù)。 @ 如果S=A+C+C，則S的勝負(fù)情況與A相同。 & 令B=C+C，則S=A+B且B負(fù)，故S的勝負(fù)情況與A相同。 G 圖1所示的初始局面(3, 3, 1) = (3) + (3) + (1)，與局面(1)的勝負(fù)情況相同。 G 圖1中所示的初始局面(3, 3, 1)是“勝”局面，甲有必勝策略。 F 稱一個石子也沒有的局面為“空局面”。 @ 空局面是“負(fù)”局面。 F 如果局面S中，存在兩堆石子，它們的數(shù)目相等。用T表示從S中把這兩堆石子拿掉之后的局面，則稱“S可以簡化為T”。 G 局面(2, 2, 2, 7, 9, 9)可以簡化為(2, 2, 2, 7)，還可以進(jìn)一步簡化為(2, 7)。 @ 一個局面的勝負(fù)情況，與其簡化后的局面相同。 G 三個局面(2, 2, 2, 7, 9, 9)、(2, 2, 2, 7)和(2, 7)，勝負(fù)情況都相同。 F 不能簡化的局面稱為“最簡局面”。 G 局面 (2, 7)是最簡局面。 @ 最簡局面中不會有兩堆相同的石子，故可以用一個集合來表示最簡局面。 G 最簡局面(2, 7)可以用集合{2, 7}來表示。 * 如果只關(guān)心局面的勝負(fù)，則一個局面可以用一個集合來描述。 G 圖1所示的局面(3, 3, 1)，可以用集合{1}來描述。 如果用搜索（搏弈樹）的方法來解這個游戲，則采用集合來表示一個局面，比采用多元組來表示一個局面，搜索量將有所減少，但時間復(fù)雜度仍然很高。 能不能進(jìn)一步簡化一個局面的表示呢？ 三、 類比與聯(lián)想 2 二進(jìn)制加法 本文的“二進(jìn)制加法”，是指不進(jìn)位的二進(jìn)制加法，也可以理解為邏輯里的“異或”操作。 1 + 0 = 1； 0 + 1 = 1； 0 + 0 = 0； 1 + 1 = 0。 2 二進(jìn)制的加法 VS 局面的加法 大寫字母AB表示局面，小寫字母ab表示二進(jìn)制 若A和B相同，則A+B負(fù)；若a和b相等，則a+b=0 若A勝B負(fù)，則A+B勝；若a=1且b=0，則a+b=1 若B勝A負(fù)，則A+B勝；若b=1且a=0，則a+b=1 若A負(fù)B負(fù)，則A+B負(fù)；若a=0且b=0，則a+b=0 …… Z 如果用二進(jìn)制1和0，分別表示一個局面的勝或負(fù) @ 局面的加法，與二進(jìn)制的加法有很多類似之處。 若A勝B勝，則A+B有時勝，有時負(fù)；若a=1且b=1，則a+b=0。 F 二進(jìn)制數(shù)的加法：對二進(jìn)制數(shù)的每一位，都采用二進(jìn)制的加法。 0011 + 1010 1001 G ， 1010 + 1010 0000 。 2 二進(jìn)制數(shù)的加法 VS 局面的加法 大寫字母AB表示局面，小寫字母ab表示二進(jìn)制數(shù) 若A和B相同，則A+B負(fù)；若a和b相等，則a+b為0 若A勝B負(fù)，則A+B勝；若a≠0且b=0，則a+b≠0 若B勝A負(fù)，則A+B勝；若b≠0且a=0，則a+b≠0 若A負(fù)B負(fù)，則A+B負(fù)；若a=0且b=0，則a+b=0 若A勝B勝，則A+B有時勝，有時負(fù) 若a≠0且b≠0，則有時a+b≠0，有時a+b=0 …… Z 如果用二進(jìn)制數(shù)s來表示一個局面S的勝或負(fù)，S勝則s≠0，S負(fù)則s=0 @ 局面的加法，與二進(jìn)制數(shù)的加法，性質(zhì)完全相同。 Z 能否用一個二進(jìn)制數(shù)，來表示一個局面呢？ F 用符號#S，表示局面S所對應(yīng)的二進(jìn)制數(shù)。 Z 如果局面S只有一堆石子，則用這一堆石子數(shù)目所對應(yīng)的二進(jìn)制數(shù)來表示S。 G #(5)=5=101。 Z 若局面S=A+B，則#S=#A+#B。 G 局面(3, 3)=(3)+(3)，所以#(3, 3)=#(3)+#(3)=11+11=0。 G 局面(3, 3, 1)=(3, 3)+(1)，所以#(3, 3, 1)=#(3, 3)+#(1)=0+1=1。 F 函數(shù)f：若局面S只有一堆石子，設(shè)S={a1}，則f(a1)=#S，即f(a1)=#(a1)。 G 對于游戲A來說，#(5)=101，所以f(5)=101。 G 對于游戲A來說，f(x)就是x所對應(yīng)的二進(jìn)制數(shù)。換句話說，f(x)=x。 @ 設(shè)局面S=(a1, a2, …, an)，即S=(a1)+(a2)+…+(an)，則#S=f(a1)+f(a2)+…+f(an)。 G #(3, 3, 1)=#((3)+(3)+(1))=#(3)+#(3)+#(1)=f(3)+f(3)+f(1)=11+11+1=1。 Z 對于局面S，若#S=0，則S負(fù)；若#S≠0，則S勝。 四、 證明 @ 二進(jìn)制數(shù)a, b，若a + b = 0，當(dāng)且僅當(dāng)a = b。 1011 + 1011 0000 1011 + 1001 0010 G @ 二進(jìn)制數(shù)a, b, s，若a + b = s，則a = b + s。 0011 + 1010 1001 1001 + 1010 0011 G @ 二進(jìn)制數(shù)a1+a2+…+an=p≠0，則必存在k，使得ak+p下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 由感性認(rèn)識到理性認(rèn)識-透析一類搏弈游戲的解答過程 算法 感性 認(rèn)識到 理性認(rèn)識 透析 一類 游戲 解答 過程
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://m.appdesigncorp.com/p-9369400.html