算法合集之淺談補集轉(zhuǎn)化思想在統(tǒng)計問題中的應(yīng)用-閱讀頁
2025-01-24 09:23本頁面
【正文】 ? 矩形 A 的左上角為 (AX1,AY1)，右下角為 (AX2,AY2)，矩形 B 的左上角為(BX1,BY1)，右下角為 (BX2,BY2)，如果存在某兩個格子 a∈ A， b∈ B 且 a、 b相鄰或重合，就稱 A 和 B“相交”。 ? 設(shè)一個已經(jīng)擺放的矩形 A 為 X 行 Y 列，新擺放的矩形 B 為 P 行 Q 列，矩形B 怎樣擺放才能和矩形 A 相交呢？根據(jù)結(jié)論二我們直接就可以得出 結(jié)論三 ：矩形 B 能夠與 A 相交的所有方案位于一個 2P+X 行， 2Q+Y 列的矩形框內(nèi)。當然，這樣說還不是太嚴密，因為這個矩形框有可能超出了棋盤的邊界，此時它的邊就要調(diào)整到棋盤邊界內(nèi)。 圖六 補集轉(zhuǎn)化 根據(jù)結(jié)論一，在給定的棋盤上不加限制擺放一個矩形，其方案數(shù) S 是可以根據(jù)公式計算出來的。問題就轉(zhuǎn)化為：如何高效地求出 T。 在結(jié)論三的基礎(chǔ)上稍加判斷，再結(jié)合結(jié)論一，我們實際上已經(jīng)能夠直接計算和任意一個已經(jīng)擺放的矩形相交的方案數(shù)。因為有些擺放方案會同時和不止一個矩形相交，例如圖七中，藍色的矩形同時和兩個黑色黑色已擺放矩形相交。 圖七 如何排除這種重復計數(shù)呢？我們采用一種排除重復的常用方法：有序化。例如圖七中，如果我們規(guī)定左邊的黑色矩形編號較小，則在處理右邊的黑色矩形時，與它相交的藍色擺放方案就不允許計入 T，因為右邊的黑色矩形并不是與藍色方案相交的編號最小的已擺放矩形。 為了做到這一點，我們只需采取如下算法：依次處理每個 已經(jīng)擺放的矩形，設(shè)當前處理的矩形編號為 i，一一枚舉與它相交的擺放方案，對于每個方案，再依次枚舉編號為 1,2,?? (i1)的矩形，判斷這些矩形能否與當前枚舉的方案相交，如果發(fā)現(xiàn)有相交的情況，則此方案不能計入 T，否則就將 T 加 1。而且，一旦想到了補集轉(zhuǎn)化，則下面的分析、算法設(shè)計都非常自然，程序基本上都是循環(huán)枚舉和簡單的判斷。 小結(jié) 在這個例子中，離散化思想能夠幫助我們解決原題，但是時間、思維和編程復雜度都很高。 本題從正面考慮，枚舉量太大，所以常規(guī)的解法是采用離散化技巧來減少枚舉量。補集轉(zhuǎn)化思想在這里起到的作用是幫助我們選擇了合適的枚舉對象，從而減少了枚舉量 。 但是補集轉(zhuǎn)化思想體現(xiàn)在兩個具體的例子中，又有所不 同： 從作用效果上來看，在例 1 中，補集轉(zhuǎn)化思想指導我們設(shè)計出了本質(zhì)上不同于單純枚舉的算法 — 枚舉＋組合計數(shù)，可以說是“另辟奚徑”；而在例 2 中，它并沒有改變算法的本質(zhì)，而只是通過改變枚舉對象減少了枚舉量。 從意義價值上看，在例 1 中，補集轉(zhuǎn)化思想似乎是解決問題的唯一可行方法；而在例 2 中，用離散化也可以解決問題，但補集轉(zhuǎn)化的算法更自然、更優(yōu)秀，更有普遍性。 總之， 補集轉(zhuǎn)化思想可以比較廣泛地應(yīng)用于統(tǒng)計問題中，是解決統(tǒng)計問題的一種很值得掌握的非常規(guī)思想 。統(tǒng)計問題的本質(zhì)就是在給定了對象之間的一系列關(guān)聯(lián)、限制（也就是矛盾）的基礎(chǔ)上進行計數(shù)的問題。我們應(yīng)該注意培養(yǎng)逆向思維的能力，才能用好、用活補集轉(zhuǎn)化思想。雖然在本文的例子中，補集轉(zhuǎn)化思想有著很多的閃光之處，但是并不能認為常規(guī)方法一定不如非常規(guī)方法。
試題試卷相關(guān)推薦
鄂ICP備17016276號-1