算法合集之構(gòu)造——解題的最短路徑法-資料下載頁
2024-10-16 20:32本頁面
【正文】 。 分析：為了方便起見 ， 用 AB表示選手 A比選手 B強(qiáng) 。 首先嘗試一般的歸納構(gòu)造： 設(shè)結(jié)論對于 n成立 ， 考慮 n+1時 ， 共 2n+1名選手分為兩個組 A、 B， 每組 2n個人 ， 由歸納假設(shè) ， 只需 n*(n+1)/2天即可確定兩個組各自的順序 ， 假設(shè)已經(jīng)排成： A1A2A3…… A2 n， B1B2B3…… B2n， 那么現(xiàn)在要在(n+1)*(n+2)/2n*(n+1)/2=n+1天內(nèi)完成兩個組的合并 。 這一步是整個問題的關(guān)鍵所在，也是問題的瓶頸！ IOI’ 2021冬令營講稿 例四：賽程安排問題（ 5） 問題轉(zhuǎn)化為： 已知 A1A2A3…… A2n， B1B2B3…… B2n， 在 n+1天之內(nèi)確定這 2n+1個人的順序 。 這一步仍然需要采用歸納法來解決 。 經(jīng)過許多次嘗試 ， 我們發(fā)現(xiàn)一般的歸納構(gòu)造在 “ 分 ?合 ” 這一步上都無法勝任 。 想到數(shù)學(xué)歸納法的一個常用技巧 ——加強(qiáng)命題 ！ 命題加強(qiáng)為： k+l=2n（ k、 l、 n均為正整數(shù)），已知 A1A2A3…… Ak， B1B2B3…… Bl，決定這 2n名選手強(qiáng)弱只需 n天。 上述命題仍然可以采用歸納構(gòu)造來解決。 IOI’ 2021冬令營講稿 例四：賽程安排問題（ 6） 當(dāng) n=1時 ， k=l=1， 安排 A1?B1， 結(jié)論顯然成立 。 假設(shè)對于 n時已經(jīng)有了安排方法 ， 考慮 n+1的情況 。 不妨設(shè) k≤l ， k+l=2n+1。 安排第一天的比賽如下： 設(shè) Aj是編號最小的負(fù)于對手的選手 ， 即 A A …… Aj1都取勝 ， Aj、Aj+ …… Ak都負(fù)于對手 。 可以推出結(jié)論： A1A2…… Aj1B2nj+2 B2nj+3…… B2n1 B2n…… Bl B1B2…… B2nj+1AjAj+1…… Ak IOI’ 2021冬令營講稿 例四：賽程安排問題（ 7） 把這 2n名選手分為兩組： 強(qiáng)組： A1A2…… Aj1， B1B2…… B2nj+1 共 2n名 。 弱組： AjAj+1…… Ak， B2nj+2 B2nj+3…… B2n1 B2n…… Bl， 共 2n名 。 容易看出 ， 強(qiáng)組中的任一人均比弱組中的任一人強(qiáng) 。 由歸納假設(shè)，兩組均只需 n天（并列進(jìn)行）就可以確定組內(nèi)的強(qiáng)弱，又由于強(qiáng)組全體排在弱組前，故整體名次也確定。加上初始時用的一天時間，總共 n+1天，這 2n+1名選手名次確定，結(jié)論對于 n+1時也成立。 加強(qiáng)后的結(jié)論成立 ， 故之前的結(jié)論也成立 。 回到原來的問題 ， 就很容易解決了 。由上述結(jié)論推出 ， A1A2A3…… A2n， B1B2B3…… B2n， 只需 n+1天就可以合并這兩個組 。 總共需要的天數(shù)為 n*(n+1)/2+(n+1)=(n+1)*(n+2)/2， 即 n+1時也可以完成賽程安排 。 IOI’ 2021冬令營講稿 例四：小結(jié) 上面的兩個賽程安排問題都是運用歸納構(gòu)造的典型。前者很容易就能實現(xiàn)從 m1到 m的過渡，但后者則需要加強(qiáng)命題，并兩次使用歸納構(gòu)造。 加強(qiáng)命題是數(shù)學(xué)中一種常用的方法，在加強(qiáng)結(jié)論的同時，歸納假設(shè)的條件也增強(qiáng)了，為解題鋪平了道路。 構(gòu)造中綜合運用數(shù)學(xué)的各種方法 Back
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1