一張一弛,解題之道

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

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

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

3、21【摘要】本文主要闡述了“約制、放寬”方法在解題中的應用。第一部分解釋了什么“約制、放寬”方法。第二部分論述了在解題中為什么需要“約制、放寬”方法。第三部分通過分析《騎士》、《友好的動物》和《消防站》分別介紹了“約制”方法、“放寬”方法和兩者綜合應用在解題中起的作用。最后作者結(jié)合自身經(jīng)驗談談在解題中如何靈活運用“約制、放寬”方法?！娟P(guān)鍵字】“約制”方法“放寬”方法過于寬松過于繁雜過于獨立過于嚴格約制條件、限制放寬條件、限制第21頁共21頁2006年全國信息學冬令營講座正文“約制、放寬”方法的定義“約制”方法——添增一

4、些約束的條件、限制，并保證在這些條件和限制下依然能找到解?！胺艑挕狈椒ā獪p除、放寬一些條件、限制，并保證在這些條件和限制下依然能找到解。引言在分析問題、設(shè)計算法的時候，我們常常會覺得條件、限制過于繁雜、嚴格或者過于寬松、獨立以致無法下手。這時，不妨嘗試“約制、放寬”方法?！凹s制”方法往往在我們迷茫時指出一條光明大道，“放寬”方法則常常在關(guān)系錯綜復雜時破除阻擾和荊棘。巧妙地運用這兩種方法能使我們在解題中排除萬難，直入臟腑。例題分析下面，本人從“約制”方法，“放寬”方法和兩者的綜合應用三個方面精心挑選了三個題目并作詳細分

5、析，希望這能起到拋磚引玉的作用。[例一]騎士選自POI2005的STAGE1的《KNIGHTS》【問題描述】有一騎士在一個無限大的棋盤上移動。它每次的移動都用一個整數(shù)對來描述——整數(shù)對（a,b）表示騎士能從位置（x,y）跳到位置(x+a,y+b)或者(x-a,y-b)。每個騎士有一系列的已確定的整數(shù)對，描述這騎士能進行哪些移動。我們保證每個騎士能到達的位置不在同一直線上。當兩個騎士以位置（0，0）為始點能到達的所有位置完全相同時（可能做很多次移動），我們就說這兩個騎士是等價的?？梢宰C明對于每一個騎士，都存在一個只有兩個

6、整數(shù)對的等價騎士。第21頁共21頁2006年全國信息學冬令營講座任務：讀入一個騎士的所有整數(shù)對，找出一個只有兩個整數(shù)對的等價騎士?！締栴}分析】【數(shù)學模型】令輸入的整數(shù)對分別表示為向量,向量……向量，找出兩個整數(shù)對——向量和與這n個向量等價,也就是對于任意的整數(shù)序列，都存在兩個整數(shù)使得并且對于任意兩個整數(shù)，都存在一個整數(shù)序列，使得【算法模型分析】看到這個題目，最容易想到的算法是枚舉這兩個向量和用寬度優(yōu)先搜索判斷是否等價。但是要尋找的這兩個向量的范圍是無限大的，并且棋盤也是無限大的。因此這個算法宛如大海撈針一般，極難在有限

7、的時間內(nèi)找到解。然后嘗試貪心、動態(tài)規(guī)劃、圖論等硬做的算法，但這些算法都在預料之中以失敗告終。最后，看來只有必經(jīng)之路——數(shù)學方法才能可以解決這個問題。【確定總算法和研究對象】用數(shù)學方法解決等價轉(zhuǎn)化等題目的方法還是不勝枚舉的。例如有歸納法，有總體法，有解方程法，有數(shù)形結(jié)合。對于這個題目，我們應選取什么數(shù)學方法好呢？注意到，如果任意的三個向量都可以與某兩個向量等價，那么便可以從n(n>2)個向量中任選三個向量出來，用與它們等價的兩個向量代替它們，從而變成n-1個向量。不斷重復上述的過程，直到只剩下兩個向量為止，這時剩下的兩個

8、向量便是一個可行解。而由問題描述可以知道：對于任意三個向量都存在兩個向量與它們等價。這便意味這種方法是可行的。于是，就可以確定下總算法——不斷化三為二第21頁共21頁2006年全國信息學冬令營講座，同時也產(chǎn)生了我們的研究對象——如何把三個向量等價替換為兩個向量？【分析研究對象】因為滿足條件的解（等價的兩個向量）是無限多個的，解的范