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