算法合集之淺析解對策問題的兩種思路-閱讀頁
2025-05-22 01:33本頁面
【正文】 證 明 ： （一） F1(=2)， F2(=3)時(shí)，顯然成立。 設(shè)先手取 K粒石子 。 后手獲勝，先手?jǐn)? K (NK,2K) 淺析解 “ 對策問題 ” 的兩種思路 思路二： 特殊性方法 證 明 ： Fi1 Fi Fi+1 K （一） F1(=2)， F2(=3)時(shí)，顯然成立。 設(shè)先手取 K粒石子 。 (Fi,X) 淺析解 “ 對策問題 ” 的兩種思路 思路二： 特殊性方法 證 明 ： （一） F1(=2)， F2(=3)時(shí)，顯然成立。 設(shè)先手取 K粒石子 。 （二）若 F1至 Fi成立，則 Fi+1成立。 （ 1）若 K≥Fi1 后手得狀態(tài) (NK,2K) 后手獲勝，先手?jǐn)? （ 2）若 K Fi1 Fi1 Fi Fi+1 后手獲勝，先手?jǐn)? 由（ 1） （ 2）得 Fi+1時(shí)，結(jié)論成立。 淺析解 “ 對策問題 ” 的兩種思路 思路二： 特殊性方法 結(jié)論 2：狀態(tài) (N， N1） N∈ {F}且 N2，先手必勝。 例如 POI99 《 多邊形 》 ， IOI96的 取數(shù)字也 可以用 “ 特殊性 方法 ” 來解決。 淺析解 “ 對策問題 ” 的兩種思路 思路二： 特殊性方法 l 逆向分析 從簡單的結(jié)局或殘局開始 ， 自底向上分析 。 淺析解 “ 對策問題 ” 的兩種思路 一般性方法 與 特殊性方法 1一次可取先前對方所取石子數(shù)的 3倍 《取石子》問題的推廣： 1一次可取先前對方所取石子數(shù)的 4倍 1一次可取先前對方所取石子數(shù)的 5倍 1一次可取先前對方所取石子數(shù)的 K倍 1………… 一 般 性 方 法 特 殊 性 方 法 VS 淺析解 “ 對策問題 ” 的兩種思路 一般性方法 與 特殊性方法 l 思路方向 一般性方法 ： 自頂而 下 考察所有狀態(tài)勝負(fù) 特殊性方法 ： 自底而上 研究一類平衡狀態(tài) 淺析解 “ 對策問題 ” 的兩種思路 一般性方法 與 特殊性方法 l 思路方向 一般性方法 ： 有通行勝負(fù)規(guī)則 特殊性方法 ： 無通行勝負(fù)規(guī)則 l 勝負(fù)規(guī)則 淺析解 “ 對策問題 ” 的兩種思路 一般性方法 與 特殊性方法 l 思路方向 l 勝負(fù)規(guī)則 一般性方法 ： 關(guān)鍵是動(dòng)態(tài)規(guī)劃或記憶化搜索的預(yù)處理 。 l 實(shí)現(xiàn)方法 淺析解 “ 對策問題 ” 的兩種思路 一般性方法 與 特殊性方法 l 思路方向 l 勝負(fù)規(guī)則 一般性方法 ： 有通行規(guī)則可套用，應(yīng)用面十分廣泛；但是受“拓?fù)浣Y(jié)構(gòu)”限制，而且需考察所有狀態(tài)，時(shí)空復(fù)雜度也有可能很高。 l 優(yōu)點(diǎn) 缺點(diǎn) l 實(shí)現(xiàn)方法 淺析解 “ 對策問題 ” 的兩種思路 一般性方法 與 特殊性方法 l 思路方向 l 勝負(fù)規(guī)則 在 “ 對策問題 ” 中，一個(gè)狀態(tài)要么是先手必勝，要么是先手必?cái)?！因此，在對局時(shí)，我方要做的就是占據(jù)必勝，把必?cái)×艚o對方。 “ 特殊性方法 ” 從特殊的角度，考察一類狀態(tài)，來決定對局策略。本文通過《取石子》問題，簡單的闡述了解決一類 “ 對策問題 ”的兩種思路，也是我的一點(diǎn)心得，但并不能涵蓋萬一。在解其他類型的題目時(shí)，也同樣可以應(yīng)用這兩種思考方法。 ” 我們還需要不斷努力 ， 不斷實(shí)踐 ， 不斷探索
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1