算法合集之《由感性認識到理性認識——透析一類搏弈游戲的解答過程》-全文預覽
【正文】 ? 甲乙兩人取石子游戲及其類似的游戲； ? 每一步只能對某一堆石子進行操作； ? 每一步操作的限制，只與這堆石子的數(shù)目或一些常數(shù)有關(guān)； ? 操作在有限步內(nèi)終止，并不會出現(xiàn)循環(huán)； ? 誰無法繼續(xù)操作，誰就是輸家。 ? 令非負整數(shù)集為全集，集合 G(x)表示集合 g(x)的補集。 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 16 七、 結(jié)論 ? 此類搏弈游戲的一般性解法： ? 用一個 n 元組 (a1, a2, … , an)，來描述游戲過程中的一個局面。 ? 設(shè)局面 S=(a1, a2, … , an)， S=f(a1)+f(a2)+…+f(a n)，采用二進制數(shù)的加法。 ? 如果 g(a1)={0, 1, 2, 5, 7, 8, 9}，則 f(a1)=3，滿足要求。（充要） (5) (1, 4) (2, 3) (7) $(7)={(5), (1, 4), (2, 3)} g(7)={(5), (1, 4), (2, 3)} 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 14 ? ? 若 S≠ 0，則先行者必然存在一種取子方法 S→T ，且 T=0。 ? 在游戲 B 中，若 m=4，則 g(9)={(8), (7), (6), (5)}， g(2)={(1), (0)}。 ? 在游戲 B 中，若 m=4，則 $(9)={(8), (7), (6), (5)}， $(2)={(1), (0)}。 ? 若 S=0，則無論先行者如何取子 S→T ，都有 T≠ 0。 ? 游戲 B 中， f(x) = x mod (m + 1)。 六、 精華 ? 回憶游戲 A 的結(jié)論，以及它在游戲 B 上的推廣，對于游戲 C，我們的想法是 ? 設(shè)計一個函數(shù) f，把函數(shù) f 的值看作是二進制數(shù)。但是，前面所列出的，游戲 A 的關(guān)鍵性質(zhì)，游戲 C 卻都具有。 圖 2 游戲的一個初始局面 ? 如果甲第一步選擇取第一排 34 這兩 枚石子，之后無論是甲還是乙，都不能一次取走 25 這兩枚石子。這是因為兩個游 戲的規(guī)則相當類似。 ? 對于任意初始局面 S=(a1, a2, … , an)，令 S=f(a1)+f(a2)+… +f(an)。令 S=a1+a2+… +an。 ? 若 S=0，則 S 負；若 S≠ 0，則 S 勝。 ? 先行者只能從某一堆中取若干石子，不妨設(shè)他選擇的就是第 1 堆； ? 設(shè)先行者從第 1 堆中取了 x 個石子，用 T 表示取完之后的局面； ? 設(shè) S=(a1, a2, … , an)，則 T=(a1–x, a2, … , an)； ? S=f(a1)+(a2, …, an)=0，故 f(a1)=(a2, …, an)； ? T=f(a1–x)+(a2, …, an)=f(a1–x)+f(a1)； ? x0→f( a1)≠ f(a1–x)→f (a1)+f(a1–x)≠ 0→ T≠ 0。 ? ? 二進制數(shù) a, b, s，若 a + b = s，則 a = b + s。 ? 設(shè)局面 S=(a1, a2, … , an)，即 S=(a1)+(a2)+… +(an)，則 S=f(a1)+f(a2)+… +f(an)。 ? 函數(shù) f：若局面 S 只有一堆石子，設(shè) S={a1}，則 f(a1)=S，即 f(a1)=(a1)。 ? (5)=5=101。 ? ， 。 ? 二進制的加法 VS 局面的加法 ? 大寫字母 AB 表示局面，小寫字母 ab 表示二進制 ? 若 A 和 B 相同，則 A+B 負；若 a 和 b 相等，則 a+b=0 ? 若 A 勝 B 負，則 A+B 勝；若 a=1 且 b=0，則 a+b=1 ? 若 B 勝 A 負，則 A+B 勝；若 b=1 且 a=0，則 a+b=1 ? 若 A 負 B 負，則 A+B 負；若 a=0 且 b=0，則 a+b=0 ? ?? ? 如果用二進制 1 和 0，分別表示一個局面的勝或負 ? 局面的加法，與二進制的加法有很多類似之處。 ? 如果只關(guān)心局面的勝負，則一個局面可以用一個集合來描述。 ? 不能簡化的局面稱為“最簡局面”。用 T 表示從 S 中把這兩堆石子拿掉之后的局面，則稱“ S 可以簡化為 T”。 ? 圖 1 中所示的初始局面 (3, 3, 1)是“勝”局面，甲有必勝策略。 ? 若 A 勝 B 勝，則有時 S 勝，有時 S 負。 ? 不妨設(shè) A 勝 B 負； ? 想象有兩個桌子 A 和 B，桌子上分別放著 A 局面和 B 局面； ? 因為 A 勝，所以甲可以保證取桌子 A 上的最后一個石子； ? 與此同時，甲還可以保證在桌子 B 中走第一步的是乙； ? 因為 B 負，所以甲還可以保證取桌子 B 中的最后一個石子； ? 綜上所述，甲可以保證 兩個桌子上的最后一個石子都由自己取得。 ? 如果局面 S 勝，則必存在取子的方法 S→T ，且 T 負。 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 4 ? 對于局面 S，若先行者有必勝策略，則稱“ S 勝”。 ? 局面 (3, 3, 1)可以分解為 (3, 3)和 (1)。 ? 對于初始局面 (1)，甲有必勝策略，而初始局面 (3, 3)，乙有必勝策略。 ? 如果初始局面只有一堆石子，則甲有必勝策略。 二、 從簡單入手 ? 用一個 n 元組 (a1, a2, … , an)，來描述游戲過程中的一個局面。兩人輪流按下列規(guī)則取走一些石子，游戲的規(guī)則如下： ? 每一步應取走至少一枚石子； ? 每一步只能從某一堆中 取走部分或全部石子； ? 如果誰無法按規(guī)則取子，誰就是輸家。例如圖 1所示的初始局面：共 n=3 堆，其中第一堆的石子數(shù) a1=3，第二堆石子數(shù) a2=3，第三堆石子數(shù) a3=1。 下面，我們從簡單入手，先來研究研究這個游戲的一些性質(zhì)。 ? (3, 3, 1)和 (1, 3, 3)，可以看作是同一個局面。 ? 因為有兩堆石子，所以甲無法一次取完； ? 如果甲在
試題試卷相關(guān)推薦
鄂ICP備17016276號-1