算法合集之構(gòu)造——解題的最短路徑法(參考版)
2024-10-19 20:32本頁面
【正文】 構(gòu)造中綜合運(yùn)用數(shù)學(xué)的各種方法 Back 。前者很容易就能實(shí)現(xiàn)從 m1到 m的過渡，但后者則需要加強(qiáng)命題，并兩次使用歸納構(gòu)造。 總共需要的天數(shù)為 n*(n+1)/2+(n+1)=(n+1)*(n+2)/2， 即 n+1時(shí)也可以完成賽程安排 。 回到原來的問題 ， 就很容易解決了 。加上初始時(shí)用的一天時(shí)間，總共 n+1天，這 2n+1名選手名次確定，結(jié)論對(duì)于 n+1時(shí)也成立。 容易看出 ， 強(qiáng)組中的任一人均比弱組中的任一人強(qiáng) 。 可以推出結(jié)論： A1A2…… Aj1B2nj+2 B2nj+3…… B2n1 B2n…… Bl B1B2…… B2nj+1AjAj+1…… Ak IOI’ 2021冬令營(yíng)講稿 例四：賽程安排問題（ 7） 把這 2n名選手分為兩組： 強(qiáng)組： A1A2…… Aj1， B1B2…… B2nj+1 共 2n名 。 不妨設(shè) k≤l ， k+l=2n+1。 IOI’ 2021冬令營(yíng)講稿 例四：賽程安排問題（ 6） 當(dāng) n=1時(shí) ， k=l=1， 安排 A1?B1， 結(jié)論顯然成立 。 想到數(shù)學(xué)歸納法的一個(gè)常用技巧 ——加強(qiáng)命題 ！ 命題加強(qiáng)為： k+l=2n（ k、 l、 n均為正整數(shù)），已知 A1A2A3…… Ak， B1B2B3…… Bl，決定這 2n名選手強(qiáng)弱只需 n天。 這一步仍然需要采用歸納法來解決 。 首先嘗試一般的歸納構(gòu)造： 設(shè)結(jié)論對(duì)于 n成立 ， 考慮 n+1時(shí) ， 共 2n+1名選手分為兩個(gè)組 A、 B， 每組 2n個(gè)人 ， 由歸納假設(shè) ， 只需 n*(n+1)/2天即可確定兩個(gè)組各自的順序 ， 假設(shè)已經(jīng)排成： A1A2A3…… A2 n， B1B2B3…… B2n， 那么現(xiàn)在要在(n+1)*(n+2)/2n*(n+1)/2=n+1天內(nèi)完成兩個(gè)組的合并 。試給出一種賽程的安排表，使得在 n*(n+1)/2天內(nèi)確定所有選手的強(qiáng)弱。已知兩個(gè)選手比賽時(shí)總是強(qiáng)的一方勝，且不會(huì)出現(xiàn)某兩個(gè)選手一樣強(qiáng)的情況。根據(jù)這張表可以給出相應(yīng)的賽程安排。 令 A=D=Pm， B=C=Pm+2m（表示把 Pm中的元素都加上 2m后形成的新矩陣）。為了適應(yīng)規(guī)模的增大，對(duì)于 Pm中的元素進(jìn)行適當(dāng)?shù)募訙p運(yùn)算。 采用歸納構(gòu)造的基本思想是：首先構(gòu)造出 Pm，在 Pm的基礎(chǔ)上構(gòu)造出 Pm+1。 第一天 第二天 …… 第 2m1天 第 2m天 選手 1 選手 2 …… 選手 2m1 選手 2m 分析：將賽程表設(shè)計(jì)成如下 2m*2m的矩陣 (除去第一行），記為 Pm。 在競(jìng)賽中 ， 采用得比較普遍的仍然是一般歸納法 +構(gòu)造法的形式 。它被頻繁采用并衍生出多種形式：如第二歸納法、多起點(diǎn)歸納法、曲線歸納法等等。 Back IOI’ 2021冬令營(yíng)講稿 歸納構(gòu)造 這里所說的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1