算法合集之構(gòu)造——解題的最短路徑法-閱讀頁
2024-10-31 20:32本頁面
【正文】 點。 構(gòu)造的分類標(biāo)準(zhǔn) 與 選擇的構(gòu)造方法 息息相關(guān) 。數(shù)學(xué)歸納法一直被人們津津樂道，因為有限的幾步，跨越了無限的空間。 歸納構(gòu)造利用了歸納的思想 ， 是構(gòu)造法的一個經(jīng)典的實現(xiàn)形式 。 在這里 ， 我們概括出這種方法一般的步驟如下： 構(gòu)造 i=1的情況 假設(shè) i=j已經(jīng)構(gòu)造出來 ， 構(gòu)造 i=j+1的情況 利用歸納法 ， 推廣到 i=n的情況 IOI’ 2021冬令營講稿 例四：賽程安排問題（ 1） 有 2m個選手 ， 每一天安排若干場比賽 ， 且每個選手每天僅可以參加一場比賽 ，試給出一種賽程的安排表 ， 使得在 2m1天內(nèi)任意兩個選手都至少比賽過一場 。 IOI’ 2021冬令營講稿 例四：賽程安排問題（ 2） 容易知道 ， 這個矩陣有以下幾個特點： 1) 第 i行第一列的數(shù)為 i， 2) 第 i行的數(shù)的并集等于 {1， 2， 3， …… ， 2m} 3) 第 j列的數(shù)的并集等于 {1， 2， 3， …… ， 2m} 4) 若第 i行第 j列的數(shù)字為 k， 那么第 k行第 j列的數(shù)字為 i。 Pm+1是一個 2m+1*2m+1的矩陣，啟發(fā)我們將它均分成四個 2m*2m的矩陣，實現(xiàn)從 Pm到 Pm+1的過渡。 IOI’ 2021冬令營講稿 例四：賽程安排問題（ 3） A B C D 設(shè) Pm已經(jīng)填好，將 Pm+1均分為四份 A、 B、 C、 D。 可以驗證，這樣構(gòu)造出來的矩陣仍然滿足要求 1）、 2）、 3）、4）。 Pm P m+2m Pm+2m Pm Pm+1= IOI’ 2021冬令營講稿 例四：賽程安排問題（ 4） 有 2n個選手參加比賽。每個選手每天至多同一個對手比賽。 分析：為了方便起見 ， 用 AB表示選手 A比選手 B強(qiáng) 。 這一步是整個問題的關(guān)鍵所在，也是問題的瓶頸！ IOI’ 2021冬令營講稿 例四：賽程安排問題（ 5） 問題轉(zhuǎn)化為： 已知 A1A2A3…… A2n， B1B2B3…… B2n， 在 n+1天之內(nèi)確定這 2n+1個人的順序 。 經(jīng)過許多次嘗試 ， 我們發(fā)現(xiàn)一般的歸納構(gòu)造在 “ 分 ?合 ” 這一步上都無法勝任 。 上述命題仍然可以采用歸納構(gòu)造來解決。 假設(shè)對于 n時已經(jīng)有了安排方法 ， 考慮 n+1的情況 。 安排第一天的比賽如下： 設(shè) Aj是編號最小的負(fù)于對手的選手 ， 即 A A …… Aj1都取勝 ， Aj、Aj+ …… Ak都負(fù)于對手 。 弱組： AjAj+1…… Ak， B2nj+2 B2nj+3…… B2n1 B2n…… Bl， 共 2n名 。 由歸納假設(shè)，兩組均只需 n天（并列進(jìn)行）就可以確定組內(nèi)的強(qiáng)弱，又由于強(qiáng)組全體排在弱組前，故整體名次也確定。 加強(qiáng)后的結(jié)論成立 ， 故之前的結(jié)論也成立 。由上述結(jié)論推出 ， A1A2A3…… A2n， B1B2B3…… B2n， 只需 n+1天就可以合并這兩個組 。 IOI’ 2021冬令營講稿 例四：小結(jié) 上面的兩個賽程安排問題都是運(yùn)用歸納構(gòu)造的典型。 加強(qiáng)命題是數(shù)學(xué)中一種常用的方法，在加強(qiáng)結(jié)論的同時，歸納假設(shè)的條件也增強(qiáng)了，為解題鋪平了道
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1