一、枚举法
枚举算法的思想是:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,丢弃不合适的。
使用枚举算法解题的基本思路如下所示:
(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