C語言枚舉法課件

ACM程序設(shè)計福州大學(xué)至誠學(xué)院馮新第三講枚舉枚舉法概念枚舉法，常常稱之為窮舉法，是指從可能的集合中一一枚舉各個元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。枚舉算法基本思路采用枚舉算法解題的基本思路：（1）

確定枚舉對象、枚舉范圍和判定條件；（2）

一一枚舉可能的解，驗證是否是問題的解問題描述求x2+y2=2000的正整數(shù)解這道題明顯是一道枚舉題，需要枚舉出所有的可能的解。解題方案1：大家可以很自然的算出45*45>2000，于是我們的問題就被簡化了。一個簡單的代碼就能解出題目。for(i=0;i<45;i++)for(j=0;j<45;j++) if(i*i+j*j==2000) ...上面的方法可以優(yōu)化嗎？解題方案2如果我們x=44,y=9。那么我們還需要枚舉接下來的y嗎？？？于是我們就有了第二種方案：#include<stdio.h>intmain(){inti,j;for(i=0;i<45;i++){for(j=0;j<45;j++){ if(i*i+j*j==2000) printf("2000=%d*%d+%d+%d\n",i,i,j,j); if(i*i+j*j>=2000) break;}}return0;}還可以優(yōu)化嗎？解題方案3：#include<stdio.h>intmain(){inti,j;for(i=0;i<45;i++){for(j=i;j<45;j++){ if(i*i+j*j==2000) printf("2000=%d*%d+%d+%d\n",i,i,j,j); if(i*i+j*j>=2000) break;}}return0;}還可以進一步的優(yōu)化嗎？？？大家回去也可以好好思考下?？梢酝ㄟ^上面的例子看到，雖然都是枚舉法，但是運行效率還是會有很大的差距的。第一個方案我們至少需要做45*45次操作而第三種方案明顯比第一個方案少很多次操作。ZOJ1722switchThereareNlightsinaline.Giventhestates(on/off)ofthelights,yourtaskistodetermineatleasthowmanylightsshouldbeswitched(fromontooff,orfromofftoon),inordertomakethelightsonandoffalternatively.有N盞燈，排成一排。給定每盞燈的初始狀態(tài)（開或關(guān)），你的任務(wù)是計算至少要切換多少 盞燈的狀態(tài)（將開著的燈關(guān)掉，或?qū)㈥P(guān)掉的燈開起來），才能使得這N盞燈開和關(guān)交替出現(xiàn)。Input

Onelineforeachtestcase.

TheintegerN(1<=N<=10000)comesfirstandisfollowedbyNintegersrepresentingthestatesofthelights("1"foronand"0"foroff).

Processtotheend-of-file.輸入文件中包含多個測試數(shù)據(jù)，每個測試數(shù)據(jù)占一行。首先是一個整數(shù)N，1≤N≤10000，然后是N個整數(shù)，表示這N盞燈的初始狀態(tài)，1表示開著的，O表示關(guān)著的。測試數(shù)據(jù)一直到文件尾。Output

Foreachtestcaseoutputalineconsistsofonlytheleasttimesofswitches.對每個測試數(shù)據(jù)，輸出占一行，表示至少需要切換狀態(tài)的燈的數(shù)目。SampleInput

91001110103101SampleOutput

3

0解題方案1：第一種枚舉思路。N盞燈，每盞燈都有兩種狀態(tài)：1和0，則N盞燈共有2N種狀態(tài)，從000…0到111…1?？梢悦杜e這2^N種狀態(tài)，每種狀態(tài)都判斷一下是否是開和關(guān)交替出現(xiàn)，如果是，則還要統(tǒng)計從初始狀態(tài)轉(zhuǎn)換到該狀態(tài)需要切換的燈的數(shù)目。但這種枚舉策略勢必要花費很多時間，因為N最大可以取到10000，而2^10000的數(shù)量級是10^3010。我們的OJ時間限制為1s，即我們最多只能是10^7次操作。（一般OJ1S能進行2*10^7次操作）解題方案2：第二種思路。要使得N盞燈開和關(guān)交替出現(xiàn)，實際上只有兩種可能：奇數(shù)位置上的燈是開著的，或者偶數(shù)位置上的燈是開著的。只要分別計算從N盞燈的初始狀態(tài)出發(fā)，切換到這兩種狀態(tài)所需要切換燈的數(shù)目，取較小者即可。例如樣例輸入中的第1個測試數(shù)據(jù)對應(yīng)的初始狀態(tài)如圖所示，將這9盞燈切換到奇數(shù)位置上的燈是開著的，需要切換6盞燈；切換到偶數(shù)位置上的燈是開著的，需要切換3盞燈；因此至少需要切換3盞燈。intres1=0,res2=0;for(i=1;i<=N;i++)//計算第1位為1，需要調(diào)整的數(shù)目{ if(i%2==1&&a[i]==0) //奇數(shù)位為0，需要調(diào)整 res1++; if(i%2==0&&a[i]==1) //偶數(shù)位為1，需要調(diào)整 res1++;}for(i=1;i<=N;i++)//計算第1位為0，需要調(diào)整的數(shù)目{ if(i%2==1&&a[i]==1)//奇數(shù)位為1，需要調(diào)整 res2++; if(i%2==0&&a[i]==0) //偶數(shù)位為0，需要調(diào)整 res2++;}res=min(res1,res2);//答案就是兩個中較小的一個可以優(yōu)化嗎？？？大家發(fā)現(xiàn)沒有？？res1+res2肯定會等于燈的總數(shù)n。（原因大家自己想想）那么我們代碼可以優(yōu)化成：intres1=0; //計算第1位為1，需要調(diào)整的數(shù)目for(i=1;i<=N;i++)

{ //奇數(shù)位為0，需要調(diào)整 if(i%2==1&&a[i]==0) res1++; //偶數(shù)位為1，需要調(diào)整 if(i%2==0&&a[i]==1) res1++;}intresult=min(res1,n-res1);省了一半的操作?。?！PKU1316SelfNumbers1949年，印度數(shù)學(xué)家D．R．Kaprekar發(fā)現(xiàn)了一類叫做自我數(shù)(selfnumber)的數(shù)。對于任一正整數(shù)a，定義d(n)為n加上n的每一位數(shù)字得到的總和。 例如，d(75)=75+7+5=87。 取任意正整數(shù)n作為出發(fā)點，你可以建立一個無窮的正整數(shù)序列n,d(n),d(d(n))…… 例如，如果你從33開始，下一個數(shù)字就是33+3+3=39，再下一個是39+3+9=51，再下一個是51+5+1=57，…。如此便產(chǎn)生一個整數(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ù)字有多于一個生成器，如101有兩個生成器，91和100。而一個沒有生成器的數(shù)字則稱作自我數(shù)(selfnumber)。100以內(nèi)的自我數(shù)共有13個：1，3，5，7，9，20，31，42,53，64，75，86和97。輸入描述：此題無輸入。輸出描述：輸出所有小于或等于1000000的正的自我數(shù)，以升序排列，并且每個數(shù)占一行。SampleOutput1357。。。<--這里有很多自我數(shù)

9960997199829993解題思路最簡單的方法，把1到1000000所有的數(shù)的產(chǎn)生的d(n),都算出來，所有沒被算出來的數(shù)就是我們所需要的答案了。intb[1000001];for(i=1;i<=1000000;i++){ x=i,temp=i; while(temp!=0){ x+=temp%10; temp/=10; } if(x<=1000000) b[x]=1; }小技巧：很多編譯器的主函數(shù)里面是不支持開大數(shù)組。我們可以通過定義全局變量來解決這個問題?？梢詢?yōu)化嗎？？？intb[1000001];for(i=1;i<=1000000;i++){ x=i,temp=i; while(temp!=0){ x+=temp%10;if(x>1000000)break; temp/=10; } if(x<=1000000) b[x]=1; }優(yōu)化用枚舉法解題的最大的缺點是運算量比較大，解題效率不高，如果枚舉范圍太大（一般以不超過兩百萬次為限），