一張一弛,解題之道

《一張一弛,解題之道》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、2006年全國(guó)信息學(xué)冬令營(yíng)講座一張一弛，解題之道——“約制、放寬”方法在解題中的應(yīng)用廣東省中山紀(jì)念中學(xué)陳啟峰第21頁(yè)共21頁(yè)2006年全國(guó)信息學(xué)冬令營(yíng)講座目錄一張一弛，解題之道1——“約制、放寬”方法在解題中的應(yīng)用1目錄2【摘要】3【關(guān)鍵字】3“約制、放寬”方法的定義4引言4例題分析4[例一]騎士4【問(wèn)題描述】4【問(wèn)題分析】5【數(shù)學(xué)模型】5【算法模型分析】5【確定總算法和研究對(duì)象】5【分析研究對(duì)象】6【“約制”方法確定新任務(wù)】6【尋找兩個(gè)向量的規(guī)律】6【“約制”方法解決新任務(wù)】8【回到研究對(duì)象】10【回到起點(diǎn)】11【小結(jié)】11[例二]友

2、好的動(dòng)物12【問(wèn)題描述】12【問(wèn)題分析】12【數(shù)學(xué)模型】12【原始算法的矛盾】13【數(shù)據(jù)范圍分析】13【數(shù)據(jù)結(jié)構(gòu)優(yōu)化時(shí)的矛盾】13【分析矛盾】14【“放寬”方法化解矛盾】14【小結(jié)】15[例三]消防站16【問(wèn)題描述】16【問(wèn)題分析】16【數(shù)學(xué)模型】16【算法模型分析】16【預(yù)處理】17【確定動(dòng)態(tài)規(guī)劃時(shí)的矛盾】17【總結(jié)分析】17第21頁(yè)共21頁(yè)2006年全國(guó)信息學(xué)冬令營(yíng)講座【“放寬”方法轉(zhuǎn)化限制】18【進(jìn)一步分析】18【“約制”方法增添限制】19【確定動(dòng)態(tài)規(guī)劃轉(zhuǎn)移方程】19【小結(jié)】20總結(jié)21【感謝】21【摘要】本文主要闡述了“約制、放

3、寬”方法在解題中的應(yīng)用。第一部分解釋了什么“約制、放寬”方法。第二部分論述了在解題中為什么需要“約制、放寬”方法。第三部分通過(guò)分析《騎士》、《友好的動(dòng)物》和《消防站》分別介紹了“約制”方法、“放寬”方法和兩者綜合應(yīng)用在解題中起的作用。最后作者結(jié)合自身經(jīng)驗(yàn)談?wù)勗诮忸}中如何靈活運(yùn)用“約制、放寬”方法?！娟P(guān)鍵字】“約制”方法“放寬”方法過(guò)于寬松過(guò)于繁雜過(guò)于獨(dú)立過(guò)于嚴(yán)格約制條件、限制放寬條件、限制第21頁(yè)共21頁(yè)2006年全國(guó)信息學(xué)冬令營(yíng)講座正文“約制、放寬”方法的定義“約制”方法——添增一些約束的條件、限制，并保證在這些條件和限制下依然能找到

4、解。“放寬”方法——減除、放寬一些條件、限制，并保證在這些條件和限制下依然能找到解。引言在分析問(wèn)題、設(shè)計(jì)算法的時(shí)候，我們常常會(huì)覺(jué)得條件、限制過(guò)于繁雜、嚴(yán)格或者過(guò)于寬松、獨(dú)立以致無(wú)法下手。這時(shí)，不妨嘗試“約制、放寬”方法?！凹s制”方法往往在我們迷茫時(shí)指出一條光明大道，“放寬”方法則常常在關(guān)系錯(cuò)綜復(fù)雜時(shí)破除阻擾和荊棘。巧妙地運(yùn)用這兩種方法能使我們?cè)诮忸}中排除萬(wàn)難，直入臟腑。例題分析下面，本人從“約制”方法，“放寬”方法和兩者的綜合應(yīng)用三個(gè)方面精心挑選了三個(gè)題目并作詳細(xì)分析，希望這能起到拋磚引玉的作用。[例一]騎士選自POI2005的STAG

5、E1的《KNIGHTS》【問(wèn)題描述】有一騎士在一個(gè)無(wú)限大的棋盤上移動(dòng)。它每次的移動(dòng)都用一個(gè)整數(shù)對(duì)來(lái)描述——整數(shù)對(duì)（a,b）表示騎士能從位置（x,y）跳到位置(x+a,y+b)或者(x-a,y-b)。每個(gè)騎士有一系列的已確定的整數(shù)對(duì)，描述這騎士能進(jìn)行哪些移動(dòng)。我們保證每個(gè)騎士能到達(dá)的位置不在同一直線上。當(dāng)兩個(gè)騎士以位置（0，0）為始點(diǎn)能到達(dá)的所有位置完全相同時(shí)（可能做很多次移動(dòng)），我們就說(shuō)這兩個(gè)騎士是等價(jià)的?？梢宰C明對(duì)于每一個(gè)騎士，都存在一個(gè)只有兩個(gè)整數(shù)對(duì)的等價(jià)騎士。第21頁(yè)共21頁(yè)2006年全國(guó)信息學(xué)冬令營(yíng)講座任務(wù)：讀入一個(gè)騎士的所有整

6、數(shù)對(duì)，找出一個(gè)只有兩個(gè)整數(shù)對(duì)的等價(jià)騎士?！締?wèn)題分析】【數(shù)學(xué)模型】令輸入的整數(shù)對(duì)分別表示為向量,向量……向量，找出兩個(gè)整數(shù)對(duì)——向量和與這n個(gè)向量等價(jià),也就是對(duì)于任意的整數(shù)序列，都存在兩個(gè)整數(shù)使得并且對(duì)于任意兩個(gè)整數(shù)，都存在一個(gè)整數(shù)序列，使得【算法模型分析】看到這個(gè)題目，最容易想到的算法是枚舉這兩個(gè)向量和用寬度優(yōu)先搜索判斷是否等價(jià)。但是要尋找的這兩個(gè)向量的范圍是無(wú)限大的，并且棋盤也是無(wú)限大的。因此這個(gè)算法宛如大海撈針一般，極難在有限的時(shí)間內(nèi)找到解。然后嘗試貪心、動(dòng)態(tài)規(guī)劃、圖論等硬做的算法，但這些算法都在預(yù)料之中以失敗告終。最后，看來(lái)只有必

7、經(jīng)之路——數(shù)學(xué)方法才能可以解決這個(gè)問(wèn)題?！敬_定總算法和研究對(duì)象】用數(shù)學(xué)方法解決等價(jià)轉(zhuǎn)化等題目的方法還是不勝枚舉的。例如有歸納法，有總體法，有解方程法，有數(shù)形結(jié)合。對(duì)于這個(gè)題目，我們應(yīng)選取什么數(shù)學(xué)方法好呢？注意到，如果任意的三個(gè)向量都可以與某兩個(gè)向量等價(jià)，那么便可以從n(n>2)個(gè)向量中任選三個(gè)向量出來(lái)，用與它們等價(jià)的兩個(gè)向量代替它們，從而變成n-1個(gè)向量。不斷重復(fù)上述的過(guò)程，直到只剩下兩個(gè)向量為止，這時(shí)剩下的兩個(gè)向量便是一個(gè)可行解。而由問(wèn)題描述可以知道：對(duì)于任意三個(gè)向量都存在兩個(gè)向量與它們等價(jià)。這便意味這種方法是可行的。于是，就可以確定

8、下總算法——不斷化三為二第21頁(yè)共21頁(yè)2006年全國(guó)信息學(xué)冬令營(yíng)講座，同時(shí)也產(chǎn)生了我們的研究對(duì)象——如何把三個(gè)向量等價(jià)替換為兩個(gè)向量？【分析研究對(duì)象】因?yàn)闈M足條件的解（等價(jià)的兩個(gè)向量）是無(wú)限多個(gè)的，解的范