算法合集之構(gòu)造——解題的最短路徑法(存儲版)
【正文】 在競賽中 ， 采用得比較普遍的仍然是一般歸納法 +構(gòu)造法的形式 。 令 A=D=Pm， B=C=Pm+2m（表示把 Pm中的元素都加上 2m后形成的新矩陣）。 首先嘗試一般的歸納構(gòu)造： 設結(jié)論對于 n成立 ， 考慮 n+1時 ， 共 2n+1名選手分為兩個組 A、 B， 每組 2n個人 ， 由歸納假設 ， 只需 n*(n+1)/2天即可確定兩個組各自的順序 ， 假設已經(jīng)排成： A1A2A3…… A2 n， B1B2B3…… B2n， 那么現(xiàn)在要在(n+1)*(n+2)/2n*(n+1)/2=n+1天內(nèi)完成兩個組的合并 。 不妨設 k≤l ， k+l=2n+1。 回到原來的問題 ， 就很容易解決了 。 構(gòu)造中綜合運用數(shù)學的各種方法 Back 。加上初始時用的一天時間，總共 n+1天，這 2n+1名選手名次確定，結(jié)論對于 n+1時也成立。 IOI’ 2021冬令營講稿 例四：賽程安排問題（ 6） 當 n=1時 ， k=l=1， 安排 A1?B1， 結(jié)論顯然成立 。試給出一種賽程的安排表，使得在 n*(n+1)/2天內(nèi)確定所有選手的強弱。為了適應規(guī)模的增大，對于 Pm中的元素進行適當?shù)募訙p運算。它被頻繁采用并衍生出多種形式：如第二歸納法、多起點歸納法、曲線歸納法等等。 分類構(gòu)造的步驟如下： 對問題進行分類 針對每一類進行構(gòu)造 合成整個問題的解 分析問題性質(zhì) 分類的各種思想在這里同樣可以得到很好的應用，如按照剩余系分類（奇偶分類）、按照數(shù)據(jù)大小分類、按照題目中所涉及到的定義概念分類、按照參數(shù)的變化等等。 ??? ?niiii abl為奇數(shù)112) 取 [a2， b2]、 [a4， b4]、 [a6， b6]…… 這些編號為偶數(shù)的區(qū)間。這僅僅是一個猜想，需要經(jīng)過實踐以及證明。 ? 在熟悉的事物中尋找，在特殊的事物中尋找，接合目標，不斷地調(diào)整甚至改變方案，直至實現(xiàn)構(gòu)造 IOI’ 2021冬令營講稿 例一：三臂起重機（ 1） 給出了三個數(shù) p、 q、 n， 要構(gòu)造若干個三元組 ， 符合以下四個要求： （ 1） 三元組必須具備形式 （ i， i+p， i+p+q） （ i， i+q，i+p+q） 之一 。 ? 實際應用中，首先對于目標對象進行觀察，發(fā)現(xiàn)一般性的規(guī)律，加以概括總結(jié)后運用至構(gòu)造中。 ?取上面 s個三元組中沒有出現(xiàn)過的最小自然數(shù) r +p沒有出現(xiàn)過 ? (xs+1,ys+1,zs+1)=(r,r+p,r+p+q) +p出現(xiàn)過 ? (xs+1,ys+1,zs+1)=(r,r+q,r+p+q) IOI’ 2021冬令營講稿 例一：三臂起重機（ 3） 這個方法馬上被下面的例子推翻： p=3,q=2 (1,4,6) (2,5,7) (3,?,8) ?處無論填 5還是6均已出現(xiàn)過 但是如果換一種填法： p=2,q=3 (1,3,6) (2,4,7) (5,8,10) (9,11,14) …… 交換一下 p、 q的位置，再應用上面的填法 啟發(fā)我們，應用上述填法的條件是： p≤q ，即當 pq時，先交換 p、 q的位置。 1 2 3 如：對下面的三個區(qū)間進行染色，紅色部分為僅被一個染色區(qū)間覆蓋的區(qū)域 IOI’ 2021冬令營講稿 例二：區(qū)間染色問題（ 2）
教學課件相關推薦
鄂ICP備17016276號-1