矩形周長(zhǎng)與面積的并

《矩形周長(zhǎng)與面積的并》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率——從IOI98試題PICTURE談起數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率——從IOI98試題PICTURE談起福建師大附中陳宏【關(guān)鍵字】數(shù)據(jù)結(jié)構(gòu)的選擇線性結(jié)構(gòu)樹形結(jié)構(gòu)【摘要】算法+數(shù)據(jù)結(jié)構(gòu)=程序。設(shè)計(jì)算法與選擇合適的數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)中相輔相成的兩方面，缺一不可。數(shù)據(jù)結(jié)構(gòu)的選擇一直是程序設(shè)計(jì)中的重點(diǎn)、難點(diǎn)，正確地應(yīng)用數(shù)據(jù)結(jié)構(gòu)，往往能帶來(lái)意想不到的效果。反之，如果忽視了數(shù)據(jù)結(jié)構(gòu)的重要性，對(duì)某些問(wèn)題有時(shí)就得不到滿意的解答。通過(guò)對(duì)IOI98試題Picture的深入討論，我們可以看到兩種不同的數(shù)據(jù)結(jié)構(gòu)在解題中的應(yīng)用，以及由此得到的不同的算法效率。本文以Picture問(wèn)題為例，探討數(shù)據(jù)結(jié)構(gòu)

2、的選擇對(duì)算法效率的影響。【正文】引言算法通常是決定程序效率的關(guān)鍵，但一切算法最終都要在相應(yīng)的數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)，許多算法的精髓就是在于選擇了合適的數(shù)據(jù)結(jié)構(gòu)作為基礎(chǔ)。在程序設(shè)計(jì)中，不但要注重算法設(shè)計(jì)，也要正確地選擇數(shù)據(jù)結(jié)構(gòu)，這樣往往能夠事半功倍。在算法時(shí)間與空間效率的兩方面，著重分析時(shí)間效率，即算法的時(shí)間復(fù)雜度，因?yàn)槲覀兛偸窍Ｍ绦蛟谳^短的時(shí)間內(nèi)給出我們所希望的輸出。如果在空間上過(guò)于“吝嗇”而使得時(shí)間上無(wú)法承受，對(duì)解題并無(wú)益處。本文對(duì)IOI98的試題Picture作一些分析，通過(guò)兩種不同數(shù)據(jù)結(jié)構(gòu)的選擇，將了解到數(shù)據(jù)結(jié)構(gòu)對(duì)算法本身及算法效率的影響。Picture問(wèn)題及算法設(shè)計(jì)一、Picture問(wèn)題Pi

3、cture問(wèn)題是IOI98的一道試題，描述如下：墻上貼著一些海報(bào)、照片等矩形，所有的邊都為垂直或水平。每個(gè)矩形可以被其它矩形部分或完全遮蓋，所有矩形合并成區(qū)域的邊界周長(zhǎng)稱為輪廓周長(zhǎng)。例如圖1的三個(gè)矩形輪廓周長(zhǎng)為30：IOI’99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選-35-數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率——從IOI98試題PICTURE談起圖1要求編寫程序計(jì)算輪廓周長(zhǎng)。數(shù)據(jù)量限制：0≤矩形數(shù)目<5000；坐標(biāo)數(shù)值為整數(shù)，范圍是[-10000，10000]。一、算法描述在算法的大體描述中，將不涉及到具體的數(shù)據(jù)結(jié)構(gòu)，便于數(shù)據(jù)結(jié)構(gòu)的進(jìn)一步選擇和比較分析。（一）、輪廓的定義在描述算法前，我們先明確一下“輪廓”的定義：1、輪廓

4、由有限條線段組成，線段是矩形邊或者矩形邊的一部分。2、組成矩形邊的線段不應(yīng)被任何矩形遮蓋。圖2與圖3分別是遮蓋的兩種情況。圖2圖3圖4（AB被遮蓋）（CD被遮蓋）（二）、元線段本題的一大特征是分析矩形的邊，而邊的端點(diǎn)（即矩形的頂點(diǎn)）坐標(biāo)為整數(shù)，且坐標(biāo)取值范圍已經(jīng)限定在[-10000，10000]之間。這樣，就可以把這個(gè)平面理解成為一個(gè)網(wǎng)格。由于給出的坐標(biāo)是整數(shù)，所以矩形邊一定在網(wǎng)格線上。在網(wǎng)格中，對(duì)于一條線段我們最關(guān)心其絕對(duì)坐標(biāo)。如圖4，我們認(rèn)為矩形邊AB由線段L1、L2、L3組成。像L1、L2、L3這樣連接相鄰網(wǎng)格頂點(diǎn)的基本線段，稱之為“元線段”，這樣就把矩形邊離散化了。顯然，有限的元線段覆

5、蓋了所有的網(wǎng)格線，且元線段是組成矩形邊乃至組成輪廓的基本單位。一條元線段要么完全屬于輪廓，要么完全不屬于輪廓。這種定義使我們對(duì)問(wèn)題的研究具體到每一條元線段，這樣的離散化處理有利于問(wèn)題的進(jìn)一步討論。（三）、超元線段IOI’99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選-35-數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率——從IOI98試題PICTURE談起元線段的引入，使問(wèn)題更加具體。但也應(yīng)當(dāng)看到，平面中共有20001*20000*2條元線段，研究的對(duì)象過(guò)多，而且計(jì)算量受到網(wǎng)格大小的影響，如果頂點(diǎn)坐標(biāo)范圍是[-1,000,000，1,000,000]，元線段數(shù)目將達(dá)到8*10^12，這是天文數(shù)字。因此有必要對(duì)“元線段”進(jìn)行優(yōu)化。受到元線

6、段的啟發(fā)，我們定義一種改進(jìn)后的元線段——“超元線段”，它將由對(duì)平面的“切割”得到。具體做法是，根據(jù)每個(gè)矩形縱向邊的橫坐標(biāo)縱向地對(duì)平面進(jìn)行2*N次切割、根據(jù)矩形橫向邊的縱坐標(biāo)橫向地對(duì)矩形進(jìn)行2*N次切割（N為矩形個(gè)數(shù)）。顯然，經(jīng)過(guò)切割后的平面被分成了(2*N+1)^2個(gè)區(qū)域，如圖5所示：圖5圖6其中像橫向邊AB、縱向邊CD這樣的線段就是“超元線段”。超元線段與元線段有著相似的性質(zhì)，也是組成輪廓的基本單位。所不同的是，超元線段的數(shù)目較少，一般為4*N條左右，且超元線段數(shù)目不受網(wǎng)格大小的影響?；诔€段的優(yōu)點(diǎn)，算法最終將研究超元線段。(一)、離散化及算法框架算法的研究對(duì)象是超元線段，但這并不等于逐

7、一枚舉，那樣耗時(shí)過(guò)大，而整體考慮又使得問(wèn)題無(wú)從下手。有一種考慮方法是折中的，即既不研究每一條超元線段，也不同時(shí)研究所有的超元線段，而是再進(jìn)一步優(yōu)化問(wèn)題的離散化，即將超元線段分組研究。如圖6所示，夾在兩條縱向分割邊的超元線段自然地分為一組，它們的共同點(diǎn)是長(zhǎng)度相同，并且端點(diǎn)的橫坐標(biāo)相同?？v向線段也可以進(jìn)行類似的離散化。這樣的離散化處理后，使得問(wèn)題規(guī)模降低，以此為基礎(chǔ)，算法的框架可以基本確定為：1、對(duì)平