唐巧的博客
·
CSPJ 教学思考：枚举
💡
原文中文，约8000字，阅读约需19分钟。
📝
内容提要
本文讨论了多种编程题目的枚举方法，包括哥德巴赫猜想、烤鸡配料、全排列和组合等。通过递归和循环实现枚举，避免重复计算以提升效率。示例代码展示了如何使用 STL 的 next_permutation 函数生成全排列和组合，并分析了特定问题的时间复杂度及优化策略。
🎯
关键要点
- 枚举是尝试所有情况的过程，简单的可以用 for 循环，复杂的需要用递归。
- 哥德巴赫猜想的枚举方法是将每个合数拆解为两个质数的和，使用 map 保存质数运算结果以避免重复计算。
- 烤鸡配料问题中，虽然 N 很大，但每种配料最多 3 克，总克数不超过 30 克，因此暴力枚举的时间复杂度为 3^10，不会超时。
- 全排列问题可以使用 STL 的 next_permutation 函数来实现，简化了代码的复杂性。
- 组合问题也可以利用 next_permutation，通过构造一个包含 0 和 1 的数组来表示选中和未选中的状态。
- 在处理复杂的枚举问题时，预先保存相关数据可以提高效率，例如在涂条纹问题中，预保存每行的颜色块数量以快速求解。
- 在火柴棒等式问题中，通过枚举数字 A 和 B 的范围，计算其火柴数并检查是否满足条件，最终输出所有可能的组合。
❓
延伸问答
枚举的基本概念是什么？
枚举是尝试所有情况的过程，简单的可以用 for 循环，复杂的需要用递归。
如何使用递归解决哥德巴赫猜想的枚举问题？
通过将每个合数拆解为两个质数的和，并使用 map 保存质数运算结果以避免重复计算。
烤鸡配料问题的时间复杂度是多少？
暴力枚举的时间复杂度为 3^10，约为 59000，不会超时。
如何使用 STL 的 next_permutation 函数生成全排列？
全排列问题可以直接用 STL 中的 next_permutation 函数来实现，简化了代码的复杂性。
组合问题如何利用 next_permutation 实现？
通过构造一个包含 0 和 1 的数组来表示选中和未选中的状态，利用 next_permutation 进行组合生成。
在复杂的枚举问题中，如何提高效率？
预先保存相关数据可以提高效率，例如在涂条纹问题中，预保存每行的颜色块数量以快速求解。
➡️
