淺談數(shù)形結(jié)合思想在信息學(xué)競賽中的應(yīng)用

1、淺談數(shù)形結(jié)合思想在信息學(xué)競賽中的應(yīng)用安徽 周源目錄目錄1摘要2關(guān)鍵字2引子3以形助數(shù)3例一Raney引理的證明3題意簡述3分析3目標圖形化3小結(jié)4例二最大平均值問題(USACO 2003 March Open)4題意簡述4分析5目標圖形化5構(gòu)造下凸折線5維護下凸折線6最后的優(yōu)化：利用圖形的單調(diào)性7小結(jié)7以數(shù)助形7例三畫室(POI oi V Stage I)8題意簡述8分析8目標數(shù)值化9動態(tài)規(guī)劃解題9小結(jié)10總結(jié)10附錄11關(guān)于2003年上海市選拔賽題Sequence11題意簡述11分析11論文附件12參考文獻12摘要數(shù)與形是數(shù)學(xué)中兩個最古老而又最基本的對象，數(shù)形結(jié)合又是一種重要的數(shù)學(xué)思想。本文

2、主要以當今信息學(xué)奧賽中幾道試題為例，從以形助數(shù)和以數(shù)助形兩個側(cè)重點討論了數(shù)形結(jié)合思想在信息學(xué)競賽解題中廣闊的應(yīng)用前景。最后文章分析指出數(shù)形結(jié)合思想的兩個重要特性并由此提出“數(shù)形結(jié)合”重在有機的結(jié)合，希望對同學(xué)們在實際比賽中靈活的運用數(shù)形結(jié)合思想有一些幫助。關(guān)鍵字信息學(xué)競賽 數(shù)學(xué)思想 數(shù)形結(jié)合思想以數(shù)助形 以形助數(shù)辯證矛盾 多元性 個體差異性思維、編程、時間、空間復(fù)雜度引子數(shù)與形是數(shù)學(xué)中兩個最古老而又最基本的對象，數(shù)形結(jié)合又是一種重要的數(shù)學(xué)思想。在當今信息學(xué)競賽中，某些紛繁復(fù)雜的試題背后，往往蘊含著豐富的幾何背景，而計算幾何類問題卻又需要借助計算機強大的實數(shù)運算能力。正如華羅庚先生所說的“數(shù)形結(jié)

3、合千般好”，在算法和程序設(shè)計中，巧妙地運用數(shù)形結(jié)合思想，可以順利的破解問題，化難為易，找到問題的解題思路。數(shù)形結(jié)合思想常包括以形助數(shù)、以數(shù)助形兩個方面。以形助數(shù)正如前文所述，一些試題中繁雜的代數(shù)關(guān)系身后往往隱藏著豐富的幾何背景，而借助背景圖形的性質(zhì)，可以使那些原本復(fù)雜的數(shù)量關(guān)系和抽象的概念，顯得直觀，從而找到設(shè)計算法的捷徑。例一Raney引理的證明題意簡述設(shè)整數(shù)序列A = Ai, i=1, 2, , N，且部分和Sk=A1+Ak，序列中所有的數(shù)字的和SN=1。證明：在A的N個循環(huán)表示 先設(shè)一個序列是環(huán)狀的，則從其任意一個字符處斷開以后形成的非環(huán)序列即為該序列的一個循環(huán)表示。中，有且僅有一個序列

4、B，滿足B的任意部分和Si均大于零。分析先來看一個例子，若有序列A = <1, 4, -5, 3, -2, 0>，其6個循環(huán)表示為1. <1, 4, -5, 3, -2, 0>2. <4, -5, 3, -2, 0, 1>3. <-5, 3, -2, 0, 1, 4>4. <3, -2, 0, 1, 4, -5>5. <-2, 0, 1, 4, -5, 3>6. <0, 1, 4, -5, 3, -2>其中只有第4個序列，部分和為3, 1, 1, 2, 6, 1，滿足成為序列B的條件。若要用一般的代數(shù)或是組合方

5、法來證明這個有趣的結(jié)論，似乎無從下手，但若要想到了用“形”來幫忙，問題就簡單多了。目標圖形化周期性的推廣A序列，得到一個無窮序列，便于觀察其循環(huán)表示，得到：<A1, A2, , AN, A1, A2, , AN, >同時計算這個序列的部分和Si，因為這個序列是周期性的，因此對于所有的k>0，均有Sk+N=Sk+1。如果做出這個函數(shù)的圖像，則可以說函數(shù)有一個“平均斜率”為：每沿橫軸正方向走N個單位，函數(shù)值就增加1。于是如下圖所示，可以用兩條斜率為的直線“夾住”函數(shù)包含的所有點：圖 1 無窮序列的部分和函數(shù)圖像圖示中N=6，且使用了上文舉的例子。注意較低的那條直線，在每連續(xù)的N個

6、單位長度中，它與函數(shù)圖像有且僅有一個交點，這是因為斜率是的直線在每N個單位長度中最多到達一次整數(shù)點。這個交點是在這以后的N個點中的最低值，因此由此處的后一個位置導(dǎo)出的循環(huán)表示的所有部分和均為正數(shù)。而同時每連續(xù)N個單位長度僅有一個交點也證明了解的唯一性。小結(jié)一個簡單的幾何論證就證明了著名的Raney引理，其簡練是其他方法不能企及的。Raney引理有很廣泛的應(yīng)用，Catalan數(shù)以及擴展Catalan數(shù)的組合公式就可以用該引理輕松解決。比如今年上海市選拔賽第二天比賽中的序列(Sequence)以及OIBH練習(xí)賽中的項鏈，使用Raney引理都是最簡單的方法之一。 用Raney引理解答Sequence

7、的過程，詳見附錄。用幾何圖形輔助思考，不只停留在組合計數(shù)這一類中，更滲透在算法設(shè)計和優(yōu)化的每一個分支中，近年來流行的“斜率優(yōu)化”法是另一個很好的例子。例二最大平均值問題(USACO 2003 March Open)題意簡述讀入一列正數(shù)，a1, a2, , aN，以及一個數(shù)F。定義，ij。求Maxave(a, b), 1a, bN，且ab-F+1，即求一段長度大于等于F且平均值最大的子串。范圍：FN105。分析簡單的枚舉算法可以這樣描述：每次枚舉一對滿足條件的(a, b)，即ab-F+1，檢查ave(a, b)，并更新當前最大值。然而這題中N很大，N2的枚舉算法顯然不能使用，但是能不能優(yōu)化一下這

8、個效率不高的算法呢？答案是肯定的。目標圖形化首先一定會設(shè)序列ai的部分和：Si=a1+a2+ai，特別的定義S0=0。這樣可以很簡潔的表示出目標函數(shù)！如果將S函數(shù)繪在平面直角坐標系內(nèi)，這就是過點Sj和點Si-1直線的斜率！于是問題轉(zhuǎn)化為：平面上已知N+1個點，Pi(i, Si)，0iN，求橫向距離大于等于F的任意兩點連線的最大斜率。構(gòu)造下凸折線有序化一下，規(guī)定對i<j，只檢查Pj向Pi的連線，對Pi不檢查與Pj的連線。也就是說對任意一點，僅檢查該點與在其前方的點的斜率。于是我們定義點Pi的檢查集合為Gi = Pj, 0ji-F特別的，當i<F時，Gi為空集。其明確的物理意義為：在平

9、方級算法中，若要檢查ave(a, b)，那么一定有PaGb；因此平方級的算法也可以這樣描述，首先依次枚舉Pb點，再枚舉PaGb，同時檢查k(PaPb)。若將Pi和Gi同時列出，則不妨稱Pi為檢查點，Gi中的元素都是Pi的被檢查點。當我們考察一個點Pt時，樸素的平方級算法依次選取Gt中的每一個被檢查點p，考察直線pPt的斜率。但仔細觀察，若集合內(nèi)存在三個點Pi, Pj, Pk，且i<j<k，三個點形成如下圖所示的的關(guān)系，即Pj點在直線PiPk的上凸部分：k(Pi, Pj)>k(Pj, Pk)，就很容易可以證明Pj點是多余的。圖 2若k(Pt, Pj) > k(Pt, Pi

10、)，那么可以看出，Pt點一定要在直線PiPj的上方，即陰影所示的1號區(qū)域。同理若k(Pt, Pj) > k(Pt, Pk)，那么Pt點一定要在直線PjPk的下方，即陰影所示的2號區(qū)域。綜合上述兩種情況，若PtPj的斜率同時大于PtPi和PtPk的，Pt點一定要落在兩陰影的重疊部分，但這部分顯然不滿足開始時t>j的假設(shè)。于是，Pt落在任何一個合法的位置時，PtPj的斜率要么小于PtPi，要么小于PtPk，即不可能成為最大值，因此Pj點多余，完全可以從檢查集合中刪去。這個結(jié)論告訴我們，任何一個點Pt的檢查集合中，不可能存在一個對最優(yōu)結(jié)果有貢獻的上凸點，因此我們可以刪去每一個上凸點，剩下

11、的則是一個下凸折線。最后需要在這個下凸折線上找一點與Pt點構(gòu)成的直線斜率最大顯然這條直線是在與折線相切時斜率最大，如圖所示。圖 3維護下凸折線這一小節(jié)中，我們的目標是：用盡可能少的時間得到每一個檢查點的下凸折線。算法首先從PF開始執(zhí)行：它是檢查集合非空的最左邊的一個點，集合內(nèi)僅有一個元素P0，而這顯然滿足下凸折線的要求，接著向右不停的檢查新的點：PF+1, PF+2, , PN。檢查的過程中，維護這個下凸折線：每檢查一個新的點Pt，就可以向折線最右端加入一個新的點Pt-F，同時新點的加入可能會導(dǎo)致折線右端的一些點變成上凸點，我們用一個類似于構(gòu)造凸包的過程依次刪去這些上凸點，從而保證折線的下凸性

12、。由于每個點僅被加入和刪除一次，所以每次維護下凸折線的平攤復(fù)雜度為O(1)，即我們用O(N)的時間得到了每個檢查集合的下凸折線。最后的優(yōu)化：利用圖形的單調(diào)性最后一個問題就是如何求過Pt點，且與折線相切的直線了。一種直接的方法就是二分，每次查找的復(fù)雜度是O(log2N)。但是從圖形的性質(zhì)上很容易得到另一種更簡便更迅速的方法：由于折線上過每一個點切線的斜率都是一定的 由于折線沒有連續(xù)性，因此更準確的應(yīng)該說，過每一個點切線斜率的范圍都一定的。，而且根據(jù)下凸函數(shù)斜率的單調(diào)性，如果在檢查點Pt時找到了折線上的已知一個切點A，那么A以前的所有點都可以刪除了：過這些點的切線斜率一定小于已知最優(yōu)解，不會做出更

13、大的貢獻了。于是另外保留一個指針不回溯的向后移動以尋找切線斜率即可，平攤復(fù)雜度為為O(1)。至此，此題算法時空復(fù)雜度均為O(N)，得到了圓滿的解決。小結(jié)回顧本題的解題過程，一開始就確立了以平面幾何為思考工具的正確路線，很快就發(fā)現(xiàn)了檢查集合中對最優(yōu)解有貢獻的點構(gòu)成一個下凸函數(shù)這個重要結(jié)論，之后借助計算幾何中求凸包的方法維護一個下凸折線，最后還利用下凸函數(shù)斜率的單調(diào)性發(fā)現(xiàn)了找切線簡單方法。題解圍繞平面幾何這個中心，以斜率為主線，整個解題過程一氣呵成，又避免了令人頭暈的代數(shù)式變換，堪稱以形助數(shù)的經(jīng)典例題。順便提一下：這種方法在加速決策過程，很多動態(tài)規(guī)劃算法都可以運用本題“斜率優(yōu)化”的方法提高算法效率

14、。如IOI 2002的batch和BOI 2003的euro等。至于這類題目的共同特點，還是很值得研究的，但不在本文討論范圍內(nèi)，因而不再討論，但歡迎有興趣的同學(xué)以后和我交流。以數(shù)助形古希臘的畢達哥拉斯認為“萬物皆數(shù)”，的確，數(shù)是反映事物本質(zhì)特征的最好方法之一。數(shù)學(xué)發(fā)展史上，正是在解析幾何創(chuàng)立之后，人們才對各種繁雜的曲線有了更深入的了解。如今信息時代中，計算機處理各類事物，最終無不是歸結(jié)于二進制數(shù)的基本運算，數(shù)的重要性可見一斑。在當今信息學(xué)競賽中，一些試題給出的描述中圖形極為復(fù)雜，容易使選手陷入“迷魂陣”，在這種情況下，以數(shù)助形，一舉抓住其本質(zhì)特征，不失為解題的一種好方法。例三畫室(POI oi

15、 V Stage I)題意簡述定義尺寸為0的方陣為一個1*1的矩陣，在其唯一的一個方格中有一個小孔。對于i>0，遞歸的定義尺寸為i的方陣如下圖所示：圖 4給定方陣的尺寸N，以及另外兩個參數(shù)X和Y。準備兩個尺寸為N的方陣，一個疊放在另一個上面，再將上面的方陣向右移動X列，同時向上移動Y行。如此操作之后，求兩個方陣有多少個公共的孔。如右上圖，尺寸為2的方陣，向右平移2列，向上平移2行。則兩個方陣有3個公共小孔。范圍：N100。分析直接分析兩個方陣相交后的情況是可行的，我曾經(jīng)看過一些集訓(xùn)隊前輩的解題報告，都是這么分析的，但是方法很繁，思考量很大。下圖是某解題報告中的一個說明附圖，報告中先標出兩

16、個方陣的相交區(qū)域，再分情況討論。顯然可以看出，直接從“形”來分析本題，路子是很坎坷的。圖 5目標數(shù)值化我們不如換至和“形”相對的另一面“數(shù)”來思考，按照下圖所示的x, y方向為每行每列從0開始編號，最大至2N-1，于是每一個方格都有唯一的坐標(x, y)。圖 6下面來研究一下在什么條件下，一個方格P(x, y)內(nèi)有小孔。由于方陣是二分遞歸定義的，于是我們很自然聯(lián)想到將x和y化為二進制。設(shè)x和y的二進制表示分別為：a1a2a3aN 和 b1b2b3bN來看兩個數(shù)的第1位，a1和b1，如下圖，它們一共有4種取值方法，其分布分別對應(yīng)著遞歸定義中的左上、左下、右上、右下四塊區(qū)域。顯然當a1=0且b1=

17、1時無論以后各位取什么數(shù)，P點內(nèi)都不會有小孔：因為其已經(jīng)落在了左上無孔區(qū)。否則可以同理討論兩個數(shù)的第2位，第3位圖 7 示意(a1, b1)的取值分布情況得到的結(jié)論是，當且僅當不存在1iN，滿足ai=0且bi=1時，方格P內(nèi)有小孔。不妨稱這個為方格的有孔性質(zhì)。動態(tài)規(guī)劃解題后面的問題就非常簡單了，題目要找的無非是這樣的有序數(shù)對(x, y)的個數(shù)：0x, y，x+X, y+Y2N-1，且(x, y)，(x+X, y+Y)的二進制表示都滿足有孔性質(zhì)稱這個為方格的有公共孔性質(zhì)。我們可以采用動態(tài)規(guī)劃的方法：首先將X,Y也都轉(zhuǎn)化成二進制形式：p1p2p3pN 和 q1q2q3qN以位數(shù)為階段，通過記錄進位

18、情況保證無后效性：f(i, k1, k2)表示第i位至第N位部分滿足有公共孔性質(zhì)的有序?qū)倲?shù)，且要滿足這一部分有序?qū)Φ淖鴺撕蛯?yīng)部分的X, Y相加進位分別是k1和k2：顯然0k1, k21。動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移是非常簡單的，但描述比較復(fù)雜：每一次轉(zhuǎn)移需要約(22)2=16次運算，因此不再贅述，有興趣的讀者可以查看附件中的程序。最后說明一下，題目所要的答案就是f(1, 0, 0)。算法若不算上高精度，時間復(fù)雜度為O(N)，若使用循環(huán)數(shù)組，空間上僅需要常數(shù)個高精度數(shù)組 直接用“形”的方法做出的程序，空間復(fù)雜度是O(N)的，而且程序很長，詳見附錄。，而且實現(xiàn)程序也極為簡單，包括高精度也不過100多行。

19、對比從“形”上得出的算法，“數(shù)”的優(yōu)越性是不言而喻的。小結(jié)回顧解題過程，當分析發(fā)現(xiàn)兩方陣相交情況較復(fù)雜，不宜討論時，我們決定避開“形”的正面沖突，而從“數(shù)”這方面下手，很快便取得了令人滿意的效果：方格的有孔性質(zhì)和有公共孔性質(zhì)使題目的要求顯得簡單了許多。到此就可以套用經(jīng)典的動態(tài)規(guī)劃算法了?？梢哉f本題是一個較好的例子，但類似以數(shù)助形的例題似乎比較罕見。事實上，正如前文所述，一般的計算機都是以數(shù)為基礎(chǔ)的，同學(xué)們在寫各類程序的時候，最終還是要歸結(jié)到“數(shù)”來實現(xiàn)，對數(shù)的重要作用多少有些熟視無睹了。而從上例又可以看出，如果試題加以適當?shù)摹罢`導(dǎo)”，選手們背離“數(shù)”的捷徑，南轅北轍也不是沒有可能的。因此，在遇

20、到如同上例的題目時，面對多元化的復(fù)雜圖形，化形歸數(shù)，往往是抓住題目要害的好方法?？偨Y(jié)數(shù)與形是現(xiàn)實世界中客觀事物的抽象和反映，是數(shù)學(xué)的基石，也是信息學(xué)競賽命題涉及的兩個主要方面。數(shù)形結(jié)合是一種古老的數(shù)學(xué)思想，新興的信息學(xué)奧林匹克競賽又賦予她新的活力。上文舉了三個實例，大體上來說，都巧妙的運用了數(shù)形結(jié)合思想。但從細節(jié)上分析，它們之間仍略有差異。其一，三者從兩個不同的側(cè)重點闡述了數(shù)形結(jié)合思想的內(nèi)涵，即以形助數(shù)和以數(shù)助形。但在實際問題中，數(shù)和形決沒有明確的界限，數(shù)形結(jié)合思想也并不僅僅局限于文中提出的兩個方面。更多的情況下，數(shù)與形互相促進、互相包含，在一定條件下互相轉(zhuǎn)化，可以用“數(shù)形互助”一詞來形容。這

21、，體現(xiàn)了數(shù)形的辯證矛盾關(guān)系和數(shù)形結(jié)合思想的多元性。其二，用“形”來解例題二，似乎是唯一的出路，但在例一和例三中，并不是僅僅能用文中提到的方法解題，其他精彩解法我也略知一二。但相比而言，巧妙的使用數(shù)形結(jié)合思想會大大降低思考和編程復(fù)雜度，為我們在短短的競賽時間中迅速解題開辟了一條便捷的道路。需要指出的是，不同的人有不同的知識結(jié)構(gòu)，比賽經(jīng)驗等，他們對某一算法難度系數(shù)的感覺也是不同的。因而對同一題而言，不同的人可能會選擇不同的數(shù)形之路解題。這，體現(xiàn)了數(shù)形結(jié)合思想的個體差異性。而本文提出的三個例子，都是選擇了大多數(shù)人能夠接受的算法，卻并不能說是每位讀者心目中最簡單的算法。但醉翁之意不在酒，幾個小例子僅作

22、拋磚引玉，重點在于探討如何在信息學(xué)競賽中運用數(shù)形結(jié)合思想。在信息學(xué)競賽中運用數(shù)形結(jié)合思想，就是在處理問題時，斟酌問題的具體情形，善于抓住問題的主要矛盾，使數(shù)量關(guān)系的問題借助于幾何圖形直觀而形象化，或者使圖形問題借助于數(shù)量關(guān)系而本質(zhì)化。數(shù)形結(jié)合，重在“結(jié)合”二字。靈活的運用數(shù)形結(jié)合思想，需要重視思想的個體差異性，根據(jù)各人的現(xiàn)有知識水平和思維方式，有機的將抽象的數(shù)學(xué)、計算機語言與直觀的圖形結(jié)合起來，將抽象思維與形象思維結(jié)合起來，實現(xiàn)抽象概念與具體形象的聯(lián)系和轉(zhuǎn)化，更快更好更簡單的解決實際問題。附錄關(guān)于2003年上海市選拔賽題Sequence題意簡述一個序列Ai, i=0, 1, 2, , 3N由3N+1項組成，每一項要么為1，要么為 -2。定義部分和SK=A0+A1+AK，求所有滿足性質(zhì)P的序列A的數(shù)目，性質(zhì)P為：S3N = 1且對于所有的K = 0,