第三課 提高班 枚舉模擬.ppt

1、枚舉算法,主講：蘭椿森,什么是枚舉,枚舉，通俗地講就是把所有的可能一個(gè)個(gè)列舉出來(lái) 比如：一周有星期一、星期二、星期三、星期四、星期五、星期六、星期天； 警察破案時(shí)羅列出所有的犯罪嫌疑人,百錢(qián)買(mǎi)百雞問(wèn)題,一百個(gè)銅錢(qián)買(mǎi)了一百只雞，其中公雞一只 5 錢(qián)、母雞一只 3 錢(qián)，小雞3 只一 錢(qián) ，問(wèn)一百只雞中公雞、母雞、小雞各多少 傳統(tǒng)數(shù)學(xué)方法 枚舉法,傳統(tǒng)數(shù)學(xué)方法,設(shè)一百只雞中公雞、母雞、小雞分別為 x，y，z，問(wèn)題化為三 元一次方程組： 5 x + 3 y + z / 3 = 100(百錢(qián)) x + y + z = 100(百雞) 可是計(jì)算機(jī)沒(méi)有你那么聰明，它自己不會(huì)解方程，怎么辦？,枚舉法,這里 x

2、,y,z 為正整數(shù),由于雞的總數(shù)是 100,可以確定x,y,z 的取值范圍:0=x,y,z=100,對(duì)于這個(gè)問(wèn)題我們可以用枚舉的方法，枚舉 x,y,z 的所有可能組合,最后得到問(wèn)題的解 for(int i=0;i=100;i+) for(int j=0;j=100;j+) for(int k=0;k=100;k=k+3),優(yōu)化后的枚舉算法,公雞最多買(mǎi)20只，母雞最多買(mǎi)33只，小雞最多買(mǎi)100只，于是。 for(int i=0;i=20;i+) for(int j=0;j=33;j+) for(int k=0;k=100;k=k+3),繼續(xù)優(yōu)化,一旦公雞和母雞確定了，小雞的數(shù)量也就確定了，所以不

3、用再枚舉小雞的數(shù)量 for(int i=0;i=20;i+) for(int j=0;j=33;j+) int k=100-i-j; 運(yùn)算次數(shù)從21780次減少到660次 時(shí)間性能從O(n3)提升到O(n2),小結(jié),從上面的對(duì)比可以看出，對(duì)于枚舉算法，加強(qiáng)約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。在枚舉法解題中，判定條件的確定是很重要的，如果約束條件不對(duì)或者不全面，就窮舉不出正確的結(jié)果。,三位數(shù),求所有的三位數(shù)，它除以11所得的余數(shù)等于它的三個(gè)數(shù)字的平方和。 解題思路：三位數(shù)只有900個(gè)，可用枚舉法解決，枚舉時(shí)可先估計(jì)有關(guān)量的范圍，以縮小討論范圍，減少計(jì)算量。,解法,解：設(shè)這個(gè)三位數(shù)

4、的百位、十位、個(gè)位的數(shù)字分別為x，y，z。由于任何數(shù)除以11所得余數(shù)都不大于10，所以 x2+y2+z210， 從而1x3，0y3，0z3。所求三位數(shù)必在以下數(shù)中： 100,101,102,103,110,111,112,120,121,122,130 200,201,202 ,211,212,220,221 300,301,310 不難驗(yàn)證只有100，101兩個(gè)數(shù)符合要求。,完美立方 (POJ1543),問(wèn)題描述： a3 = b3 + c3 + d3為完美立方等式。例如123 = 63 + 83 + 103 。編寫(xiě)一個(gè)程序，對(duì)任給的正整數(shù)N (N100)，尋找所有的四元組(a, b, c,

5、d)，使得a3 = b3 + c3 + d3，其中1a, b, c, d N。 輸入：正整數(shù)N (N100) 輸出：每行輸出一個(gè)完美立方，按照a的值，從小到大依次輸出。當(dāng)兩個(gè)完美立方等式中a的值相同，則依次按照b、c、d進(jìn)行非降升序排列輸出，即b值小的先輸出、然后c值小的先輸出、然后d值小的先輸出。,樣例,樣例輸入：24 樣例輸出： Cube = 6, Triple = (3,4,5) Cube = 12, Triple = (6,8,10) Cube = 18, Triple = (2,12,16) Cube = 18, Triple = (9,12,15) Cube = 19, Tripl

6、e = (3,10,18) Cube = 20, Triple = (7,14,17) Cube = 24, Triple = (12,16,20),代碼,逐一枚舉a,b,c,d #include main() int n, i,a,b,c,d , cube101; scanf(%d, ,拓展,現(xiàn)在需求改變了，需要處理多組數(shù)據(jù) 應(yīng)該如何修改程序？,模擬算法,模擬算法,什么是模擬算法 模擬法應(yīng)注意什么？ 典型例題 模擬法的局限,什么是模擬算法,模擬的定義： 模擬整個(gè)過(guò)程，通過(guò)改變數(shù)學(xué)中模型的各種參數(shù)，進(jìn)而觀(guān)察變更這些參數(shù)所引起過(guò)程狀態(tài)的變化。 通俗的理解： 所謂模擬，即將程序完整的按題目所訴的方

7、式來(lái)編寫(xiě)，最終運(yùn)行得出題目想要的答案。,模擬法應(yīng)注意什么？,這樣的題目在算法上沒(méi)有太多技巧，需要我們有較好的程序設(shè)計(jì)基本技能，熟練地使用計(jì)算機(jī)語(yǔ)言描述對(duì)象，同時(shí)需要細(xì)心和耐心。適當(dāng)?shù)倪x擇數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行模擬。編碼上要比其它好的算法長(zhǎng)。,Collatz Conjecture,考拉茲猜想，又稱(chēng)為3n1猜想、冰雹猜想、角谷猜想、哈塞猜想、烏拉姆猜想或敘拉古猜想，是指對(duì)于每一個(gè)正整數(shù)，如果它是奇數(shù)，則對(duì)它乘3再加1，如果它是偶數(shù)，則對(duì)它除以2，如此循環(huán)，最終都能夠得到1。 如n = 6，根據(jù)上述數(shù)式，得出 63105168421 。步驟中最高的數(shù)是16，共有8個(gè)步驟?，F(xiàn)在給定任意整數(shù)a和b，問(wèn)對(duì)所有a

8、n b，一共經(jīng)過(guò)多少步后才能都得到1，其中最高的數(shù)是多少。 Input 有多組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)占一行，包含兩個(gè)正整數(shù)1 a 1000000和a b a + 10。輸入以EOF結(jié)束。 Output 對(duì)每組測(cè)試數(shù)據(jù)，輸出步數(shù)和最高數(shù)，用空格隔開(kāi)。,樣例,Sample Input 6 6 11 12 23 33 Sample Output 8 16 23 52 360 9232,奇幻方,幻方是在一個(gè)n*n的矩陣中放置從1到n2的數(shù)，每個(gè)數(shù)只出現(xiàn)一次，并且在每行，每列及對(duì)角線(xiàn)的和是一樣的。,模擬過(guò)程,1、讓我們開(kāi)始在最上面的一行的中間放上1(在這個(gè)例中n=3) 你的任務(wù)是寫(xiě)一個(gè)程序去找出哪個(gè)數(shù)會(huì)被放到右下角在n幻方中，當(dāng)然，你可以使用上面的規(guī)律去構(gòu)造幻方。 2、我們假定最后一行是第一行的上一行，向右上角移動(dòng)意思是向上移一行并且向右移一列，因此2就放置到最后一行的最后一列上。 3、同樣，在最右邊的列再向右移時(shí)，我們認(rèn)為第