國家集訓(xùn)隊2005論文集 朱晨光

《國家集訓(xùn)隊2005論文集 朱晨光》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、淺析倍增思想在信息學(xué)競賽中的應(yīng)用安徽省蕪湖市第一中學(xué)朱晨光淺析倍增思想在信息學(xué)競賽中的應(yīng)用安徽省蕪湖市第一中學(xué)朱晨光目錄?摘要2?關(guān)鍵字2?正文2u引言2u應(yīng)用之一在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移2u應(yīng)用之二加速區(qū)間操作8u一個有趣的探討11?總結(jié)12?感謝12?參考文獻13?附錄13第29頁共29頁淺析倍增思想在信息學(xué)競賽中的應(yīng)用安徽省蕪湖市第一中學(xué)朱晨光摘要倍增思想是解決信息學(xué)問題的一種獨特而巧妙的思想。本文就倍增思想在信息學(xué)競賽中兩個方面的應(yīng)用進行了分析。全文可以分為五個部分：第一部分引言，簡要闡述了倍增思想的重要作用以及運用方法；第二部分介紹倍增

2、思想的第一個應(yīng)用——在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移；第三部分介紹倍增思想的第二個應(yīng)用——加速對區(qū)間進行的操作；第四部分探討了一個有趣的問題，即為什么倍增思想每次只將考慮范圍擴大一倍而不是兩倍、三倍等；第五部分總結(jié)全文，再次指出倍增思想的重要性以及應(yīng)該怎樣靈活運用倍增思想。關(guān)鍵字倍增思想變化規(guī)則狀態(tài)轉(zhuǎn)移區(qū)間操作正文引言倍增思想是一種十分巧妙的思想，在當(dāng)今的信息學(xué)競賽中應(yīng)用得十分廣泛。盡管倍增思想可以應(yīng)用在許多不同的場合，但總的來說，它的本質(zhì)是：每次根據(jù)已經(jīng)得到的信息，將考慮的范圍擴大一倍，從而加速操作。大家所熟悉的歸并排序?qū)嶋H上就是倍增思想的一個經(jīng)典應(yīng)用

3、。在解決信息學(xué)問題方面，倍增思想主要有這兩個方面的應(yīng)用——一、在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移；二、加速區(qū)間操作。下文將就這兩個方面進行詳細(xì)的討論。倍增思想應(yīng)用之一在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移這里是指由一種狀態(tài)變化到另一種狀態(tài)，并不只限于動態(tài)規(guī)劃中的“狀態(tài)轉(zhuǎn)移”。首先，讓我們來看一個簡單的例子——已知實數(shù)a，計算a17。分析：很顯然，一種最簡單的方法就是令b=a，然后重復(fù)16次進行操作b=b*a.這樣，為了得到a17，共進行了16次乘法。第29頁共29頁淺析倍增思想在信息學(xué)競賽中的應(yīng)用安徽省蕪湖市第一中學(xué)朱晨光現(xiàn)在考慮另外一種方法，令a0=a,a1

4、=a2,a2=a4,a3=a8,a4=a16,可以看出，ai=ai-12,(1<=i<=4)。于是，得到a0,a1,a2,a3,a4共需要4次乘法。而a17=a*a16=a0*a4,也就是說，再進行一次乘法就可以得到a17.這樣，總共進行5次乘法就算出了a17.如果將這種方法推而廣之，就可以解決這樣一個一般性的例題：例1、已知，計算:分析：1、將n表示成為二進制形式并提取出其中的非零位，即n=2b1+2b2+……+2bw，不妨設(shè)b1

5、3、根據(jù)冪運算的法則，可以推出==**……*，而這些數(shù)都已經(jīng)被求出，所以最多再進行(bw+1)次操作就可以得到。由于n的二進制表示最多有個非零位，所以bw最大為。也就是說，最多進行O()次乘法就可以算出，這比進行O(n)次乘法效率高得多。當(dāng)然，由于得到n的二進制表示的過程本身就是按照從低位到高位的順序，所以并不需要記錄，，，……，，只需要每次即算即用就可以了。偽代碼如下（見下頁）：那么，這個算法是如何減少乘法次數(shù)的呢？顯然，==**……*使得求轉(zhuǎn)化為求不超過個a的冪的積。而序列，，，……，中除了第一個數(shù)以外，每一個數(shù)都是前一個數(shù)的平方。即在從得到的過程中，

6、按照原始的方法需要進行2i次乘法操作，而現(xiàn)在只需要利用已知結(jié)果進行一次乘法操作（*=）即可。大大減少了操作次數(shù)，從而降低了時間復(fù)雜度。第29頁共29頁淺析倍增思想在信息學(xué)競賽中的應(yīng)用安徽省蕪湖市第一中學(xué)朱晨光longdoublepower(longdoublea,longn){longdoubleb,result;result=1;b=a;while(n){if(n%2)result*=b;b*=b;n/=2;}returnresult;}算法1.1而在實際情況中，a可能是一個實數(shù)，也可能是一個矩陣或是一個抽象的狀態(tài)。變化規(guī)則也可能是其他操作（如矩陣乘法、

7、動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移等）。但是只要符合以下兩個條件，就可以應(yīng)用倍增思想并采用類似于上面的方法加速計算：1、每次的變化規(guī)則必須相同；2、變化規(guī)則必須滿足結(jié)合律。具體到上面的例子，每次的變化規(guī)則都是乘法，而乘法是滿足結(jié)合律的。下面將通過另一個例子更加深入地探討倍增思想在加速狀態(tài)轉(zhuǎn)移方面的應(yīng)用，同時得到更精確的定義。例2、骰子的運動CEPC2003ProblemDDiceContest給定一個六個面的骰子，每個面上都有一定的權(quán)值（1到50之間的整數(shù)）。骰子運動的范圍是一個寬度為4，向左右無限延伸的帶子（如圖1.1）。帶子從左到右的橫坐標(biāo)值為……，-3，-2，-1，

8、0，1，2，3，……，從前到后的縱坐標(biāo)值依次為1，2，3，4（這里