算法合集之構造——解題的最短路徑法(編輯修改稿)
2024-11-12 20:32 本頁面
【文章內(nèi)容簡介】 ? nnniii bbbaaalIOI’ 2021冬令營講稿 例二：區(qū)間染色問題（ 4） 只需證：若 l l22/3(t1t0),必然有 l3≥2/3(t1 t0) ,1121 ??????? niinii ballbn≥t1,a 1≤t0 l3≥2(t1 t0)(l1+l2)2(t1t0)4/3(t1t0)=2/3(t1t0) ???????? nininii abbal1113 )(2變形得： 這就證明了： l l l3中間必然有一個不小于 2/3(t1t0)，上述構造成立。 IOI’ 2021冬令營講稿 例二：小結 本題采用的方法特別之處在于：同時構造了多組情形，證明必然有一組符合要求。 對于某些題目，很難直接給出一種 “ 必行 ” 的構造方法，這時就需要我們?yōu)樗?“ 量身定做 ” 多個構造方法，相輔相成。某種構造成立 —— 導出結論的成立；不成立 —— 卻為其他的構造法創(chuàng)造了條件。 構造 D成立 構造 A不成立 構造 B不成立 構造 C不成立 Back IOI’ 2021冬令營講稿 分類構造 當所研究的問題包含有多種可能情況 ， 并難以統(tǒng)一處理時 ， 就需按所有可能出現(xiàn)的各種情況分類進行討論 ， 得出各種情況的相應結論 ， 最后綜合總結出問題的正確解答 ， 這種方法稱為分類法 。 分類構造是分類的思想與構造法相結合的產(chǎn)物 ， 簡單說來 ， 就是在分類的基礎上進行構造 。 分類構造的步驟如下： 對問題進行分類 針對每一類進行構造 合成整個問題的解 分析問題性質 分類的各種思想在這里同樣可以得到很好的應用，如按照剩余系分類（奇偶分類）、按照數(shù)據(jù)大小分類、按照題目中所涉及到的定義概念分類、按照參數(shù)的變化等等。 IOI’ 2021冬令營講稿 例三：棋盤遍歷問題（ 1） 有一個 n*n的正方形 ， 某人從 (x， y)出發(fā) ， 要求出一條符合要求的路線 ， 經(jīng)過每個格子一次且僅一次 。 ?路線盡可能簡單，轉彎盡可能少 —— 迂回狀折線 左圖是 n=4， x=2，y=2的情況 ?特點：在邊界處的方向與 n、 x、 y的奇偶性有關 IOI’ 2021冬令營講稿 例三：棋盤遍歷問題（ 2） ?n是偶數(shù)，不妨設 x、 y均為奇數(shù)，否則適當?shù)匦D、翻轉棋盤。 一旦 n、 x、 y的奇偶性確定，路線在邊界處的情況就可以唯一確定 IOI’ 2021冬令營講稿 例三：棋盤遍歷問題（ 3） ? n為奇數(shù) i. x、 y奇偶性相同，不妨設 x、 y均為偶數(shù)，否則適當?shù)匦D、翻轉棋盤 IOI’ 2021冬令營講稿 例三：棋盤遍歷問題（ 4） ? n為奇數(shù) ii. x、 y奇偶性不同，此時問題無解 先對棋盤進行黑白二染色，如左圖 n為奇數(shù) ? 遍歷棋盤要走奇數(shù)步 ?終止點是黑格 x為奇數(shù) 、 y為偶數(shù) ?出發(fā)點是白格 ?黑格數(shù) =白格數(shù) n為奇數(shù) ?黑格數(shù) =白格數(shù) +1 ?矛盾 IOI’ 2021冬令營講稿 例三：小結 本題的分類并不是憑空得來的，而是基于 “ 迂回性折線 ” 的特點。這種路線到了邊界處會出現(xiàn)不同的情形，需要我們區(qū)別對待。 構造
教學課件相關推薦
鄂ICP備17016276號-1