枚举法(暴力破解)

本文共有3474个字,关键词:枚举法爆破

     枚举算法(穷举法),就是按照问题本身的性质,一一列举出该问题所有可能的解,并在列举的过程中, 逐一检验 每个解是否就是真正的解。 若是,则采纳这个解;否则抛弃它。
注意:
    · 不能遗漏,否则可能导致结果不正确(边界与特殊值检查、容易挖坑)

    · 不能重复 ,否则可能导致效率比较低 (优化的意义)

 特点: 1.枚举的解准确而全面
           2.实现简单 (通过循环/递归实现)
           3.执行效率提升空间往往比较大


枚举三步:  
         1.确定枚对象 枚举对象可以理解为问题解的表达形式,一般需要用若干个参数(p1,p2,...pk)来描述
     · 参数之间要 相互独立 ,而且,参数的数目越少(求解变量的数目越少)、问题解的搜索空间的维度也相应地小。
    ·每个参数 取值范围 越小,问题解的搜索空间也越小(尽可能的减小范围)

         2.逐一列举可能解 根据枚举对象的参数构造循环,一一列举其表达式的每一种取值情况。

         3.逐一验证可能解 根据问题解的要求,一一验证枚举对象表达式的每一个取值,如果满足条件,则采纳它,否则,抛弃之。

--

例1:模糊数字问题

(原始)1.  一个5位数、百位数看不清(百位模糊)知道是一个57和67的倍数、输出所有满足这些条件的五位数,并统计这样数的个数。

    输入: 每一行对应一个测试样例,每一行包含四个数字,依此是万位数,千位数,十位数和个位数。  最后一行包含四个 -1 ,表示输入结束。
    输出:每组测试样例的结果输出占一行,第一个数字表示满足条件的编码的个数,后面按照升序输出所有满足条件的编码,数字与数字间用空格隔开。

解:    记百位为h、百位数字可能是0~9,逐一例举 即 for(h=0;h<=9;h++);
    逐一验证 即 if(((19095+100*h)%57 )== 0 && (19h95%67 == 0))
    

(进阶)2.    一个5位数、万位和百位数看不清(万位、百位模糊)知道是一个57和67的倍数、输出所有满足这些条件的五位数,并统计这样数的个数。

输入: 每一行对应一个测试样例,每一行包含四个数字,依此是万位数,千位数,十位数和个位数。  最后一行包含3个 -1 ,表示输入结束。
    输出:每组测试样例的结果输出占一行,第一个数字表示满足条件的编码的个数,后面按照升序输出所有满足条件的编码,数字与数字间用空格隔开。

解:    百位为h、万位为m, 百位0~9、万位1~9;(双层for循环)(经试验:)
    逐一验证....if()

(再改)3.  一个5位数、末尾是95、万位百位和百位数看不清(万位、百位、千位模糊)知道是一个57和67的倍数、输出所有满足这些条件的五位数,并统计这样数的个数。

解:    万位、千位、百位分别为 d1,d2,d3;  逐一列举(三层for)
    for(d1=1;d1<10;d1++)   //万位1~9
      for(d2=0;d2<10;d2++)
        for(d3=0;d3<10;d3++)
    逐一验证   d110000+d21000+d3*100+95 能否整除 56 & 57 。

方法2(优化) :  前三位数字记为 d ,d=100~999;
    逐一列举  for(d=100;d<=999;d++);
    逐一验证  d*100 + 95 能否整除 56 & 57

代码实现(类似模板方式):

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int d1,d2,d4,d5,h,myValue=0;
    int myCount=0;
    int  allResult[10];  //最多有10个,节约空间 
    scanf("%d%d%d%d",&d5,&d4,&d2,&d1);
         while(d5!=-1){
             myCount=0;
             for(h=0;h<10;h++){   //枚举 
                 myValue = d5*10000+d4*1000+d2*10+d1+h*100;
                 if((myValue%57==0)&&(myValue%67==0))  //验证
                  {
                      allResult[myCount] = myValue;
                      cout<<myValue;
                      myCount++;   //这种位置顺序会导致多一位 
                  }
             }
             cout<<myCount<<endl;  //个数(有几种)
             for(int i=0;i<myCount;i++){   //因为16行,所以是 < myCount而不是 <=  
             cout<<allResult[i]; }  //

             printf("\r\n");   // \r是制表符,enter上方是\ 
             cin>>d5>>d4>>d2>>d1; //务必和第一次输入顺序一样 
    }
    return 0;
}

优化(整理)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int d1,d2,d4,d5,h,myValue=0;
    int myCount=0;
    int  allResult[10];  //最多有10个,节约空间 
//    scanf("%d%d%d%d",&d5,&d4,&d2,&d1);
         while(scanf("%d%d%d%d",&d5,&d4,&d2,&d1) && (d5!=-1)){
             myCount=0;
             for(h=0;h<10;h=h+1){   //枚举 
                 myValue = d5*10000+d4*1000+d2*10+d1+h*100;
                 if((myValue%57==0)&&(myValue%67==0))  //验证
                  {
                      allResult[myCount] = myValue;
            //          cout<<myValue;
                    
            //        cout<<myCount;
                      myCount++;   //这种位置顺序会导致多一位 
                  }
            //      cout<<h;
            
             }
             cout<<myCount<<endl;
             for(int i=0;i<myCount;i++){   //因为16行,所以是 < myCount而不是 <=  
             cout<<allResult[i]; }

             printf("\r\n");   // \r是制表符,enter上方是\ 
//          scanf("%d%d%d%d",&d5,&d4,&d2,&d1); //务必和第一次输入顺序一样 
    }
    return 0;
}
版权声明:本文为作者原创,如需转载须联系作者本人同意,未经作者本人同意还请不要擅自转载。
添加新评论
暂无评论
Title - Artist
0:00