枚举 元素

如何应用枚举算法

2018-11-07
38次浏览
算法描述 算法思想:   对所有可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。 算法特点:   算法简单,但执行效率低。因此枚举法的关键在于提高编程效率。
对于可预先确定元素的个数,并且元素所在的区间是连续的情况非常适合。
对于类似的求abcd /ef=xy的这类问题,一般枚举用的比较多,经典的例子比如求水仙花数目,也是枚举,下面是一个小学时代的百鸡百钱问题对枚举的应用案例,来分析对枚举应用过程中运算的改进
百鸡百钱 设母鸡每只5元,公鸡每只3元,小鸡1元3只。现用100元买100只鸡,求出所有可能的解。
设母鸡x,公鸡y,小鸡z,满足x+y+z=100 5*x+3*y+z/3==100这两个关系式子
这种枚举效率很低,3层循环,每层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 )//因为现实总z必须是3的整数倍,比如进行判断 printf("%10d,%20d,%d\n",x,y,z); }利用x,y,z之间的关系可以减少一层循环#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,%d\n",x,y,z); } }根据y可能出现的最大值进行限制y的范围,上面那个y循环,从34-100之间的都是无用功,如果把y循环改成对z的循环就不好了,循环次数更多了#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,%d\n",x,y,z); } }01背包问题 有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。例如:设限制重量为7,现有4件物品,它们的重量和价值见下表,问如何物品的价值之和最大?
#include#define N 100 typedef struct product/**结构体用来保存物品信息*/ {     int weight;     int value; }PRO; PRO pro[N];/**存储物品的数组*/ int a[N],b[N];/**a是保存的最大值物品选择信息,b是每次的物品选择与否的信息*/ PRO tem,max;   /**tem保存临时计算的物品信息,max保存最大值时的信息*/ int zuheshu(int n)/**根据排列组合的规则,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)/**根据组合数的范围,把在组合数范围内的数字num,和物品选择与否对应起来*/ {     int j;     for(j=0;j<n;j++)/**把num换成2进制,而且二进制的位数和商品的总数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++)/**对组合范围内的数字进行逐个枚举*/     {         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++)/**更新下数组a*/                 a[k]=b[k];         }     } } int main() {     int n,i,lim;     printf("输入数目和限制:\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 %d\n",max.value,max.weight);     for(i=0;i<n;i++)     {         if(a[i]==1)         {             printf("%d ",i);//看编号范围,从1开始,输出i+1就行         }     }     return 0; }这个题目最大的感触就是把二进制和枚举联系在一起了。 棋盘问题 在4×4的棋盘上放置8个棋,要求每一行,每一列上只能放置2个。找出所有可能的解并输出解的个数
枚举思想1:
用二维数组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行,这些就够了,也是二进制数的运用 void tc_h(int row,int num)//填充第i行,n为列数 {     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为行总数 {     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)//判断下,减少次数         {             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); }
互不相同的平方数 求个数
给定的正整数,再给定一个条件:一个数的平方数为1个9位数,并且其各数互不相同。 统计出小于等于X的整数中满足此条件的数的个数 Input 每一行为一个数字,为5位正整数x Output 对应每个数字输出满足条件的个数 Sample Input 10000 Sample Output 0
#includeint panduan(int num) {     int i;     int date[10]={0};     for(i=0;i<10;i++)//取9位数的每一位     {         date[num%10]++;         num=num/10;     }     for(i=0;i1)//9位数,没有重复的情况下不会大于1,不能用date[i]!=1判断,因为0-9十个数字,有可能为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位数据了         for(i=10000;i<num;i++)         {             num2=i*i;             if(panduan(num2)==1)             {                 printf("%d*%d=%d\n",i,i,num2);             }         }         printf("END");     }     return 0; }

我要点评