論文國家隊胡偉棟

《論文國家隊胡偉棟》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、減少冗余與算法優(yōu)化長沙市長郡中學(xué)胡偉棟1摘要】在信息學(xué)競賽中，我們經(jīng)常會遇到冗余，而冗余會造成算法、程序的效率不同程度的降低：有的是微不足道的，而有的會導(dǎo)致算法復(fù)雜度大大提高。本文針對后者，舉例說明冗余對算法效率的影響和如何減少冗余。【關(guān)鍵字】冗余、算法優(yōu)化1正文】引言信息學(xué)競賽屮，我們所追求的口標(biāo)之一，是使程序用最少的時間解決問題,也就是達到最高的效率。實際生活中也同樣需要這樣，高效率者往往會在競爭中収得優(yōu)勢。冗余，是指多余的或重復(fù)的操作。在搜索、遞推、動態(tài)規(guī)劃等諸多的算法中,都會出現(xiàn)兀余。曲冗余的定義，要使算法達到最高的效率，必須去除算法中的冗余處理。

2、但完全去除兀余是難以實現(xiàn)的，使程序用絕對最少的時間解決問題也是很難的，通由兀余的定義,常需要退一步，將忖標(biāo)改為：使程序用盡量少的時間解決問題?？梢缘玫剑阂岣咚惴ǖ男?，必須減少算法中的冗余處理。要減少兀余，需要在大量的做題過程屮，不斷探索，不斷積累經(jīng)驗。下面就讓我們通過兩個具體的例子來研究冗余是如何彫響算法效率的以及如何減少兀余。二整數(shù)拆分2.1問題描述①將正整數(shù)N拆分成若干個整數(shù)的和，使拆分成的數(shù)是2的非負整數(shù)幕的形式。問有多少種拆分方案。如果兩個方案僅有數(shù)的順序不同，它們算作同一種方案。如：當(dāng)N=5時，可以拆分成下面的形式：5=14-1+1+1+15

3、=1+14-1+25=1+2+25=1+4①題目來源：金愷原創(chuàng)第1頁共10頁所以，5有4種拆分方案。2.2粗略分析此題可用遞推解決（為什么？請讀者自己思考5用F[iJ]表示i拆分成若干個數(shù)，其中最大的數(shù)不超過2,的拆分總數(shù)。則:1°F[OJ]=12°FfZ,01=1,即I拆分成若干個數(shù)，其屮最大的數(shù)不超過2o=l的拆分方案只有一種：把i拆分成i個1o3°當(dāng)z>0j>0時，F(xiàn)[i,j]由兩類組成：第一類：拆分成的最大數(shù)止好是2）,其總數(shù)為F[i2第二類：拆分成的最人數(shù)小于2j,其總數(shù)為F[iJ1]。所以F[i9j]=F[i2)J]+F[jJl]o最后要計算的

4、

5、=[標(biāo)是F[N,M]o因為i2/必須wO,所以Ilog2/

6、J,又有18/5/Vo不難得出：總的時間復(fù)雜度是0（N阻2N）①,空間復(fù)雜度也是O（NgN）o看上去，這個復(fù)雜度已經(jīng)很低了。但是，復(fù)雜度能不能再低一點兒呢？2.3減少冗余為了便于研究，可以首先處理W是2的整數(shù)幕這種特殊情況，然后把N不是2的整數(shù)幕的情況化為N是2的整數(shù)幕的情況處理。2?3?1當(dāng)N是2的整數(shù)次幕時把所有的F[iJ]對應(yīng)將橫坐標(biāo)為z的點稱設(shè)N=2m（M為非負整數(shù)）。首先，為了討論時更直觀,到以I為橫軸，丿為縱軸的直角坐標(biāo)系中的每一個整點上,為第i列的點、縱坐標(biāo)為j的點稱為第/行的點

7、。是第i列，第丿?行的點）若點C是點A與點B的和②，則連有向邊AC和BC（如圖A所示）。①此處所講的時空復(fù)雜度都忽略了高粹度的因索。因為當(dāng)N達到10000000時答案也只有60位，這個數(shù)字是比較小的。?當(dāng)C為F[iJ]時，由遞推方程，A、B分別為F[i2丿J]、F[iJ1]。第2頁共10頁J32C(F[iJ])11])0123456圖A(M=3,N=078I根據(jù)遞推關(guān)系將所有的邊都連出來，可以得到圖BoJD321E0123456圖B(M=3,/V=8)78I觀察耍計算的冃標(biāo)F[N,M],它是F[N2.w,M]=F[0,M]與F[N,M1]的和，而F[N1]

8、是2mi,M1]與F[N,M2]的和；F[N,M2]是F[N2a/2,M2]與F[N3]的和……可以看出，圖中有很多的點(如圖B中的D,E)的值求出與不求出都不影響最后的答案，所以這些點都沒必要求出，都是冗余的，在圖中也沒必要向這些點連邊。將這些兀余的點和邊刪掉，只留下最后可能影響到冃標(biāo)點的點和邊，圖B變成了圖C的樣子，可以看岀，圖C比圖B簡潔多了，要計算的點數(shù)也少多了。3210123456781圖C(M=3,N=8)那么，到底要計算多少個點呢？觀察圖C,發(fā)現(xiàn)當(dāng)j達到最大，即j=M時第丿?行只需要計算1個值F[N,M]；當(dāng)j=M1時第j行要計算2個值——F

9、N,M1]和F[1]j=M2時第J行要計算4個值——F[-,M2]、F[-2]、F[-,M2]Ii4和F[N9M2J……由此可以猜想：①當(dāng)j=M氐時第丿行要且只要計算2,個值。k這兩個猜想是否正確呢？答案是肯定的，下面用歸納法證明：1°當(dāng)j=M時，第丿行只要計算F[N,M],這是顯然的。猜想①、②此時都成立。k1個數(shù)。取j'=j=Mk,當(dāng)/=/o時，由于第J行耍計算F[/o2./,j],由遞推方程，第廣行要計算F仏2八廣]=F[2*/°2八廣]，而計算川2*厶2?，廣]乂要用到F[(2/o1)*2廠,廣],計算F[(2/o1)*2?廠，廣]時要用至IJ

10、F[(2/o2)*2；,/]……，-直下去,最后所有的F[x*2>