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

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

2、,y,z 為正整數(shù),由于雞的總數(shù)是 100,可以確定x,y,z 的取值范圍:0=x,y,z=100,對于這個問題我們可以用枚舉的方法，枚舉 x,y,z 的所有可能組合,最后得到問題的解 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)化后的枚舉算法,公雞最多買20只，母雞最多買33只，小雞最多買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; 運算次數(shù)從21780次減少到660次 時間性能從O(n3)提升到O(n2),小結,從上面的對比可以看出，對于枚舉算法，加強約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。在枚舉法解題中，判定條件的確定是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結果。,三位數(shù),求所有的三位數(shù)，它除以11所得的余數(shù)等于它的三個數(shù)字的平方和。 解題思路：三位數(shù)只有900個，可用枚舉法解決，枚舉時可先估計有關量的范圍，以縮小討論范圍，減少計算量。,解法,解：設這個三位數(shù)

4、的百位、十位、個位的數(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 不難驗證只有100，101兩個數(shù)符合要求。,完美立方 (POJ1543),問題描述： a3 = b3 + c3 + d3為完美立方等式。例如123 = 63 + 83 + 103 。編寫一個程序，對任給的正整數(shù)N (N100)，尋找所有的四元組(a, b, c,

5、d)，使得a3 = b3 + c3 + d3，其中1a, b, c, d N。 輸入：正整數(shù)N (N100) 輸出：每行輸出一個完美立方，按照a的值，從小到大依次輸出。當兩個完美立方等式中a的值相同，則依次按照b、c、d進行非降升序排列輸出，即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ù) 應該如何修改程序？,模擬算法,模擬算法,什么是模擬算法 模擬法應注意什么？ 典型例題 模擬法的局限,什么是模擬算法,模擬的定義： 模擬整個過程，通過改變數(shù)學中模型的各種參數(shù)，進而觀察變更這些參數(shù)所引起過程狀態(tài)的變化。 通俗的理解： 所謂模擬，即將程序完整的按題目所訴的方

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

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