算法合集之淺談補(bǔ)集轉(zhuǎn)化思想在統(tǒng)計(jì)問(wèn)題中的應(yīng)用-資料下載頁(yè)
2025-01-09 09:23本頁(yè)面
【正文】 ，這樣計(jì)數(shù)不會(huì)出現(xiàn)重復(fù)。 為了做到這一點(diǎn)，我們只需采取如下算法：依次處理每個(gè) 已經(jīng)擺放的矩形，設(shè)當(dāng)前處理的矩形編號(hào)為 i，一一枚舉與它相交的擺放方案，對(duì)于每個(gè)方案，再依次枚舉編號(hào)為 1,2,?? (i1)的矩形，判斷這些矩形能否與當(dāng)前枚舉的方案相交，如果發(fā)現(xiàn)有相交的情況，則此方案不能計(jì)入 T，否則就將 T 加 1。 根據(jù)結(jié)論三，與每個(gè)已擺放的 X 行 Y 列的矩形相交的擺放方案位于它周圍的一個(gè)矩形框內(nèi)，這個(gè)矩形框最多 2P+X 行， 2Q+Y 列，再根據(jù)結(jié)論一，在其中擺放 P 行 Q 列的矩形最多只有 (P+X+1)*(Q+Y+1)種方案，由于每個(gè)矩形的大小均在 P*Q 這樣的級(jí)別，所以總共需要處理的方案數(shù)規(guī)模為 O(P2Q2L)，而對(duì)于每個(gè)方案，最多只需要枚舉 L－ 1 個(gè)已擺放矩形判斷是否與之相交，根據(jù)結(jié)論二，判斷兩個(gè)矩形是否相交的復(fù)雜度為 O(1)，所以處理每個(gè)方案的復(fù)雜度為 O(L)，因此整個(gè)算法的復(fù)雜度僅為 O(P2Q2*L2)，非常優(yōu)秀，大大領(lǐng)先于離散化的常規(guī)方法。而且，一旦想到了補(bǔ)集轉(zhuǎn)化，則下面的分析、算法設(shè)計(jì)都非常自然，程序基本上都是循環(huán)枚舉和簡(jiǎn)單的判斷?？梢哉f(shuō)，在思維復(fù)雜度和編程復(fù)雜度上，基于補(bǔ)集轉(zhuǎn)化的算法比離散化的常規(guī)算法好得多。 小結(jié) 在這個(gè)例子中，離散化思想能夠幫助我們解決原題，但是時(shí)間、思維和編程復(fù)雜度都很高。但 是利用補(bǔ)集轉(zhuǎn)化思想，我們卻可以設(shè)計(jì)出全面超越離散化算法的新算法。 本題從正面考慮，枚舉量太大，所以常規(guī)的解法是采用離散化技巧來(lái)減少枚舉量。但是從反面考慮，枚舉量就非常小了。補(bǔ)集轉(zhuǎn)化思想在這里起到的作用是幫助我們選擇了合適的枚舉對(duì)象，從而減少了枚舉量 。 總結(jié) 本文中的兩個(gè)例子都是利用補(bǔ)集轉(zhuǎn)化思想解決統(tǒng)計(jì)問(wèn)題，它們?cè)谒枷肷嫌兄黠@的相同點(diǎn)：如果目標(biāo) R 比較難以求解，而它的補(bǔ)集 T 以及 R 和 T 的總和 S相對(duì)容易求出，那么不妨從反面考慮，求出 S 和 T，也就間接地求出了 R。 但是補(bǔ)集轉(zhuǎn)化思想體現(xiàn)在兩個(gè)具體的例子中，又有所不 同： 從作用效果上來(lái)看，在例 1 中，補(bǔ)集轉(zhuǎn)化思想指導(dǎo)我們?cè)O(shè)計(jì)出了本質(zhì)上不同于單純枚舉的算法 — 枚舉＋組合計(jì)數(shù)，可以說(shuō)是“另辟奚徑”；而在例 2 中，它并沒(méi)有改變算法的本質(zhì)，而只是通過(guò)改變枚舉對(duì)象減少了枚舉量。由此可見(jiàn)，補(bǔ)集轉(zhuǎn)化思想應(yīng)用于統(tǒng)計(jì)問(wèn)題的形式是多種多樣的，可以從解決問(wèn)題的每個(gè)方面幫助我們 。 從意義價(jià)值上看，在例 1 中，補(bǔ)集轉(zhuǎn)化思想似乎是解決問(wèn)題的唯一可行方法；而在例 2 中，用離散化也可以解決問(wèn)題，但補(bǔ)集轉(zhuǎn)化的算法更自然、更優(yōu)秀，更有普遍性。由此可見(jiàn)，補(bǔ)集轉(zhuǎn)化思想不僅可以應(yīng)用于一些非常規(guī)的統(tǒng)計(jì)問(wèn)題，而且 對(duì)于一些常 規(guī)算法能夠解決的問(wèn)題，應(yīng)用補(bǔ)集轉(zhuǎn)化思想也許可以做得更好 。 總之， 補(bǔ)集轉(zhuǎn)化思想可以比較廣泛地應(yīng)用于統(tǒng)計(jì)問(wèn)題中，是解決統(tǒng)計(jì)問(wèn)題的一種很值得掌握的非常規(guī)思想 。 補(bǔ)集轉(zhuǎn)化思想，體現(xiàn)了 矛盾對(duì)立統(tǒng)一，互相轉(zhuǎn)化 的一種哲學(xué)觀念。統(tǒng)計(jì)問(wèn)題的本質(zhì)就是在給定了對(duì)象之間的一系列關(guān)聯(lián)、限制（也就是矛盾）的基礎(chǔ)上進(jìn)行計(jì)數(shù)的問(wèn)題。所以在統(tǒng)計(jì)問(wèn)題中靈活地應(yīng)用補(bǔ)集轉(zhuǎn)化思想，往往可以起到“出奇制勝”的效果。我們應(yīng)該注意培養(yǎng)逆向思維的能力，才能用好、用活補(bǔ)集轉(zhuǎn)化思想。 值得注意的是，利用補(bǔ)集轉(zhuǎn)化思想解決統(tǒng)計(jì)問(wèn)題作為一種非常規(guī)的統(tǒng)計(jì)方法，它和一些 常規(guī)的統(tǒng)計(jì)方法、技巧之間的關(guān)系是辨證的。雖然在本文的例子中，補(bǔ)集轉(zhuǎn)化思想有著很多的閃光之處，但是并不能認(rèn)為常規(guī)方法一定不如非常規(guī)方法。大多數(shù)的統(tǒng)計(jì)問(wèn)題還是適合用常規(guī)方法的，所以 只有將常規(guī)方法和非常規(guī)方法都靈活地掌握，并對(duì)于具體問(wèn)題選擇合適的方法，才能夠游刃有余地解決統(tǒng)計(jì)問(wèn)題 。
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1