如何應(yīng)用枚舉算法

時(shí)間：2018-11-07 14:06:01

關(guān)鍵字：元素枚舉

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]算法描述?算法思想： ? 對(duì)所有可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。?算法特點(diǎn)： ??算法簡(jiǎn)單，但執(zhí)行效率低。因此枚舉法的關(guān)鍵在于提高編程效率

算法描述?

算法思想： ? 對(duì)所有可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。?

算法特點(diǎn)： ??算法簡(jiǎn)單，但執(zhí)行效率低。因此枚舉法的關(guān)鍵在于提高編程效率。
對(duì)于可預(yù)先確定元素的個(gè)數(shù)，并且元素所在的區(qū)間是連續(xù)的情況非常適合。
對(duì)于類似的求abcd /ef=xy的這類問(wèn)題，一般枚舉用的比較多，經(jīng)典的例子比如求水仙花數(shù)目，也是枚舉，下面是一個(gè)小學(xué)時(shí)代的百雞百錢(qián)問(wèn)題對(duì)枚舉的應(yīng)用案例，來(lái)分析對(duì)枚舉應(yīng)用過(guò)程中運(yùn)算的改進(jìn)
百雞百錢(qián) 設(shè)母雞每只5元，公雞每只3元，小雞1元3只?，F(xiàn)用100元買(mǎi)100只雞，求出所有可能的解。
設(shè)母雞x，公雞y，小雞z，滿足x+y+z=100 5*x+3*y+z/3==100這兩個(gè)關(guān)系式子
這種枚舉效率很低，3層循環(huán)，每層100次

#includeint?main()
{	int?x,y,z;
	for?(x=0;?x<=100;x++)
		for?(y=0;?y<=100;?y++)
		????for?(z=0;?z<=100;?z++)
		?	if?(?x+y+z==100?&&?5*x+3*y+z/3==100&&z%3==0?)//因?yàn)楝F(xiàn)實(shí)總z必須是3的整數(shù)倍，比如進(jìn)行判斷
				printf("%10d,%20d,%dn",x,y,z);
}

利用x，y，z之間的關(guān)系可以減少一層循環(huán)

#includeint?main()
{	int?x,y,z;
	for?(x=0;?x<=100;x++)
		for?(y=0;?y<=100;?y++)
		{	z=100-x-y;
			if?(z%3==0?&&??5*x+3*y+z/3==100)
				printf("%d,%d,%dn",x,y,z);
		}
}

根據(jù)y可能出現(xiàn)的最大值進(jìn)行限制y的范圍，上面那個(gè)y循環(huán)，從34-100之間的都是無(wú)用功，如果把y循環(huán)改成對(duì)z的循環(huán)就不好了，循環(huán)次數(shù)更多了

#includeint?main()
{	int?x,y,z;
	for?(x=0;?x<=20;x++)
		for?(y=0;?y<=33;?y++)
		{	z=100-x-y;
			if?(?z%3==0?&&?5*x+3*y+z/3==100)
				printf("%d,%d,%dn",x,y,z);
		}
}

01背包問(wèn)題有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過(guò)指定的限制重量，但選中物品的價(jià)值之和最大。例如：設(shè)限制重量為7，現(xiàn)有4件物品，它們的重量和價(jià)值見(jiàn)下表，問(wèn)如何物品的價(jià)值之和最大？

#include#define?N?100
typedef?struct?product/**結(jié)構(gòu)體用來(lái)保存物品信息*/
{
????int?weight;
????int?value;
}PRO;
PRO?pro[N];/**存儲(chǔ)物品的數(shù)組*/
int?a[N],b[N];/**a是保存的最大值物品選擇信息，b是每次的物品選擇與否的信息*/
PRO?tem,max;???/**tem保存臨時(shí)計(jì)算的物品信息，max保存最大值時(shí)的信息*/
int?zuheshu(int?n)/**根據(jù)排列組合的規(guī)則，n個(gè)物品0表示不選擇，1表示選擇，有2^n種選擇*/
{
????int?i,s=1;
????for(i=0;i<n;i++)
????{
????????s*=2;
????}
????return?s;
}
void?jisuan_1(int?num,int?n)/**根據(jù)組合數(shù)的范圍，把在組合數(shù)范圍內(nèi)的數(shù)字num，和物品選擇與否對(duì)應(yīng)起來(lái)*/
{
????int?j;
????for(j=0;j<n;j++)/**把num換成2進(jìn)制，而且二進(jìn)制的位數(shù)和商品的總數(shù)n相同*/
????{
????????b[j]=num%2;
????????num=num/2;
????}
}
void?jisuan_2(int?n,int?lim)
{
????int?i,k,t;
????for(i=0;i<zuheshu(n);i++)/**對(duì)組合范圍內(nèi)的數(shù)字進(jìn)行逐個(gè)枚舉*/
????{
????????jisuan_1(i,n);/**進(jìn)行信息對(duì)應(yīng)*/
????????tem.value=0;/**用前要先清零*/
????????tem.weight=0;/**用前要先清零*/
????????for(t=0;tmax.value)&&(tem.weight<lim))/**確定是否滿足條件，不超過(guò)限制*/
????????{
????????????max.value=tem.value;
????????????max.weight=tem.weight;
????????????for(k=0;k<n;k++)/**更新下數(shù)組a*/
????????????????a[k]=b[k];
????????}
????}
}
int?main()
{
????int?n,i,lim;
????printf("輸入數(shù)目和限制:n");
????scanf("%d",&n);
????scanf("%d",&lim);
????printf("%輸入重量和價(jià)值:n");
????for(i=0;i<n;i++)
????{
???????scanf("%d?%d",&pro[i].weight,&pro[i].value);
????}
????jisuan_2(n,lim);
????printf("輸出最大價(jià)值和重量n");
????printf("%d?%dn",max.value,max.weight);
????for(i=0;i<n;i++)
????{
????????if(a[i]==1)
????????{
????????????printf("%d?",i);//看編號(hào)范圍，從1開(kāi)始，輸出i+1就行
????????}
????}
????return?0;
}

這個(gè)題目最大的感觸就是把二進(jìn)制和枚舉聯(lián)系在一起了。棋盤(pán)問(wèn)題在4×4的棋盤(pán)上放置8個(gè)棋,要求每一行,每一列上只能放置2個(gè)。找出所有可能的解并輸出解的個(gè)數(shù)
枚舉思想1：
用二維數(shù)組a[4][4]存放所有可能的解，1表示存放，0表示不存放。

#include#include#define?N?4

int?a[N][N];
char?b[]={3,5,6,9,10,12};//0011?0101?0110?1001?1010?1100?每行必須有兩個(gè)，4行，這些就夠了，也是二進(jìn)制數(shù)的運(yùn)用
void?tc_h(int?row,int?num)//填充第i行，n為列數(shù)
{
????int?j,t;
????t=b[num];
????for(j=0;j<N;j++)
????{
????????a[row][j]=t%2;
????????t=t/2;
????}
}
int?panduan_l(int?cle)//檢查每一列是否合格，m為行總數(shù)
{
????int?i,count=0;
????for(i=0;i2)
????????????return?0;
????}
????return?count;
}
int?main()
{
????int?count=0;
????int?i,j,k,s,b,c;
????for(i=0;i<6;i++)
????{
????????tc_h(0,i);
?????????for(j=0;j<6;j++)//每行進(jìn)行填充
?????????{
?????????????tc_h(1,j);
??????????????for(k=0;k<6;k++)
??????????????{
???????????????????tc_h(2,k);
???????????????????for(s=0;s<6;s++)
???????????????????{
???????????????????????tc_h(3,s);
???????????????????????if?((panduan_l(0)&&panduan_l(1)&&panduan_l(2)&&panduan_l(3))&&(panduan_l(0)+
????????????????????????panduan_l(1)+panduan_l(2)+panduan_l(3)==8))//對(duì)于每種情況逐列判斷是否符合情況
???????????????????????{
???????????????????????????count++;
????????????????????????????for(b=0;b<N;b++)
????????????????????????????{
????????????????????????????????for(c=0;c<N;c++)
????????????????????????????????{
????????????????????????????????????printf("%d?",a[b][c]);//符合就輸出
????????????????????????????????}
????????????????????????????????printf("n");
????????????????????????????}
????????????????????????????printf("n");
???????????????????????}
???????????????????}
??????????????}
?????????}
????}
????printf("%d?",count);
????return?0;
}

另一種方法

#include#include#define?N?4
int?a[N][N];/**這里用的方法是一次填充完16個(gè)，然后在判斷是否滿足條件*/
int?one(int?num)
{
????int?i,count=0;
????for(i=0;i<16;i++)
????{
???????count+=num%2;
???????num=num/2;
????}
????return?count;
}
int?panduan(int?(*a)[N])
{
????int?i,j,count=0;
????int?count2=0;
????for(i=0;i<N;i++)
????{
????????count=0;
????????count2=0;
????????for(j=0;j2||count2>2)
????????return?0;
????}
????return?1;
}
int?main()
{
????int?i,j,k,t,num,*p,count=0;

????for(num=0;num<65535;num++)
????{
????????if(one(num)==8)//判斷下，減少次數(shù)
????????{
????????????t=num;
????????????p=a;
????????????for(j=0;j<16;j++)
????????????{
????????????????*p++=t%2;
?????????????????t=t/2;
????????????}
????????????if(panduan(a)==1)
????????????{
????????????????count++;
????????????????for(i=0;i<N;i++)
????????????????{
????????????????????for(k=0;k<N;k++)
????????????????????{
????????????????????????printf("%d?",a[i][k]);
????????????????????}
?????????????????????printf("n");
????????????????}
????????????????printf("n");
????????????}
????????}
????}
????printf("%d?",count);
}

互不相同的平方數(shù) 求個(gè)數(shù)
給定的正整數(shù)，再給定一個(gè)條件：一個(gè)數(shù)的平方數(shù)為1個(gè)9位數(shù)，并且其各數(shù)互不相同。統(tǒng)計(jì)出小于等于X的整數(shù)中滿足此條件的數(shù)的個(gè)數(shù) Input 每一行為一個(gè)數(shù)字，為5位正整數(shù)x Output 對(duì)應(yīng)每個(gè)數(shù)字輸出滿足條件的個(gè)數(shù) Sample Input 10000 Sample Output 0

#includeint?panduan(int?num)
{
????int?i;
????int?date[10]={0};
????for(i=0;i<10;i++)//取9位數(shù)的每一位
????{
????????date[num%10]++;
????????num=num/10;
????}
????for(i=0;i1)//9位數(shù)，沒(méi)有重復(fù)的情況下不會(huì)大于1，不能用date[i]！=1判斷，因?yàn)?-9十個(gè)數(shù)字，有可能為0
????????????return?0;
????}
????return?1;
}
int?main()
{
????int?num;//不會(huì)溢出
????int?num2;
????int?i,j,k;
????while(scanf("%d",&num)!=EOF)
????{
????????num=num>33000?33000:num;//不會(huì)超過(guò)33000，否則就不是9位數(shù)據(jù)了
????????for(i=10000;i<num;i++)
????????{
????????????num2=i*i;
????????????if(panduan(num2)==1)
????????????{
????????????????printf("%d*%d=%dn",i,i,num2);
????????????}

????????}
????????printf("END");

????}

????return?0;
}