用穷举法设计算法

第五讲穷举算法学习重点：1、了解穷举法的基本概念及用穷举法设计算法的基本过程。

2、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。

3、能对穷举法编写的程序进行优化学习过程：穷举算法是学生在学完了QB基本语句后最早接触到的算法。

一些简单的穷举算法题目如求水仙花数、找出缺失的数字等和小学生的数学学习紧密结合，程序也比较容易实现，因此学生的学习兴趣还是很高的。

近几年的省小学生程序设计竞赛中也常出现穷举算法的题目，如：2001年题四算24；2002年题三求素数个数与素数个数最多的排列；2005年回文数个数等题目，有些题虽然说用穷举算法实现比较勉强（如2002年题三的后半题求出素数个数最多的排列），但在考试时，如果一时想不出更好的办法，用穷举算法也不失为一种明智的选择。

穷举法，常常称之为枚举法，是指从可能的集合中一一穷举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。

能使命题成立者，即为问题的解。

穷举是最简单，最基础，也是通常被认为非常没效率的算法，但是。

穷举拥有很多优点，它在算法中占有一席之地。

首先，穷举具有准确性，只要时间足够，正确的穷举得出的结论是绝对正确的；其次，穷举拥有全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。

采用穷举算法解题的基本思路：（1）确定穷举对象、穷举范围和判定条件；（2）一一列举可能的解，验证是否是问题的解一、穷举算法的实现在前面基础语句（for语句）的学习中，其实我们就用到了穷举。

比如培训教材p77【例5-7】打印九九乘法表中，被乘数A和乘数B都从1-9一一列举。

这样，九九乘法表中就不会遗失任何一句乘法口诀；在p79【例5-9】的数学灯谜题中，我们也是用了一一列举的方法，找出了A、B、C、D的取值范围。

下面我们再看两道例题：1、搬运砖头【问题描述】36 块砖， 36 人搬。

男搬 4 ，女搬 3 ，两个小儿抬一砖。

要求一次全搬完。

问需男、女、小儿各若干？【问题分析】题目要我们找出符合条件的男生、女生和小孩的人数。

穷举法——计算机求解问题的一种方法概述所谓穷举法，就是在列举所有可能的解，逐一检验直至找到真正的解。

例如，“找出整数n的所有因子”这一问题就可以采用穷举法。

所有可能的解（即因子）落在集合{1, 2, 3, …, n}内，分别用n除一除，余数为0则是因子，否则不是因子。

银行卡密码是6位数字，采用穷举法破解就是把所有6位数都试一遍，那一共要试106次。

人来试是受不了的，而计算机也许可以（因为速度更快）。

所谓暴力破解法正是这样做的。

例一题目：一个首项大于0的递增等差数列前四项和为26，前四项积为880，求该数列的第20项的值。

提示：如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，这个常数叫做等差数列的公差。

例如：等差数列：1，3，5，7，9，11。

该数列的公差是2，第5项值是9。

采用穷举法解题说明如下。

假设数列首项为a，差值为d，有：a+ a+d + a+2d + a+3d = 26a*(a+d) * (a+2d)*(a+3d) = 880如何求出a和d？答：穷举（a，d）的组合。

数列首项a从1穷举到5，差值d可从1穷举到5。

a从1开始是因为题目指出首项大于0，a到5为止是因为数列前4项之和为26，而4*5+6*1（差值d至少为1）等于26。

差值d从1开始是因为是等差数列，差值至少为1，到5为止的因为6*5>26。

这样，构造出了所有可能的解，即（a，d）的组合：(1, 1)，(1, 2), (1, 3), (1, 4), (1, 5), (2, 1),(2,2),(2,3),(2,4),(2,5)…(5,1), (5,2),(5,3),(5,4),(5,5)。

算法描述如下：for a=(1,2,3,4,5):for d=(1,2,3,4,5):如果a+ a+d + a+2d + a+3d等于26且a*(a+d) * (a+2d)*(a+3d)等于880，则：求得数列第20项是a+19*d；算法结束。

穷举法算法案例《用穷举法解决问题》教学设计教学分析 1.教学目标知识与技能：了解什么是穷举法及其特点，以及用穷举法设计算法的基本过程；能够根据具体问题的要求，使用穷举法设计算法。

过程和方法：运用观察、发现、归纳、应用的方法，发展学生的归纳思维；培养学生独立探究与自主发现的学习能力。

情感态度与价值观：了解算法和程序设计在计算机解决问题过程中的重要性；体验将算法转变为程序的过程，享受计算机解决问题的快乐。

2.教学重点和难点重点：用穷举算法解决问题的一般步骤；能根据具体问题的要求，提高运用穷举算法解决问题的能力。

难点：通过观察、类比多种方式培养学生归纳思维。

教学过程1.创设情境激趣引入教师活动：某同学用自己的QQ号登录，可他记不清密码了，你能帮他找回密码吗？他的密码是一个5位数，67□□8，其中百位和十位上的数字他不记得了，但他还记得该数能够被78整除，也能被67整除。

你能帮他设计一个算法求出该密码吗？希望大家能在学习完下面这个例子后就可以解决这个问题。

设计意图：成功的教学不是强制，而是激发学生的学习兴趣，该导入正是从学生感兴趣的事情着手的。

2.观察―发现―归纳―应用(1)观察。

教师活动：逐语句调试以下程序，分析程序的执行过程，让学生填写下表，指出此程序功能。

For i=100 to 999a=int(i /100)b=int(i /10) mod 10C=i mod 10If a^3+b^3+c^3=ithenPrintiEndifNext i(2)发现。

教师引导：在分析上一程序过程中，你能发现什么？学生发现：①通过分析程序的执行过程，可看出变量a存放的是一个三位的自然数百位上的数字，变量b存放的是其十位上的数字，变量c存放的是其个位上的数字；②一个三位的自然数，若满足百位的立方、十位的立方与个位的立方之和等于它本身，就输出；③此程序的功能是输出100～999之间的自然数。

教师总结：此程序的特点是将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件。

4.1—4.2 用解析法、穷举法设计程序【学习目标：】1、理解解析法和穷举法2、分清两者之间的区别在经过大量编程实践之后，人们总结出很多行之有效的算法来解决实际问题。

常用的方法有：解析法、穷举法、查找法、排序法、递归法等。

4.1 解析法所谓解析法是指：通过分析问题中各要素之间的关系，用最简练的语言或形式化的符号来表达它们的关系，得出解决问题所需的表达式，然后设计程序求解问题的方法。

例1：求三角形面积已知a、b、c分别为三角形的三条边长，利用海伦公式求该三角形面积p=(a+b+c)/2编程实现：输入边长a，b，c，如果能构成三角形，输出面积，否则输出“No Answer!”界面如下：Dim a As Single , b As Single , c As Singlea=val(text1.text)b=val(text2.text)c=val(text3.text)If thenp=(a+b+c)/2s=sqr(p*(p-a)*(p-b)*(p-c))text4.text=format(s,”0.00”) ‘结果保留两位小数Elsetext4.text=”no answer”End If根据上述回答下列问题（8分，每空4分）（1）、利用海伦公式求三角形面积的算法是_____（解析法/查找法/枚举法/排序法）。

（2）、填写出参考程序中空白处的表达式________（填写字母：A/B/C/D）A、a + b > c or a + c > b and b + c > aB、a + b > c or a + c > b or b + c > aC、a + b > c and a + c > b or b + c > aD、a + b > c and a + c > b and b + c > a（1）解析法（2）D用解析法求解问题，许多时候并非只是计算一个解析式就可以完事，还要根据问题给出的已经条件，运用归纳、演绎等逻辑方法，揭示问题各要素之间的关系，寻找表示这种关系的表达式，有时需要计算的解析式是一组而不仅仅是一条。

§4.2用穷举法设计程序一、教学目标课程标准规定本节内容主要在于穷举法与问题解决。

包括两个方面：1、理解穷举法的思路。

2、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。

二、学情分析本节内容的教学对象是高一或高二年级学生，他们已经具备了一定的逻辑思维、分析问题、表达思想等能力。

同时，通过前三个章节的学习与实践，学生已初步体验了穷举法的基本思想，经历了用计算机解决问题的过程与步骤，学会了对计算机程序进行调试，掌握了程序的三种基本结构等基础知识，为本节内容的学习提供了良好的基础。

三、教材分析1、本节主要内容介绍穷举法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。

它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。

用穷举算法解决问题，通常可以从以下两个方面进行分析：⑴确定范围：问题所涉及的情况有哪些，情况的种数可不可以确定。

⑵验证条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。

只要把这两个方面分析好了，问题自然会迎刃而解。

本节内容是广东教育出版社出版的普通高中信息技术（选修１）《算法与程序设计》教材第四章第２节的教学内容，包括有穷举法的基本思路，用穷举法求解问题，穷举法中穷举方案的选择等。

2、重点难点分析教学重点：⑴建立正确的数学模型，确定穷举方案。

⑵根据命题确定变量的取值范围。

⑶正确表达“符合条件”的判断。

教学难点：⑴恰当安排穷举的方式，使得算法的效率更高。

⑵如何评价各种穷举策略的优劣。

3、课时安排1课时。

四、教学环境多媒体网络教室、投影仪等。

五、教学过程六、学习评价在教学过程中，设置了学生自评、互评，教师点评等多种评价方式。

同时制订了评价信息反馈表，充分发挥了教学评价的作用。

穷举算法一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的规律或公式）时，可以根据问题的部分条件将所有可能的情况列举出来，然后通过一 个一个验证是否符合整个问题的求解要求，而得到问题的解。

穷举算法简单，但往往运行时所花费的时间很长（因为要列举出所有情况）有些问题所列出的情况数目大的惊人，尽管计算机速度非常快，但是等待运行结果的时间仍然让人无法接受（有些问题用穷举法解可能要几年甚至更多时间），另外列举出来的众多的情况如何在计算机中存储也是个问题，因此穷举法一般用在无规律的问题求解中，并且要尽可能地将明显不符合条件的情况排除在外，以节省时间。

1、圆盘找数，如图所示，找出4个相邻的数，使其相加之和最大和最小的是哪4个数，并2、将A,B,C,D,E,F 这6个变量排成如图的三角形，这6个变量分别取[1，6]上的整数，且均不相同，求使三角形三条边上的变量之和相等的全部解。

（其中一个解）3、【问题】甲乙丙丁戊五个人在运动会上分获百米、二百米、跳高、跳远和铅球冠军，有四个人猜测比赛结果：Ａ说：乙获铅球冠军，丁获跳高冠军。

Ｂ说：甲获百米冠军，戊获跳远冠军。

Ｃ说：丙获跳远冠军，丁获二百米冠军。

Ｄ说：乙获跳高冠军，戊获铅球冠军。

其中每个人都只说对一句，说错一句。

求五人各获哪项冠军。

【算法】用1,2,3,4,5分别代表百米、二百米、跳高、跳远和铅球５个项目，用a,b,c,d,e 分别代表五人。

如b=3 表示乙获跳高冠军。

用多重循环穷举出来。

4、古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外），例如28的因子是1，2，4，7，14，且1＋2＋4＋7＋14＝28，则28是一个完全数，编程求2～1000内的所有完全数。

A B C D E F 16 3 2 5 45、一根29cm长的尺子，只允许在上面刻7个刻度，要能用它量出1～29cm的各种长度，试问这根尺的刻度应该怎样选择？6、邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票张数不超过三枚，存在整数r ，使得用不超过三枚的邮票，可以贴出连续的整数1，2，3，………r 来，找出这四种面值数，使得r 值最大。

穷举法算法案例穷举法，又称为暴力搜索或者暴力破解，是一种简单直接的算法，它通过尝试所有可能的情况来寻找问题的解。

虽然在某些情况下效率不高，但在一些小规模问题或者需要精确解的情况下，穷举法仍然是一个有效的解决方案。

下面我们将通过几个案例来了解穷举法的具体应用。

案例一，寻找素数。

素数是指除了1和自身外没有其他因数的自然数，例如2、3、5、7等。

我们可以通过穷举法来寻找一定范围内的所有素数。

具体做法是从2开始，依次判断每个数是否能被2到该数平方根之间的所有数整除，如果不能则该数是素数。

这种方法虽然效率不高，但对于小范围内的素数搜索是可行的。

案例二，密码破解。

在密码学中，穷举法常常被用来破解简单的密码，例如暴力破解4位数字密码。

假设密码由0-9的数字组成，那么一共有10000种可能的密码组合。

通过穷举法，我们可以依次尝试每一种组合，直到找到正确的密码。

当然，对于更复杂的密码，穷举法可能需要花费更长的时间，但在一些情况下仍然是有效的。

案例三，旅行推销员问题。

旅行推销员问题是一个经典的组合优化问题，假设有n个城市，推销员需要从某个城市出发，经过每个城市一次，最终回到出发的城市，要求找到一条最短的路径。

穷举法可以用来解决这个问题，具体做法是列举出所有可能的路径，计算它们的长度，最终找到最短的路径。

虽然对于大规模的问题来说，穷举法并不是最优的解决方案，但在小规模问题上仍然是可行的。

总结。

穷举法作为一种简单直接的算法，在一些情况下仍然具有一定的应用价值。

然而，需要注意的是，穷举法在处理大规模问题时可能会面临效率低下的问题，因此在实际应用中需要根据具体情况选择合适的算法。

希望通过上述案例的介绍，能够让大家对穷举法有一个更加深入的了解。

一、课程名称
用穷举法设计程序
二、授课人
李莎
三、教学目标
1．知识与技能
了解穷举法的基本概念及用穷举法设计算法的基本过程，能够根据具体问题要求，使用穷举法设计算法的基本过程。

2．过程与方法
通过分析和编写不同举例程序，掌握穷举法的穷举技巧（变量安排、穷举方案的确定）。

3．情感态度
通过研究穷举的技巧，积累程序设计的经验，提升自己设计程序求解问题的能力。

对于多种解决问题的方案，学会评价它们的好坏。

四、重点与难点分析
教学重点：
（1）建立正确的数学模型，确定穷举方案。

（2）根据命题确定自变量的取值范围。

（3）正确表达“符合条件”的判断。

教学难点：
（1）如何确定穷举方案。

（2）如何评价各种穷举方案的优劣。

五、教学方法
采用讲解、交流、任务驱动的教学方法。

六、教学环境
学生电脑多媒体教室。

七、教学时数
2课时
八、教学过程
第1课时
第2课时。

搜索方法——穷举算法穷举法，常常称之为枚举法，是指从可能的集合中一一穷举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。

能使命题成立者，即为问题的解。

穷举是最简单，最基础，也是通常被认为非常没效率的算法，但是。

穷举拥有很多优点，它在算法中占有一席之地。

首先，穷举具有准确性，只要时间足够，正确的穷举得出的结论是绝对正确的；其次，穷举拥有全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。

采用穷举算法解题的基本思路：（1）确定穷举对象、穷举范围和判定条件；（2）一一列举可能的解，验证是否是问题的解例题：谁是小偷Description警察抓住A B C D四名罪犯，其中一人是小偷。

审问A 说："我不是小偷"。

B说"C是小偷"。

C说"小偷肯定是D"。

D说"C在冤枉人"。

现在已经知道四个人中三人说的是真话，一个人说假话，问小偷到底是谁？Sample OutputC代码如下：Var a,b,c,d:integer;beginfor a:=0 to 1 do beginfor b:=0 to 1 do beginfor c:=0 to 1 do beginfor d:=0 to 1 do beginif a+b+c+d=1 then beginif ord(a=0)+ord(c=1)+ord(d=1)+ord(d<>1)=3 then begin if a=1 then writeln('A');if b=1 then writeln('B');if c=1 then writeln('C');if d=1 then writeln('D');end;end;end;end;end;end;end.再看一眼条件：审问A说："我不是小偷"。

穷举法穷举法是程序设计中使用最为普遍的一种基础算法。

计算机的特点之一就是运算速度快、善于重复做一件事情，“穷举法”正是基于这一特点的最古老算法。

它一般是在一时半会找不到解决问题的更好途径，即从数学上找不到求解的公式或规律时，根据问题中的“约束条件”，将求解的所有可能情况一一列举出来，然后再逐一验证它否符合整个问题的求解要求，从而得到问题的所有解。

示例1：求满足表达式A+B=C的所有整数解，其中A,B,C为1~3之间的整数。

【分析】本题非常简单，即枚举变量A，B，C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。

【算法】算法用伪代码描述如下：for A:=1 to 3 dofor B:=1 to 3 dofor C:=1 to 3 doif(A+B=C) thenwriteln(A,’’,B,’’C);【流程图】所谓穷举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定那些是无用的，哪些是有用的。

能使命题成立的，即为解。

在本案例中解变量有3个：A，B，C。

其中：解变量A的可能取值范围A∈｛1,2,3｝解变量B的可能取值范围B∈｛1,2,3｝解变量C的可能取值范围C∈｛1,2,3｝从而问题的可能解有3*3*3=27个，可能解集在上述可能解集中，满足题目给定的检验条件（A+B==C）的解元素，即为问题的解。

穷举法的适用范围：其一，能确定解变量（枚举变量）的个数n，其二，每个解变量Ai（1<=i<=n）的可能值能确定范围且能连续取得。

设解变量的个数是n，Ai1----解变量Ai的最小值；Aik----解变量Ai的最大值（1≤i≤n）；即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank算法框架如下（伪代码）：for A1←A11 to A1k do……for Ai←Ai1 to Aik do……for An←An1 to Ank doif状态（A1,…,Ai,…,An）满足检验条件then 输出问题的解穷举法（枚举法）的特点是算法简单，但是有时运算量大。

《用穷举法设计程序》教课方案执教教师：佛山市第三中学杨溢执教课校：绵阳南山中学一、基本状况本节内容是广东教育第一版社第一版的一般高中信息技术（选修１）《算法与程序设计》教材第四章第２节《用穷举法设计程序》的教课内容，包含用穷举法求解问题的基本过程、穷举法的基本思路，穷举法中变量的安排，穷举法中穷举方案的选择等。

本节建议使用两个课时来达成。

第一课时：穷举法求解问题的基本过程、穷举法的基本思路，穷举法中变量的安排，第二课时：穷举法中穷举方案的选择。

而本节课是穷举法的第一课时。

二、教课目的课程标准中的有关内容：1、认识穷举法的基本观点及用穷举法设计算法的基本过程。

2、能够依据详细问题的要求，使用穷举法设计算法，编写程序求解问题。

依据课程标准，确定本节课（用穷举法解决问题的基本过程）的教课目的以下：1、知识与技术⑴认识穷举法的基本观点及特色⑵能概括穷举法穷举的要点。

（设置穷举变量、变量变化范围、书写考证条件）⑶认识穷举法设计程序的基本过程。

⑷能够依据详细问题的要求，使用穷举法思想剖析问题，设计算法，编写程序求解问题。

⑸能够依据详细问题的条件，进行算法优化。

2、过程与方法⑴经历用穷举法求解问题的基本过程。

⑵能经过实质问题的剖析、求解过程，试试概括出利用穷举法解决问题的思路和方法。

3、感情态度与价值观⑴在解决问题的过程中进一步培育和提高学生的逻辑思想能力⑵培育学生算法优化的思想。

⑶认识穷举法在破解密码方面的现实应用，自觉养成保护密码的优秀习惯。

三、教材剖析1、本节在主要内容介绍⑴穷举算法的基本思路：对要解决问题的全部可能状况，一个不漏地进行检查，从中找出切合要求的答案。

⑵用穷举算法解决问基本过程：A)剖析问题：问题的条件和未知数是什么？能够用分析法解决吗？适适用穷举法吗？B)算法设计a.穷举法的基本算法（用循环语句列举穷举变量的穷举范围，用条件语句描绘考证条件）b.穷举算法设计的三个要点：ⅰ . 确定穷举变量：问题波及哪些要素需进行穷举；ⅱ . 确定穷举范围：问题所波及的状况有哪些，穷举范围应当怎样确定；ⅲ . 考证条件：剖析出来的这些状况，需要知足什么条件，才成为问题的答案。

算法分析与设计实验一——穷举算法（黑体，三号）1.穷举简介（小标题：黑体，小四；内容：宋体，五号）穷举法又称列举法，其基本思想是逐一列举问题所涉及的所有情况。

从中寻找满足条件的结果。

适用于数量较小的问题。

2.算法流程或设计思想穷举通常应用循环结构来实现。

在循环体中，应用选择结构实施判断筛选，求得所要求的解。

使用穷举法的关键是要确定正确的穷举的范围。

3.分析算法的时间复杂度4.程序设计中的问题及解决方案5.运行说明（包括实验数据和结果说明）6.主要程序代码（添加程序注释）7.对比解决该问题的其他算法（选作）题目：1.有一堆零件（1000－5000个之间），如果以4个零件为一组进行分组，则多2个零件；如果以7个零件为一组进行分组，则多3个零件；如果以9个零件为一组进行分组，则多5个零件。

编程求解这堆零件总数。

参考答案：#include<stdio.h>void main(){int n,count=0;for(n=1000;n<=5000;n++)if(n%4==2&&n%7==3&&n%9==5){printf("%d ",n);count=count+1;if(count%5==0)printf("\n");}printf("\ncount = %d\n",count);}2.穷举三位数的水仙花数。

水仙花数是指一个n 位数( n≥3 )，它的每个位上的数字的n 次幂之和等于它本身。

（例如：13 + 53 + 33 = 153）参考答案：/*2. 穷举三位数的水仙花数。

水仙花数是指一个n 位数( n≥3 )，它的每个位上的数字的n 次幂之和等于它本身。

（例如：13 + 53 + 33 = 153）*/#include <stdio.h>void main(){int a,b,c,d;for(a=100;a<=999;a++){b=a/100;c=a/10-b*10;d=a-b*100-c*10;if(b*b*b+c*c*c+d*d*d==a)printf("%d = %d^3 + %d^3 + %d^3\n",a,b,c,d);}}3.穷举真分数递增序列中的第k项的值。

利用穷举法编写一个算法判断给定的正整数n是否是素数,即判断n是否只能被1和自身
整
在数学中，素数（prime number）是一类被1和自身整除的自然数，这里我们将介绍判断给定自然数是否是素数的穷举法算法。

假设给定正整数 n，我们可以从 2 开始循环到 n-1，令每个数k 都分别和n去除。

如果n除以k余数为0，说明n能被整除，故n不是素数；如果n除以k余数不为0，则继续循环至到n-1，每一次除法操作均余数不为0，即最终也不会被整除，故n是素数。

穷举法实现，即从2开始到n-1，对每个k，令n和k去除：
(1)若n除以k余数为0，则n不是素数；
(2)若n除以k余数不为0，则继续和（k+1）去除。

(3)若n除以（n-1）余数不为0，则n是素数。

在实际编程中，我们可以利用循环来实现穷举法，如java语言中编写如下程序：
public static boolean isPrime（int n）
{
for (int k = 2;k<=n-1;k++)
{
if (n % k == 0)
return false;
}
return true;
}
最后还需要说明的是，穷举法虽可以用来判断给定的正整数n是否是素数，但当n较大时，效率会非常低，此时我们可以采用其他比较有效的数论算法来判断给定的正整数n是素数或偶数。