暴力求解法(一)—简单枚举

本文主要是介绍暴力求解法(一)—简单枚举，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

  内容提要:简单枚举包括了枚举整数，枚举连续子序列，枚举分数。

  枚举整数:1.核心思想：有些题目没必要枚举所有的变量，而是枚举其一变量，后通过等式得出另一个变量，然后在判断另一个量是否在范围内即可。

                 2.典型例题：洛谷  P uva 725 Division

                 3.AC代码展示:

#include<bits/stdc++.h>
using namespace std;
int book[10];
int n;
int main(){
    int sum=0;
    while(scanf("%d",&n),n!=0){
        sum++;
        if(sum>1){
            cout<<endl;
        }
        int a,b,flag=0;   //flag为标记变量
        for(int i=n;i<100000;i++){
            if(i%n==0){    //判断另一个数是否是整数  若是整数则接着进行
                a=i,b=i/n;
                int flag1=0;
                memset(book,0,sizeof(book));  //book数组用来判断是否是全排列
                vector<int>up,down;
                while(a){   //将各个数全部存入动态数组中去
                    up.push_back(a%10);
                    book[a%10]=1;
                    a=a/10;
                }
                while(b){   
                    down.push_back(b%10);
                    book[b%10]=1;
                    b=b/10;
                }
                while(up.size()<5){
                    up.push_back(0);
                    book[0]=1;
                }
                while(down.size()<5){   //补零
                    down.push_back(0);
                    book[0]=1;
                }
                for(int i=0;i<=9;i++){  //如果不是全排列
                    if(book[i]==0){
                        flag1=1;   //标记变量
                        break;
                    }
                }
                if(flag1==0){
                    for(int i=4;i>=0;i--){
                        cout<<up[i];
                    }
                    cout<<" / ";
                    for(int i=4;i>=0;i--){
                        cout<<down[i];
                    }
                    cout<<" = "<<n;
                    cout<<endl;
                    flag=1;
                }
            }
        }
        if(flag==0){
            cout<<"There are no solutions for "<<n<<'.'<<endl;
        }
    }
}

  枚举连续子序列;1.核心思想:枚举连续子序列就是枚举开头和结尾，故用两个for循环即可，但是一定要注意开头要在结尾前面，也不要忘了子序列长度为一的时候。

                            2.典型例题：洛谷 P uva 11059 Maximum product

                            3.AC代码展示:

#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
int main(){
    int flag=0;
    while(scanf("%d",&n)!=EOF){
        flag++;
        vector<ll>s;
        for(int i=0;i<n;i++){
            int a;
            cin>>a;
            s.push_back(a);
        }
        ll maxn=0;  //开long long  应为看到数据可能会超出int 数据最高可以到达10^18
        for(int i=0;i<s.size();i++){
            for(int j=i;j<s.size();j++){  //这里最好别i+1,这样就可以考虑到连续子序列为1的情况
                ll k=1;
                for(int l=i;l<=j;l++){  //应上文，这里最好要<=j，原因上同。
                    k=k*s[l];
                }
                maxn=max(maxn,k);
            }
        }
        cout<<"Case #"<<flag<<": The maximum product is "<<maxn<<'.'<<endl<<endl;
    }
}

  枚举分数:1.核心思想:为了避免分数无限细分下去，一般都要根据题意再用初中数学知识，推到出其一变量的上限（可能是某一会得出下限，某一得出上限，多试试就行）。

                  2.典型例题:洛谷 p uva 10976 fraction again?!

                  3.AC代码展示:

#include<bits/stdc++.h>
using namespace std;
int k;
int main(){
    while(scanf("%d",&k)!=EOF){
        vector<int>xx;
        vector<int>yy;
        for(int y=k+1;y<=2*k;y++){   //跟题意可以用初中数学知识推出上限和下限
                if(((k*y)%(y-k))==0){
                    int a=((k*y)/(y-k));  //这个不用开long long ，但是另一个方法就要开long long
                    xx.push_back(a);
                    yy.push_back(y);
                }
        }
        cout<<xx.size()<<endl;
        for(int i=0;i<xx.size();i++){
           cout << "1/" << k << " = 1/" << xx[i] << " + 1/" << yy[i] << endl;
        }
    }
}

这篇关于暴力求解法(一)—简单枚举的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！