一、枚举法
枚举算法的思想是:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,丢弃不合适的。
使用枚举算法解题的基本思路如下所示:
(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
Java 面试宝典是大明哥全力打造的 Java 精品面试题,它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题,而是一套完整的 Java 知识体系,一套你 Java 知识点的扫盲贴。
它的内容包括:
- 大厂真题:Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容:Java 面试宝典内容全部都是大明哥原创,内容全面且通俗易懂,回答部分可以直接作为面试回答内容。
- 持续更新:一次购买,永久有效。大明哥会持续更新 3+ 年,累计更新 1000+,宝典会不断迭代更新,保证最新、最全面。
- 覆盖全面:本宝典累计更新 1000+,从 Java 入门到 Java 架构的高频面试题,实现 360° 全覆盖。
- 不止面试:内容包含面试题解析、内容详解、知识扩展,它不仅仅只是一份面试题,更是一套完整的 Java 知识体系。
- 宝典详情:https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览:https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展:https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道,总字数 42w+。大明哥还在持续更新中,下图是大明哥在 2024-12 月份的更新情况:
想了解详情的小伙伴,扫描下面二维码加大明哥微信【daming091】咨询
同时,大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ,回复【面试题】 即可免费领取。