淘先锋技术网

首页 1 2 3 4 5 6 7

算法——枚举法

一、认识枚举法

枚举法又称为暴力搜索法和穷举法,由名可知此算法是将符合程序条件的所有列举出来,从而选择最合适的结果。

枚举法常通过循环、递归等方式实现,因此枚举法的时间复杂度与问题规模正相关,因此在处理大规模问题时,常常需要采用其他更高效的算法。

适用场景:枚举法通常适用于问题规模较小、时间复杂度低的问题。

二、基本枚举法实践

2.1 题目——烤鸡:

题目描述

猪猪 Hanke 特别喜欢吃烤鸡(本是同畜牲,相煎何太急!)Hanke 吃鸡很特别,为什么特别呢?因为他有 3 3 3 种配料(芥末、孜然等),每种配料可以放 1 1 1 3 3 3 克,任意烤鸡的美味程度为所有配料质量之和。

现在, Hanke 想要知道,如果给你一个美味程度 n n n ,请输出这 3 3 3 种配料的所有搭配方案。

输入格式

一个正整数 n n n,表示美味程度。

输出格式:

3 3 3 个数,表示每种配料所放的质量

样例输入
5
样例输出
1 1 3 
1 2 2 
1 3 1 
2 1 2 
2 2 1 
3 1 1 

提示

对于 100 % 100\% 100% 的数据, n ≤ 5000 n \leq 5000 n5000

题目改编来源:洛谷P2089 烤鸡

2.2 解析

题目思路分析: 此题将三种香料设为枚举对象 x x x y y y z z z,穷举各种香料的数量,同时约束条件为
x + y + z = n 1 ≤ x ≤ 3 1 ≤ y ≤ 3 1 ≤ z ≤ 3 \begin{align} x+y&+z=n\tag{1}\\ 1 \leq &x \leq 3 \tag{2}\\ 1 \leq &y \leq 3 \tag{3}\\ 1 \leq &z \leq 3 \tag{4} \end{align} x+y111+z=nx3y3z3(1)(2)(3)(4)
根据数学公式以及逻辑可制出流程图

下面是这个题的程序:

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int x=1;x<=3;x++){
        for(int y=1;y<=3;y++){
            for(int z=1;z<=3;z++){
                if((x+y+z)==n){
                    cout<<x<<' '<<y<<' '<<z<<' '<<endl;
                }
            }
        }
    }
    return 0;
}

三、枚举法优化

由于现代计算机的发展,硬件性能有较大空间供我们使用,所以在算法比赛以及实际开发中,我们相对于控制空间消耗而言,控制时间消耗更为重要。

根据上述程序,已知三种调料经历了 3 3 3^3 33次枚举,复杂度为 O ( n 3 ) O(n^3) O(n3)。我们由此题可知 n n n为定值,由此可以得出 z = n − ( x + y ) z=n-(x+y) z=n(x+y),此时只需要枚举两种调料即可,经历 3 2 3^2 32次枚举,复杂度为 O ( n 2 ) O(n^2) O(n2)

经过优化思路可得知约束条件从 x + y + z = n x+y+z=n x+y+z=n变为了 n − x − y ⩾ 1 n-x-y \geqslant 1 nxy1

优化后代码:

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int x=1;x<=3;x++){
        for(int y=1;y<=3;y++){
            int z=n-(x+y);
            if(z>=1&&z<=3){
                cout<<x<<' '<<y<<' '<<z<<' '<<endl;
            }
        }
    }
    return 0;
}

四、总结

由此可见,对于枚举算法,应尽量用在数据量较小的地方,优化方案应从加强约束条件,缩小枚举范围为主要方向。