【算法】暴力求解法

简单枚举

简单枚举的基本思路就是, 枚举起点, 枚举终点, 然后里面再去做运算, 例题:

对于这道题, 如果使用暴力枚举法的话, 就要枚举每一个元素作为起点, 再枚举每个元素前面的元素作为终点的情况, 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;

int main(){
    int n;
    int ncase=0;
    while(cin>>n){
        // 注意会溢出
        long long ans = 0;
        long long num[100];
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        for(int i=0;i<n;i++){
            for(int j=0; i+j<n; j++){
                long long tmp = 1;
                for(int k=0; k<j; k++){
                    tmp *= num[i+k];
                }
                if(tmp>ans){
                    ans = tmp;
                }
            }
        }
        if(ans<0){
            ans = 0;
        }
        cout<<"Case #"<<++ncase<<": The maximum product is"<<ans<<"."<<endl;
    }
    return 0;
}

这里给一个值范围的表格:

排列法枚举

排列法进行枚举可以使用 STL 中的 next_permutation() , 复杂度为 O(n), 用法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<algorithm>

next_permutation() // 获取下一个排列组合
prev_permutation() // 获取上一个排列组合

// next_premutation(起点, 终点)
//如果有下一个排列组合就返回 true 并替换当前数组, 如果没有就返回 false
int num[4]={1,2,3,4};

do{
    cout<<num[0]<<num[1]<<num[2]<<num[3]<<endl
}while(next_premutation(num,num+4));

例题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n,m;
    while(cin>>n>>m){
        int num[1010];
        for(int i=1;i<=n;i++){
            num[i]=i;
        }
        int tmp=1;
        do{
            if(tmp==m) break;
            tmp++;
        }while(next_permutation(num+1,num+n+1));
        for(int i=1;i<n;i++){
            cout<<num[i]<<" ";
        }
        cout<<num[n]<<endl;
    }
    return 0;
}

二进制法

常用的位运算符有 左移(<<) 和 右移(>>), 位运算操作不建议对负数操作

其中 x<<k 表示将 x 转换为二进制再左移 k 位补零, 十进制下的运算为 $x*2^k$.

x>>k 在十进制下的运算为 $x/2^k$.

位运算常用于状态压缩, 比如有 5 个物品, 我们可以用二进制数 01000 表示只有第 2 个物品被取了, 其他物品没有被取. 当需要枚举的子集或者超集的时候, 就可以使用状态压缩.

以下是常用的位运算技巧:

例题:

这道题可以使用二进制枚举来做

首先是如何用二进制去表示每一个排列组合, 对于 $n$ 个正整数, 从 $0$ 遍历到 $2^n-1$ 就可以表示所有的组合了, 二进制下就是 $00..00$ 遍历到 $11..11$, 然后使用位运算去获取所有的排列, 这里用的位运算是 (i&(1<<j)) 表示获取 i 的 第 j 位, 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<algorithm>
#include<vector>
#include<iomanip>

// sort 的时候用来对排列后的结果排序
bool cmp(vector<int> a, vector<int> b){
    for(int i=0; i<a.size();i++){
        if(a[i]!=b[i]){
            return a[i]<b[i];
        }
    }
}

int main(){
    int n,r;
    cin>>n>>r;
    vector<vector<int>> res;
    // 遍历所有组合
    for(int i=0; i<(1<<n); i++){
        cnt=0;
        //遍历排列
        for(int j=0; j<=n; j++){
            if(i&(1<<j)){
                cnt++;
            }
        }
        //恢复获选的排列
        if(cnt==r){
            vector<int>tmp;
            for(int j=0; j<=n;j++){
                if(i&(1<<j)){
                    // 注意区分值和索引
                    tmp.push_back(j+1);
                }
            }
            res.push_back(tmp);
        }
        // 从小到大排列
        sort(res.begin(),res.end(),cmp);
        for(vector<int> a : res){
            for(int b : a){
                cout<<setw(3)<<b;
            }
            cout<<endl;
        }
    }
    return 0;
}