算法合集之淺析解對(duì)策問(wèn)題的兩種思路(編輯修改稿)
2025-06-07 01:33 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 何取勝呢 ？ 事實(shí)上 ， 甲只要先在圓桌中心放下一枚硬幣 ， 此后無(wú)論乙怎么放 ， 甲總在其關(guān)于中心對(duì)稱(chēng)處放一枚 ， 最終甲必然獲勝 。 甲 乙 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 在這個(gè)例子中 ， 甲找到了一種必勝的狀態(tài) 。 這種狀態(tài)是具有某種 “ 平衡性 ” 的 ， 稱(chēng)之為 “ 平衡狀態(tài) ” 。 每當(dāng)乙破壞了 “ 平衡 ” 后 ， 甲立即使其恢復(fù) “ 平衡 ” ， 直到結(jié)局 。 先看一個(gè)簡(jiǎn)單的例子： 在一個(gè)圓形桌面上 ， 甲 、 乙輪流放 5分硬幣 ， 不許重疊 ， 甲先放 ，首先放不下硬幣的一方為負(fù) 。 甲如何取勝呢 ？ 甲 乙 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 那么怎樣尋找 “ 對(duì)策問(wèn)題 ” 中的“ 平 衡狀態(tài) ” 呢 ？ 如何確定 “ 決策規(guī)律 ” 使我 方在平衡被破壞后必然能恢復(fù)呢 ？ 先看一個(gè)簡(jiǎn)單的例子： 在一個(gè)圓形桌面上 ， 甲 、 乙輪流放 5分硬幣 ， 不許重疊 ， 甲先放 ，首先放不下硬幣的一方為負(fù) 。 甲如何取勝呢 ？ 甲 乙 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 “ 一般性方法 ” 是從初始狀態(tài)開(kāi)始， 自頂而下 建立 “ 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) ” ?，F(xiàn)在，不妨反其道而行之，從結(jié)局或小規(guī)模殘局開(kāi)始，自底向上 分析。 甲必?cái)?： 甲必勝 ： 2 3 4 5 6 7 8 …… …… 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 Fibonacci 數(shù)列 “ 一般性方法 ” 是從初始狀態(tài)開(kāi)始， 自頂而下 建立 “ 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) ” 。現(xiàn)在，不妨反其道而行之，從結(jié)局或小規(guī)模殘局開(kāi)始，自底向上 分析。 甲必?cái)?： 甲必勝 ： 2 3 4 5 6 7 8 …… …… 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 猜 想 ： 設(shè) {F}為 Fibonacci數(shù)列 （ F1=2， F2=3， FK=FK1+FK2） 初始時(shí)有 N粒石子，若 N∈ {F}則先手必?cái)?，否則先手必勝。 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 性質(zhì) 1： 若 K≥N， 則狀態(tài) （ N,K） 先手必勝 。 性質(zhì) 2： 若狀態(tài)（ N,N1）先手必?cái)。瑒t狀態(tài)（ N,K）K N 先手必?cái)?。 性質(zhì) 3： 若狀態(tài)（ N,K） K N，則最后一次取走的石子數(shù)目不超過(guò) 2N/3。 性質(zhì) 4： 4Fi1/3 Fi （ F1=2， F2=3， FK=FK1+FK2）。 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 結(jié)論 1：狀態(tài) (Fi， A） A Fi 先手必?cái) ? 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 證 明 ： （一） F1(=2)， F2(=3)時(shí)，顯然成立。 Fi1 Fi Fi+1 （二）若 F1至 Fi成立，則 Fi+1成立。 設(shè)先手取 K粒石子 。 （ 1）若 K≥Fi1 后手得狀態(tài) (NK,2K) 2K≥2Fi1≥Fi1+Fi2= Fi NK 由性質(zhì) 1，后手獲勝。 后手獲勝，先手?jǐn)? K (NK,2K) 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 證 明 ： Fi1 Fi Fi+1 K （一） F1(=2)， F2(=3)時(shí)，顯然成立。 （二）若 F1至 Fi成立，則 Fi+1成立。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1