美文网首页数据结构与算法
常见算法思想1:枚举法

常见算法思想1:枚举法

作者: GoFuncChan | 来源:发表于2020-02-19 17:13 被阅读0次

    一、枚举法

    枚举算法的思想是:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,丢弃不合适的。

    使用枚举算法解题的基本思路如下所示:

    (1)确定枚举对象、枚举范围和判定条件。
    (2)逐一枚举可能的解,验证每个解是否是问题的解。

    枚举算法一般按照如下3个步骤进行:

    (1)题解的可能范围,不能遗漏任何一个真正解,也要避免有重复。
    (2)判断是否是真正解的方法。
    (3)使可能解的范围降至最小,以便提高解决问题的效率。

    什么时候选择枚举法?

    在任何情况下,都需要选准最合适的对象,无论是枚举还是其他算法思想,这是最关键的。选准(枚举)对象的根本原因在于优化,具体表现为减少求解步骤,缩小求解的解空间,或者是使程序更具有可读性和易于编写。有时候选好了枚举对象,确定了枚举思想解决问题,问题就迎刃而解了。有的时候,当题目逼着你用枚举思想解题时,需要考虑的往往是从众多枚举对象中选择最适合的,这需要辨别的智慧。

    运用枚举思想思考时需要面对如下表的问题:

    特点及要求 可能出现的问题
    选取考察对象 选取的考察对象不恰当
    逐个考察所有可能的情况 没有“逐个”考察,不恰当地遗漏了一些情况;可能的情况 没有“逐个”考察不恰当地遗漏了一些情况;没有考察“所有”,对解空间集的确定失误
    选取判断标准 判断标准“不正确”,导致结果错误;判断标准“不全面”,导致结果错误或得到结果的效率下降;判断标准“不高效”,意味着没有足够地剪枝
    方法实践

    百钱买鸡问题:公鸡一个五块钱,母鸡一个三块钱,小鸡三个一块钱,现在要用一百块钱买一百只鸡,问公鸡、母鸡、小鸡各多少只?

    func F() {
        var gj, mj, xj int // 分别表示可以购买的公鸡、母鸡、小鸡数
    
        var maxGj = 100 / 5
        var maxMj = 100 / 3
    
        for gj = 0; gj <= maxGj; gj++ {
            for mj = 0; mj <= maxMj; mj++ {
                xj = 100 - gj - mj
                if xj%3 == 0 && gj*5+mj*3+xj/3 == 100 {
                    fmt.Printf("公鸡:%d,母鸡:%d,小鸡:%d\n", gj, mj, xj)
                }
            }
        }
    }
    

    运行结果:

    === RUN   TestF
    公鸡:0,母鸡:25,小鸡:75
    公鸡:4,母鸡:18,小鸡:78
    公鸡:8,母鸡:11,小鸡:81
    公鸡:12,母鸡:4,小鸡:84
    --- PASS: TestF (0.00s)
    PASS
    

    相关文章

      网友评论

        本文标题:常见算法思想1:枚举法

        本文链接:https://www.haomeiwen.com/subject/tnvgfhtx.html