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