《C語(yǔ)言枚舉法》ppt課件

1、ACM程序設(shè)計(jì)程序設(shè)計(jì)福州大學(xué)至誠(chéng)學(xué)院 馮新第三講第三講枚舉枚舉枚舉法概念n枚舉法，經(jīng)常稱之為窮舉法，是指從能夠的集合中一一枚舉各個(gè)元素，用標(biāo)題給定的約束條件斷定哪些是無(wú)用的，哪些是有用的。能使命題成立者，即為問題的解。枚舉算法根本思緒n采用枚舉算法解題的根本思緒：n1 確定枚舉對(duì)象、枚舉范圍和斷定條件；n2 一一枚舉能夠的解，驗(yàn)證能否是問題的解問題描畫求x2+y2=2000的正整數(shù)解這道題明顯是一道枚舉題，需求枚舉出一切的能夠的解。解題方案1：大家可以很自然的算出45*452000，于是我們的問題就被簡(jiǎn)化了。一個(gè)簡(jiǎn)單的代碼就能解出標(biāo)題。for(i = 0; i 45; i+) for(j =

2、 0; j 45; j+) if(i*i + j*j = 2000) .上面的方法可以優(yōu)化嗎？上面的方法可以優(yōu)化嗎？解題方案2n假設(shè)我們x = 44, y = 9。那么我們還需求枚舉接下來的 y 嗎？n于是我們就有了第二種方案：#includeint main() int i,j; for(i = 0; i 45; i+) for(j = 0; j = 2000) break; return 0;還可以優(yōu)化嗎？還可以優(yōu)化嗎？解題方案3：#includeint main() int i,j; for(i = 0; i 45; i+) for(j = i; j = 2000) break; ret

3、urn 0;n還可以進(jìn)一步的優(yōu)化嗎？n大家回去也可以好好思索下。n可以經(jīng)過上面的例子看到，雖然都是枚舉法，但是運(yùn)轉(zhuǎn)效率還是會(huì)有很大的差距的。n第一個(gè)方案 我們至少需求做 45*45次操作n而第三種方案明顯比第一個(gè)方案少很多次操作。ZOJ 1722 switchnThere are N lights in a line. Given the states (on/off) of the lights, your task is to determine at least how many lights should be switched (from on to off, or from off

4、 to on), in order to make the lights on and off alternatively. n 有N盞燈，排成一排。給定每盞燈的初始形狀開或關(guān)，他的義務(wù)是計(jì)算至少要切換多少n盞燈的形狀將開著的燈關(guān)掉，或?qū)㈥P(guān)掉的燈開起來，才干使得這N盞燈開和關(guān)交替出現(xiàn)。nInputOne line for each testcase.The integer N (1 = N = 10000) comes first and is followed by N integers representing the states of the lights (1 for on and

5、0 for off).Process to the end-of-file.n 輸入文件中包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)輸入文件中包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)占一行。首先是一個(gè)整數(shù)據(jù)占一行。首先是一個(gè)整數(shù)N，1N10000，然后是，然后是N個(gè)整數(shù)，表示這個(gè)整數(shù)，表示這N盞燈的初始形狀，盞燈的初始形狀，1表示開著的，表示開著的，O表示關(guān)表示關(guān)著的。測(cè)試數(shù)據(jù)不斷到文件尾。著的。測(cè)試數(shù)據(jù)不斷到文件尾。nOutputFor each testcase output a line consists of only the least times of switches.n對(duì)每個(gè)測(cè)試數(shù)據(jù)，輸出占一行，表示

6、至少需求切換形對(duì)每個(gè)測(cè)試數(shù)據(jù)，輸出占一行，表示至少需求切換形狀的燈的數(shù)目。狀的燈的數(shù)目。nSample Input9 1 0 0 1 1 1 0 1 0n3 1 0 1nSample Output30解題方案1：n 第一種枚舉思緒。N盞燈，每盞燈都有兩種形狀：1和0，那么N盞燈共有2N種形狀，從00 00到1 1 11。可以枚舉這2N種形狀，每種形狀都判別一下能否是開和關(guān)交替出現(xiàn)，假設(shè)是，那么還要統(tǒng)計(jì)從初始形狀轉(zhuǎn)換到該形狀需求切換的燈的數(shù)目。n但這種枚舉戰(zhàn)略勢(shì)必要破費(fèi)很多時(shí)間，由于N最大可以取到10000，而210000的數(shù)量級(jí)是103010。n我們的OJ時(shí)間限制為1s，即我們最多只能是107

7、次操作。n普通OJ 1S 能進(jìn)展2*107次操作解題方案2：n 第二種思緒。要使得N盞燈開和關(guān)交替出現(xiàn)，實(shí)踐上只需兩種能夠：奇數(shù)位置上的燈是開著的，或者偶數(shù)位置上的燈是開著的。只需分別計(jì)算從N盞燈的初始形狀出發(fā)，切換到這兩種形狀所需求切換燈的數(shù)目，取較小者即可。例如樣例輸入中的第1個(gè)測(cè)試數(shù)據(jù)對(duì)應(yīng)的初始形狀如下圖，將這9盞燈切換到奇數(shù)位置上的燈是開著的，需求切換6盞燈；切換到偶數(shù)位置上的燈是開著的，需求切換3盞燈；因此至少需求切換3盞燈。int res1 = 0, res2 = 0;for(i = 1; i = N; i+) /計(jì)算第1位為1，需求調(diào)整的數(shù)目if(i%2 = 1 & ai

8、 = 0) /奇數(shù)位為0，需求調(diào)整res1+;if(i%2 = 0 & ai = 1) /偶數(shù)位為1，需求調(diào)整res1+;for(i = 1; i = N; i+) /計(jì)算第1位為0，需求調(diào)整的數(shù)目if(i%2 = 1 & ai = 1) /奇數(shù)位為1，需求調(diào)整res2+;if(i%2 = 0 & ai = 0) /偶數(shù)位為0，需求調(diào)整res2+;res = min(res1, res2); /答案就是兩個(gè)中較小的一個(gè)可以優(yōu)化嗎？可以優(yōu)化嗎？n大家發(fā)現(xiàn)沒有？nres1 + res2 一定會(huì)等于燈的總數(shù) n。緣由大家本人想想n那么我們代碼可以優(yōu)化成： int res1 =

9、 0;/計(jì)算第1位為1，需求調(diào)整的數(shù)目 for(i = 1; i = N; i+) /奇數(shù)位為0，需求調(diào)整if(i%2 = 1 & ai = 0)res1+;/偶數(shù)位為1，需求調(diào)整if(i%2 = 0 & ai = 1) res1+; int result = min(res1, n-res1); 省了一半的操作！PKU 1316 Self Numbers 1949年，印度數(shù)學(xué)家DRKaprekar發(fā)現(xiàn)了一類叫做自我數(shù)(self number)的數(shù)。對(duì)于任一正整數(shù)a，定義d(n)為 n 加上 n 的每一位數(shù)字得到的總和。例如，d(75) =75+7+5=87。取恣意正整數(shù)n作為

10、出發(fā)點(diǎn)，他可以建立一個(gè)無(wú)窮的正整數(shù)序列 n, d(n), d(d(n) 例如，假設(shè)他從33開場(chǎng)，下一個(gè)數(shù)字就是33+3+3=39，再下一個(gè)是39+3+9=51，再下一個(gè)是51+5+1=57，。如此便產(chǎn)生一個(gè)整數(shù)數(shù)列： 33, 39, 51, 57, 69, 84, 96 ,111, 114 ,120 ,123, 129, 141,數(shù)字n被叫做整數(shù)d(n)的生成器。在如上的數(shù)列中，33是39的生成器，39是51的生成器，51是57的生成器，等等。有些數(shù)字有多于一個(gè)生成器，如101有兩個(gè)生成器，91和100。而一個(gè)沒有生成器的數(shù)字那么稱作自我數(shù)(self number)。100以內(nèi)的自我數(shù)共有13

11、個(gè)：1，3，5，7，9，20，31，42, 53，64，75，86和97。 輸入描畫：輸入描畫： 此題無(wú)輸入。此題無(wú)輸入。 輸出描畫：輸出描畫： 輸出一切小于或等于輸出一切小于或等于1000000的正的自我數(shù)，以升序陳的正的自我數(shù)，以升序陳列，并且每個(gè)數(shù)占一行。列，并且每個(gè)數(shù)占一行。Sample Output1 357。 - 這里有很多自我數(shù)這里有很多自我數(shù) 99609971 9982 9993 解題思緒n最簡(jiǎn)單的方法，把1到1000000一切的數(shù)的產(chǎn)生的d(n),都算出來，一切沒被算出來的數(shù)就是我們所需求的答案了。int b1000001;for(i = 1; i = 1000000; i+)x = i, temp = i;while(temp != 0) x += temp%10;temp /= 10;if(x = 1000000)bx =1;小技巧：很多編譯器的主函數(shù)里面是不支持開大數(shù)組。我們可以經(jīng)過定義全局變量來處理這個(gè)問題?？梢詢?yōu)化嗎？可以優(yōu)化嗎？int b1000001;for(i = 1; i 1000000) break;temp /= 10;if(x = 1000000)bx =1;優(yōu)化優(yōu)化n用枚舉法解題的最大的缺陷是運(yùn)算量比較大，解題效率不高，假設(shè)枚舉范圍太大普通以不超越兩百萬(wàn)次為限，在時(shí)間上就難以接受。但枚舉算法的思緒簡(jiǎn)單，程序編寫和調(diào)試方便