算法合集之淺析解對(duì)策問(wèn)題的兩種思路(已修改)
2025-05-18 01:33 本頁(yè)面
【正文】 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 —— 從 《 取石子 》 問(wèn)題談起 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 內(nèi)容提要： 運(yùn) 籌 學(xué) 規(guī)劃論 動(dòng)態(tài)規(guī)劃 圖 論 對(duì)策論 排隊(duì)論 存儲(chǔ)論 等等 線性規(guī)劃 整數(shù)規(guī)劃 等等 本文所要探討的正是此類(lèi)“ 對(duì)策問(wèn)題 ” 。 運(yùn)籌學(xué)是一門(mén)十分年輕的學(xué)科 ， 內(nèi)容包括：規(guī)劃論 、 圖論 、對(duì)策論 、 排隊(duì)論等 。 競(jìng)賽中最常出現(xiàn)的對(duì)策問(wèn)題是：有兩個(gè)局中人 ， 在對(duì)方時(shí)刻采取最優(yōu)策略的情況下 ， 己方要么有必勝策略 ， 要么必?cái)?。 由于對(duì)局的復(fù)雜性和取勝的多樣性 ， 文章將從一道經(jīng)典的 “ 對(duì)策問(wèn)題 ” —— 《 取石子 》 談起 ，著重闡述兩種基本思想方法 。 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 問(wèn) 題 描 述 有 N粒石子 ， 甲乙兩人輪流從中拿取 ， 一次至少拿一粒 ， 至多拿先前對(duì)方一次所取石子數(shù)目的兩倍 。 甲先拿 ， 開(kāi)始甲可以拿任意數(shù)目的石子 （ 但不得拿完 ） 。 最先沒(méi)有石子可拿的一方為敗方 。 請(qǐng)問(wèn) ， 甲能否獲勝 ？ （ 1 N 100） 解 析 在本題中，影響勝敗的有兩個(gè)關(guān)鍵因素： l 當(dāng)前石子總數(shù) N l 當(dāng)前一次最多可拿的石子數(shù) K 用這兩個(gè)因素 （ N， K） 來(lái)表示當(dāng)前局面的 “ 狀態(tài) ” 。題目要求的是判斷狀態(tài) （ N， N1） 是先手必勝還是必?cái) ? 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 用一個(gè)簡(jiǎn)單例子分析：假設(shè)有 N = 4粒石子，則一開(kāi)始甲最多能取 3粒，用 （ 4， 3） 來(lái)表示初始狀態(tài)。 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) 甲取 1粒 甲取 2粒 甲取 3粒 乙取 1粒 乙取 2粒 乙取 1粒 乙取 2粒 乙取 1粒 甲取 1粒 甲取 2粒 甲取 1粒 甲取 1粒 乙取 1粒 （ 4, 3） （ 3, 2） （ 2, 2） （ 1, 1） （ 2, 2） （ 1, 1） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） 自頂而下構(gòu)造 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 （ 4, 3） （ 3, 2） （ 2, 2） （ 1, 1） （ 2, 2） （ 1, 1） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） 敗 敗 敗 敗 敗 敗 注：這里的勝敗指的均是先手勝敗。 1如果一個(gè)狀態(tài)沒(méi)有子狀態(tài)，是結(jié)局，則根據(jù)題目條件判定勝負(fù) 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 勝 勝 勝 勝 勝 勝 （ 4, 3） （ 3, 2） （ 2, 2） （ 1, 1） （ 2, 2） （ 1, 1） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） 敗 敗 敗 敗 敗 敗 注：這里的勝敗指的均是先手勝敗。 1如果一個(gè)狀態(tài)至少有一個(gè)子狀態(tài)是先手?jǐn)?，則該狀態(tài)是先手勝 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 勝 敗 勝 勝 勝 勝 勝 勝 （ 4, 3） （ 3, 2） （ 2, 2） （ 1, 1） （ 2, 2） （ 1, 1） （ 1, 1） （ 0,
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1