如何應用枚舉算法

時間：2018-11-07 14:06:01

關鍵字：元素枚舉

手機看文章

掃描二維碼
隨時隨地手機看文章

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

算法描述?

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

算法特點： ??算法簡單，但執(zhí)行效率低。因此枚舉法的關鍵在于提高編程效率。
對于可預先確定元素的個數(shù)，并且元素所在的區(qū)間是連續(xù)的情況非常適合。
對于類似的求abcd /ef=xy的這類問題，一般枚舉用的比較多，經典的例子比如求水仙花數(shù)目，也是枚舉，下面是一個小學時代的百雞百錢問題對枚舉的應用案例，來分析對枚舉應用過程中運算的改進
百雞百錢設母雞每只5元，公雞每只3元，小雞1元3只。現(xiàn)用100元買100只雞，求出所有可能的解。
設母雞x，公雞y，小雞z，滿足x+y+z=100 5*x+3*y+z/3==100這兩個關系式子
這種枚舉效率很低，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?)//因為現(xiàn)實總z必須是3的整數(shù)倍，比如進行判斷
				printf("%10d,%20d,%dn",x,y,z);
}

利用x，y，z之間的關系可以減少一層循環(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)的最大值進行限制y的范圍，上面那個y循環(huán)，從34-100之間的都是無用功，如果把y循環(huán)改成對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背包問題有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。例如：設限制重量為7，現(xiàn)有4件物品，它們的重量和價值見下表，問如何物品的價值之和最大？

#include#define?N?100
typedef?struct?product/**結構體用來保存物品信息*/
{
????int?weight;
????int?value;
}PRO;
PRO?pro[N];/**存儲物品的數(shù)組*/
int?a[N],b[N];/**a是保存的最大值物品選擇信息，b是每次的物品選擇與否的信息*/
PRO?tem,max;???/**tem保存臨時計算的物品信息，max保存最大值時的信息*/
int?zuheshu(int?n)/**根據(jù)排列組合的規(guī)則，n個物品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ù)范圍內的數(shù)字num，和物品選擇與否對應起來*/
{
????int?j;
????for(j=0;j<n;j++)/**把num換成2進制，而且二進制的位數(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++)/**對組合范圍內的數(shù)字進行逐個枚舉*/
????{
????????jisuan_1(i,n);/**進行信息對應*/
????????tem.value=0;/**用前要先清零*/
????????tem.weight=0;/**用前要先清零*/
????????for(t=0;tmax.value)&&(tem.weight<lim))/**確定是否滿足條件，不超過限制*/
????????{
????????????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("%輸入重量和價值:n");
????for(i=0;i<n;i++)
????{
???????scanf("%d?%d",&pro[i].weight,&pro[i].value);
????}
????jisuan_2(n,lim);
????printf("輸出最大價值和重量n");
????printf("%d?%dn",max.value,max.weight);
????for(i=0;i<n;i++)
????{
????????if(a[i]==1)
????????{
????????????printf("%d?",i);//看編號范圍，從1開始，輸出i+1就行
????????}
????}
????return?0;
}

這個題目最大的感觸就是把二進制和枚舉聯(lián)系在一起了。棋盤問題在4×4的棋盤上放置8個棋,要求每一行,每一列上只能放置2個。找出所有可能的解并輸出解的個數(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?每行必須有兩個，4行，這些就夠了，也是二進制數(shù)的運用
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++)//每行進行填充
?????????{
?????????????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))//對于每種情況逐列判斷是否符合情況
???????????????????????{
???????????????????????????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個，然后在判斷是否滿足條件*/
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ù) 求個數(shù)
給定的正整數(shù)，再給定一個條件：一個數(shù)的平方數(shù)為1個9位數(shù)，并且其各數(shù)互不相同。統(tǒng)計出小于等于X的整數(shù)中滿足此條件的數(shù)的個數(shù) Input 每一行為一個數(shù)字，為5位正整數(shù)x Output 對應每個數(shù)字輸出滿足條件的個數(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ù)，沒有重復的情況下不會大于1，不能用date[i]！=1判斷，因為0-9十個數(shù)字，有可能為0
????????????return?0;
????}
????return?1;
}
int?main()
{
????int?num;//不會溢出
????int?num2;
????int?i,j,k;
????while(scanf("%d",&num)!=EOF)
????{
????????num=num>33000?33000:num;//不會超過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;
}