第2讲 穷举

程序设计竞赛系列讲座

第1讲

第2讲

第3讲

第4讲

第5讲

第6讲

第7讲

杨克昌

程序设计竞赛引论 穷举 递推 递归 回溯 动态规划 综合训练 1

第2讲 穷举

穷举是计算机程序设计引导入门的基础算法，也是在数量较小的问题求解中应用广泛的算法。应用穷举设计可以非常简明地解决许多实际问题。

本章介绍统计求和、解方程、解不等式、求最值以及涉及素数的基础案例的穷举求解，并由整币兑零、完美综合式与和积三角形三个安全的求解说明穷举设计的改进与优化。

2.1 穷举概述

1. 穷举的概念

穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。

通常程序设计入门都是从穷举设计开始的。今天，计算机的运算速度非常快，应用穷举设计程序可快捷地解决一般数量的许多实际应用问题。

穷举法的特点是算法设计比较简单，解的可能为有限种，一一列举问题所涉及的所有情形。 穷举法常用于解决“是否存在”或“有多少种可能”等问题。其中许多实际应用问题靠人工推算求解是不可想象的，而应用计算机来求解，充分发挥计算机运算速度快、擅长重复操作的特点，穷举判断，快速简便。

应用穷举时应注意对问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。重复列举直接引发增解，影响解的准确性；而列举的遗漏可能导致问题解的遗漏。

2. 穷举的框架描述

穷举通常应用循环结构来实现。在循环体中，根据所求解的具体条件，应用选择结构实施判断筛选，求得所要求的解。

穷举法的框架描述： n=0;

for(k=<区间下限>;k<=<区间上限>;k++) // 根据指定范围实施穷举 if(<约束条件>) // 根据约束条件实施筛选 { printf(<满足要求的解>); // 输出满足要求的解 n++; // 统计解的个数 }

有些问题没有明确的区间限制，可根据问题的具体实际试探性的从某个数开始，增值穷举，对每一个数作一判断，若满足条件即输出结果，结束穷举。

尽管穷举比较简单，在应用穷举设计求解实际问题时要认真分析，准确选定穷举范围与约束条件。

2

3. 穷举的实施步骤

应用穷举设计求解，通常分以下几个步骤：

（1）根据问题的具体情况确定穷举量（简单变量或数组）； （2）根据确定的范围设置穷举循环；

（3）根据问题的具体要求确定筛选约束条件；

（4）设计穷举程序并运行、调试，对运行结果进行分析与讨论。

当问题所涉及数量非常大时，穷举的工作量也就相应较大，程序运行时间也就相应较长。为此，应用穷举求解时，应根据问题的具体情况分析归纳，寻找简化规律，精简穷举循环，优化穷举策略。

4. 穷举设计的意义 虽然巧妙和高效的算法很少来自穷举，但穷举设计作为一种常用的基础算法不能受到冷漠与轻视：

（1） 理论上，穷举可以解决可计算领域中的各种问题。尤其处在计算机计算速度非常高的今天，穷举的应用领域是非常广阔的。

（2） 在实际应用中，通常要解决的问题规模不大，用穷举设计的算法其运算速度是可以接受的。此时，设计一个更高效率的算法代价不值得。

（3） 穷举可作为某类问题时间性能的底限，用来衡量同样问题的更高效率的算法。

本章将通过若干典型案例的求解，说明穷举的实际应用。

2.2 统计与求和

统计与求和是程序设计最基本的课题，通常只要合理运用穷举即可简捷地解决问题。 本节介绍最简真分数与数字有特殊要求的整数这两个典型案例的穷举求解，提高对运用穷举实施统计与求和技巧的认识。

2.2.1 最简真分数统计求和

1. 案例提出

统计分母在指定区间[a,b]的最简真分数(分子小于分母，且分子分母无公因数)共有多少个,并求这些最简真分数的和(正整数a,b从键盘输入)。

2．算法设计

设分数为分子为i，分母为j，最简真分数的和为s。 在指定范围内[a,b]穷举分数的分母j:a——b； 同时对每一个分母j穷举分子i:1——j-1。 对每一分数i/j，置t=0，然后进行是否存在公因数的检测。

如果分子i与分母j?存在大于1的公因数u，说明i/j非最简真分数,应予舍略。因为分子分母同时约去u后，分母可能不在[a,b]，即使在[a,b]时前面已作了统计求和。

3