淺談信息學中狀態(tài)的合理設計與應用ppt課件

1、l在日常生活中，任務時間與任務數(shù)量、在日常生活中，任務時間與任務數(shù)量、單位效率的關(guān)系可以用下面的這個式子單位效率的關(guān)系可以用下面的這個式子來表達：來表達：l任務時間任務時間=任務數(shù)量任務數(shù)量*單位效率單位效率l在信息學中，程序的運轉(zhuǎn)時間是由兩個在信息學中，程序的運轉(zhuǎn)時間是由兩個要素決議的，程序中所處置的形狀的總要素決議的，程序中所處置的形狀的總數(shù)目和處置每個形狀所破費的時間。數(shù)目和處置每個形狀所破費的時間。l程序運轉(zhuǎn)時間程序運轉(zhuǎn)時間=形狀總數(shù)形狀總數(shù)*單位效率單位效率 l信息學中的形狀總數(shù)有時隱藏著許多冗信息學中的形狀總數(shù)有時隱藏著許多冗余形狀。我們對形狀的合理設計與運用余形狀。我們對形狀的合

2、理設計與運用不僅能優(yōu)化的算法效率，還可以協(xié)助編不僅能優(yōu)化的算法效率，還可以協(xié)助編程人員理清思緒，降低思想難度。程人員理清思緒，降低思想難度。例一 Square Root形狀分析合理地分析形狀數(shù)目例二 Banal Tickets形狀優(yōu)化對形狀進展優(yōu)化例三 Shoot Your Gun形狀設計重新設計形狀l定義邊平行于坐標軸的簡單多邊形為矩形多邊定義邊平行于坐標軸的簡單多邊形為矩形多邊形。形。l知在一個大的矩形多邊形知在一個大的矩形多邊形M中有兩個小的矩形中有兩個小的矩形多邊形多邊形G和和T。G邊上的恣意一點可以向其左上、邊上的恣意一點可以向其左上、左下、右上、右下四個方向發(fā)射出射線。射線左下、右

3、上、右下四個方向發(fā)射出射線。射線在遇到在遇到M的邊時會發(fā)生光的鏡面反射。的邊時會發(fā)生光的鏡面反射。l求從求從G邊上的恣意一點發(fā)出一條射線到邊上的恣意一點發(fā)出一條射線到T所需所需求的最少反射次數(shù)。求的最少反射次數(shù)。l矩形多邊形最多包含矩形多邊形最多包含50條邊，頂點坐標為整數(shù)條邊，頂點坐標為整數(shù)在在0，4000之內(nèi)。之內(nèi)。以下圖左描畫出了一個例子，以下圖中描畫了在特殊點時的反射規(guī)那么。射線方向如以下圖右。l標題中標題中G邊上的恣意一點都可以發(fā)射出邊上的恣意一點都可以發(fā)射出射線。射線。枚舉？l只需求處置整點和只需求處置整點和1/2點即可。點即可。l運用普通的形狀表示法，將每個點發(fā)射出的4個方向分別

4、做為4個點，進展構(gòu)圖并運用最短路算法進展求解。l這樣的形狀數(shù)是O(n2)級別的，不能很好的處理此題。l標題條件：l道路軌跡遵照光的傳播道路 l光是沿直線傳播的，只需在遇到妨礙物時才會發(fā)生反射 l只需發(fā)生反射時，道路方向才會發(fā)生改動。也就是說，只需在邊上才能夠使方向發(fā)生變化。如以下圖，圖中加粗的邊為射線的軌跡。l因此我們無妨將邊上的點作為形狀因此我們無妨將邊上的點作為形狀l運用運用spfa算法那么可以滿足標題時間和算法那么可以滿足標題時間和空間的要求。空間的要求。l用用spfa算法處理此題效果并不好。算法處理此題效果并不好。l光路是不會部分重疊的，要么完全不重光路是不會部分重疊的，要么完全不重疊

5、，要么完全重疊。疊，要么完全重疊。l只需求枚舉起點，然后每次遇到多邊形只需求枚舉起點，然后每次遇到多邊形的邊的時候模擬反射，直到到達的邊的時候模擬反射，直到到達T集合。集合。 l這樣做之后，程序?qū)崿F(xiàn)起來非常簡單，這樣做之后，程序?qū)崿F(xiàn)起來非常簡單，運轉(zhuǎn)效率也很高。至此，我們很好地處運轉(zhuǎn)效率也很高。至此，我們很好地處理了此題。理了此題。l對形狀優(yōu)化的方法是基于對形狀的表示對形狀優(yōu)化的方法是基于對形狀的表示和對標題條件的深化分析而設計的。和對標題條件的深化分析而設計的。 l在很多時候，對單位效率進展優(yōu)化難以在很多時候，對單位效率進展優(yōu)化難以奏效，對形狀進展合理地優(yōu)化與設計卻奏效，對形狀進展合理地優(yōu)化

6、與設計卻能大顯身手，獲得良好的效果。能大顯身手，獲得良好的效果。l對形狀進展合理地分析及設計能協(xié)助我對形狀進展合理地分析及設計能協(xié)助我們更好的理清頭緒并設計出簡約的算法。們更好的理清頭緒并設計出簡約的算法。謝謝 謝謝l假設整數(shù)假設整數(shù)x滿足滿足 x2 a (mod n)，那么稱，那么稱x 是是以以n為模時為模時a的平方根，記的平方根，記root(a,n)為滿足以上為滿足以上條件的條件的x的集合。標題包含的集合。標題包含k個訊問，每次訊問個訊問，每次訊問給出給出a和和n，其中，其中n為質(zhì)數(shù)，且為質(zhì)數(shù)，且a與與n互質(zhì)，要求互質(zhì)，要求出一切在出一切在(0,n-1)區(qū)間內(nèi)的區(qū)間內(nèi)的root(a,n)。

7、l數(shù)據(jù)范圍數(shù)據(jù)范圍l1=a,n=32767，n為質(zhì)數(shù)，為質(zhì)數(shù)，a與與n互質(zhì)互質(zhì)l1=k=100000l不難想到如下算法：不難想到如下算法：l枚舉枚舉x，然后算出，然后算出value(x)=x2 mod n，假設，假設value(x)等于等于a，那么就稱這個，那么就稱這個xRoot(a,n)。l每次枚舉復雜度為每次枚舉復雜度為O(N)，總復雜度為，總復雜度為O(KN)，因此這個算法是非常低效的。，因此這個算法是非常低效的。 重要條件n為質(zhì)數(shù)，a與n互質(zhì)如何利用？lK最多為最多為100000lN最多為最多為32767l根據(jù)鴿巢原理即可知根據(jù)鴿巢原理即可知N不同的訊問最多只不同的訊問最多只需需327

8、67個。個。l現(xiàn)實上，由于現(xiàn)實上，由于n為質(zhì)數(shù)，因此當為質(zhì)數(shù)，因此當N為為32767時最多只需時最多只需3500多個取值。多個取值。l我們在運用枚舉法的時候，是對x進展枚舉，然后判別x能否Root(a,n)。l仔細分析，不難發(fā)現(xiàn)，在求Root(a,n)的同時，我們可以順便求出Root(m,n) 0=mn)l因此，我們可以在對訊問進展分類后，對于n一樣的訊問，花O(N)的時間對第1個訊問進展枚舉，這樣剩下的訊問就可以用O(1)的時間得出結(jié)果了。l時間復雜度變成O(prime(n)*n+klogk)l給定一個長度為給定一個長度為2n(n=18)的數(shù)字串，數(shù)字串的數(shù)字串，數(shù)字串中有的位置的數(shù)字是知的

9、，以中有的位置的數(shù)字是知的，以0,9的數(shù)字表示；的數(shù)字表示；有的位置的數(shù)字是未知的，以有的位置的數(shù)字是未知的，以?表示。表示。l當且僅當一個數(shù)字串滿足以下條件時，稱這個當且僅當一個數(shù)字串滿足以下條件時，稱這個數(shù)字串數(shù)字串interesting，否那么為，否那么為banal:l要求求出一切要求求出一切interesting串和一切串和一切banal串的串的個數(shù)。個數(shù)。 2 *11 nniins is il求求interesting串的個數(shù)和求串的個數(shù)和求banal串的個串的個數(shù)這兩個問題是等價的，兩者為互補關(guān)數(shù)這兩個問題是等價的，兩者為互補關(guān)系。這樣，就可以經(jīng)過求其中的一個命系。這樣，就可以經(jīng)過

10、求其中的一個命題，來直接得到另一命題的解。而求題，來直接得到另一命題的解。而求interesting串的個數(shù)明顯比求串的個數(shù)明顯比求banal串的串的個數(shù)簡單，因此只思索求個數(shù)簡單，因此只思索求interesting串串的個數(shù)的命題。的個數(shù)的命題。 l不難得出這樣的一組方程：不難得出這樣的一組方程：l邊境條件邊境條件ll當當 時時l當當 時時10 , 0dp? is) 0mod(0) 0mod(, 1,isjisjisjidpjidp?is)9 , 0, 0mod(0)9 , 0, 0mod(, 1,lljlljljidpjidpldpi,j表示前表示前i位，乘積為位，乘積為j時的方案數(shù)。時的

11、方案數(shù)。設設dpa表示對前半部分進展動態(tài)規(guī)劃所表示對前半部分進展動態(tài)規(guī)劃所得出的結(jié)果，得出的結(jié)果，dpb表示后半部。表示后半部。l那么那么interesting串的個數(shù)為：串的個數(shù)為：l其中，其中，m為最大的形狀數(shù)。為最大的形狀數(shù)。0 , * , midpa n idpb n il當當s每位都取每位都取9時，總乘積到達最大時，總乘積到達最大189 =150094635296999121天文數(shù)字！需求優(yōu)化！l形狀形狀j只能夠是只能夠是0,9這這10個數(shù)的乘積，而個數(shù)的乘積，而這幾個數(shù)字只包含這幾個數(shù)字只包含2,3,5,7這這4個質(zhì)數(shù)。個質(zhì)數(shù)。l因此可以將形狀改為因此可以將形狀改為dpi,a,b,

12、c,d，表示，表示前前i位，乘積為位，乘積為2a3b5c7d的方案數(shù)。的方案數(shù)。l由于由于0無法用無法用2a3b5c7d表示，所以用表示，所以用2(-1)替代。替代。 l形狀總數(shù)形狀總數(shù)la最多為最多為3n(思索全部數(shù)字為思索全部數(shù)字為8的情況的情況)，b最多為最多為2n(全部為全部為9)，c最多為最多為n(全部為全部為5)，d最多為最多為n(全部為全部為7)。當。當n=18時，形時，形狀數(shù)目到達最大，為狀數(shù)目到達最大，為2*3*2*184=1259712(運用滾動數(shù)組運用滾動數(shù)組)。l但是此題需求運用高精度計算，這種做但是此題需求運用高精度計算，這種做法并不能令人稱心。法并不能令人稱心。l用

13、用2a3b5c7d這樣的形狀表示依然含有許這樣的形狀表示依然含有許多冗余形狀！多冗余形狀！l例如，例如，23n32n5n7n這個形狀就不能夠這個形狀就不能夠出現(xiàn)，由于出現(xiàn)，由于23n就曾經(jīng)決議了就曾經(jīng)決議了n位數(shù)字全位數(shù)字全為為8，所以其他質(zhì)數(shù)的個數(shù)不能夠大于，所以其他質(zhì)數(shù)的個數(shù)不能夠大于0l我們可以運用我們可以運用hash，經(jīng)過一個，經(jīng)過一個BFS的過的過程，遍歷出一切的可用形狀，并建立一程，遍歷出一切的可用形狀，并建立一一對應的映射關(guān)系一對應的映射關(guān)系l經(jīng)實際發(fā)現(xiàn)，對于極限形狀，運用經(jīng)實際發(fā)現(xiàn)，對于極限形狀，運用hash可以將原來的可以將原來的62萬左右的形狀數(shù)減少到萬左右的形狀數(shù)減少到5萬以下，這樣我們就可以有效地剔除冗萬以下，這樣我們就可以有效地剔除冗余了。余了。圖中從A點向右下方向發(fā)射的射線與方格的邊