(完整word版)穷举法

基础算法（⼀）穷举法
基础算法（⼀）穷举法
穷举法的基本思想:从可能的解集合中⼀⼀穷举各元素，⽤题⽬给定的检验条件判定哪些是有⽤的，哪些是⽆⽤的，能使命题成⽴的，即为其解。

穷举法解题思路：
1、对命题建⽴正确的数学模型；
2、根据命题确定数学模型中各变量的变化范围（即可能解的范围）；
3、利⽤循环语句、条件判断语句逐步求解或证明。

穷举法的特点：
算法简单，但运算量⼤。

对于可能确定解的范围，⼜⼀时找不到更好的算法时，可以采⽤穷举法。

例1、求满⾜表达式A+B=C的所有整数解，其中A、B、C为1～3之间的整数。

例2、鸡兔同笼问题（在同⼀个笼⼦⾥有鸡和兔⼦若⼲只，从上⾯看，能看到20个头，从下⾯看，能看到60只脚，问鸡兔各有多少只？）例3、百钱百鸡问题（⼀百块钱要买⼀百只鸡，这⼀百只鸡必须包含母鸡、公鸡和⼩鸡，其中，公鸡5元⼀只，母鸡3元⼀只，⼩鸡1元三只，
问有哪些购买⽅案？）
例4、⽔仙花数问题（ABC=A3+B3+C3,列出所有的整数ABC）
在⽤穷举法时，问题必须满⾜两个条件：
1、能够预先确定可能解的个数；
2、对每个解变量的取值，其变化范围也能预先确定。

使⽤穷举法时应注意的问题：
1、减少穷举变量；
2、缩⼩穷举变量的取值范围。

基本信息简介穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。

例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试9999次就能找到正确的密码。

理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。

因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

字符类型字符类型一般可以分为以下5种1.数字型0、1、2、3.4...9等（10个）2.大写字母A、B、C、D...Z等（26个）3.小写字母a、b、c、d...z等（26个）4.特殊字符～、$、#、@、&、()*等（33个）一般较少用5.用户自定义字符。

如果一个多位数并且有可能包含以上所有字符的密码的组合方法一定多的惊人，相对来讲破译的时间也会长的没法接受，有时可能会长达数年之久。

2破译方法概述穷举法是一种针对于密码的破译方法。

这种方法很像数学上的“完全归纳法”并在密码破译方面得到了广泛的应用。

简单来说就是将密码进行逐个推算直到找出真正的密码为止。

比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试9999次才能找到真正的密码。

利用这种方法我们可以运用计算机来进行逐个推算，也就是说用我们破解任何一个密码也都只是一个时间问题。

当然如果破译一个有8位而且有可能拥有大小写字母、数字、以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算，其组合方法可能有几千万亿种组合。

这样长的时间显然是不能接受的。

其解决办法就是运用字典，所谓“字典”就是给密码锁定某个范围，比如英文单词以及生日的数字组合等，所有的英文单词不过10万个左右这样可以大大缩小密码范围，很大程度上缩短了破译时间。

在一些领域，为了提高密码的破译效率而专门为其制造的超级计算机也不在少数，例如IBM为美国军方制造的“飓风”就是很有代表性的一个。

3对策现今稍具严密度的密码验证机制都会设下试误的可容许次数以应对使用密码穷举法的破解者。

• 观看C语言程序片断
开始 x=1
2x+4(30x)=95?
开始
x=1 是 X<=30? 是 2x+4(30x)=95?
30-
否
否
否
x累加1
是
输出x, x
输出x，30-x x累加1
结束
结束
(P23)练一练：在一个停车场共有24辆车，包
括4个轮子的汽车和3个轮子的摩托车，车轮共 86个，请问3轮摩托车几辆？请你画出流程图
开始
已设定密码P i从0开始逐一尝试， 直至找到符合条件 (i=P)的答案为止 是 i=p? 否 i=i+1 (i累加1)
i=0
输出 i
结束
• 穷举法:就是按照事物发展规律,将问题的所
有可能的答案一一列举,然后根据条件判断 此答案是否合适,合适就保留,不合适就丢弃 的一种方法。
1、今年弟弟6岁，哥哥15岁，当 两人年龄和为65岁时，弟弟几岁？
开始
x=1
否
x<=24?
是 3x+4(24-x)=86? 是 输出x，24-x X累加1
否
结束
开始
x=1
否 X<=30? 是 2x+4(30-x) =96? 是 输出x，30-x 否
x累加1
结束
X<=30?
（1）当找不到符合条件的值时， 可以避免死循环
（2）跳出循环时，x最终的值不同
想想该流程图应如何修改,避免死循环呢？
输出ห้องสมุดไป่ตู้x,
30-x 结束
2、笼中有鸡和兔，共有30个头，95只脚。问 鸡、兔各几只？（设鸡x只)
开始
x=1
是

穷举法
穷举的思想
鸡兔同笼
• 鸡兔同在一个笼子里，共有35个头、94只 脚，请问，笼中鸡有几只、兔有几只？
ቤተ መጻሕፍቲ ባይዱ
算法
• 抬脚法： 鸡、兔都抬2只脚，则多余的是兔的脚。 94-2*35=24 兔子=24/2=12
列举每一种可能
鸡
兔
总脚数
0
35
2*0+4*35
1
34
1*2+4*34
2
33
2*3+4*33
找回密码
• 小婷的邮箱的密码是一个5位数，但由于较 长时间没有打开这个邮箱，她忘记了密码 。小婷的生日是8月1日，她妈妈的生日是9 月1日，所以她特别喜欢用81和91的公倍数 ，她还记得这个密码的百位数是1.你能设计 一个程序帮她找回密码吗？
列举每一种可能
公鸡 0 0 0 …. 20 20 20
母鸡 0 1 2
78 79 80
小鸡 100 99 98
2 1 0
所需钱数
x
y
z
请写出下列程序
For i= to ‘公鸡的数目
for j=
to ‘母鸡的数量
k=
‘小鸡的数量
if
then
print i,j,k
end if
next j
next i
（1）枚举鸡的数目： 0-35只 （2） 确定兔的数目：35-鸡的数目 （3）验证腿的数目：2*鸡+4*兔=? 94 如果相等，就是一个解
dim i,j as integer ‘i表示鸡，j表示兔的数量 for i=0 to 35
j=35-i if 2*i+4*j=94 then
print i,j end if next i

用穷举法求解的基本过程穷举法又称试探法，是求解复杂问题常用的一种算法。

它被用来求解实际生活中各种数学、物理、化学、经济和社会等问题，它具有良好的实用价值。

穷举法是求解复杂问题的一种有效方法。

一、基本步骤（1）明确问题。

明晰问题，确定问题的求解内容，定义解空间。

（2）构建搜索树。

将解空间的每一个可能情况看作一个结点，绘制搜索树，综合运算问题的知识，将搜索空间分拆成若干小搜索空间，由此得出结点关系。

（3）生成搜索策略。

根据问题特点及给定的条件来确定搜索策略，选择最有效的搜索方式进行搜索，此步骤将决定整个穷举法求解问题的有效性。

（4）开始搜索。

依据构建的搜索树和确定的搜索策略开始搜索，首先检测第一个结点，根据条件检测的结果如果不满足就进行下一个结点的检测，直至找到最终的结果，搜索停止。

（5）结果验证。

检查搜索结果，验证是否符合原问题的要求，确保问题得到正确的求解结果。

二、优缺点（1）算法在求解复杂问题上有良好的实用价值，能够较好地把问题分解为若干小问题。

（2）搜索空间确定时，受限于其解空间的大小，穷举法在处理解空间较大的问题时存在搜索时间长的问题。

（3）穷举法在求解给定问题时，必须要进行大量的计算，计算量较大，影响了算法的效率。

（4）穷举法也缺乏一定的针对性，如果解空间较大，则需要花费更多的时间来完成。

穷举法是求解复杂问题的一种有效的方法，它具有良好的实用价值，综合运用数学、物理、化学、经济和社会等问题，可以有效地搜索出最优解。

但是，该算法也存在搜索时间过长、计算量大、缺乏针对性等弊病，该如何改进才能更好地提高求解复杂问题的效率，因此，对穷举法还有很大的改进空间，需要不断探索新的方法去改进穷举法，从而使它更好地服务于实践生活。

拓展知识5-1 穷举法一、什么是穷举法在实际问题中，经常遇到在一定范围内寻求某类事物解的问题。

比如：求水仙花数，因为水仙花数是一个三位数，所以，[100,999]就是给定的范围，水仙花数就是要求的解；又如：百马百担问题，求解决方案，大马数量[1,33]，中马数量[1,50]，小马数量[1,100] 就是给定的范围，解决方案就是要求的解等。

像这类问题，可以通过对指定范围内每种可能的情况进行一一测试，验证其是否是满足条件的解的方法来解决，我们就把这种解决问题的方法称为穷举法。

由于实际问题的指定范围可能很大，所以，穷举法更适合于使用计算机，因此，这类问题可通过程序设计来解决。

二、穷举法解决问题的关键1．确定范围（1）往往实际问题给定的范围不一定很明确，需要我们通过分析来确定范围；（2）所得到的范围还可以利用给定的部分约束条件进一步缩小，以减少程序的运行时间，提高效率。

2．确定解的条件通过对实际问题进行分析，给出判断解的条件，有了判断解的条件才能对每种可能的情况进行一一验证，从而得到问题的解。

三、穷举法解决问题的步骤1．分析问题，确定范围变量，给出解的判断条件；2．用循环或循环的嵌套对范围变量的所有可能情况进行一一测试；3．用选择语句判断每种情况是否符合解的条件；4．输出符合条件的情况。

四、穷举法的优化策略1．减少范围变量范围变量能少用尽量少用，这样可大大减少测试的数量。

例如百马百担问题，对大马、中马、小马均可设一个范围变量dm、zm、xm，其范围分别是：[1,33]，[1,50]，[1,100]，总的测试数量为33*50*100=165000次；在大马、中马具体确定后，小马可利用约束条件dm+zm+xm=100来确定，因此，只需将大马、中马设为范围变量，这样测试数量为33*50=1650次。

可见，减少范围变量的使用可大大减少测试的数量。

2．缩小穷举范围根据实际问题的隐含条件，可将不符合条件的情况去掉，缩小穷举范围，减少穷举变量的值域。

rmax:=0;s1:=1; for s2:=2 to 10 do for s3:=3 to 10 do for s4:=4 to 10 do begin 计算R值； IF R>RMAX THEN BEGIN RMAX:=R;记录对应的S1，S2，S3，S4； END; end;
计算某个解对应的连续最大R值
培养学生自主建构的意识和能力
1、不应对蕴含穷举思想的问题求解抱通过了事的心态。 、不应对蕴含穷举思想的问题求解抱通过了事的心态。 2、而应基于异中求同的思维，把蕴含穷举思想的问题 、而应基于异中求同的思维， 纳入穷举法的算法系统中来，引导、培养学生自主 纳入穷举法的算法系统中来，引导、 建构信息学知识系统的意识和能力。 建构信息学知识系统的意识和能力。 3、现状。平时做大量试题，比赛时却对类似问题的算 、现状。平时做大量试题， 法确定犹豫不决。知识系统建构不完善的结果。 法确定犹豫不决。知识系统建构不完善的结果。
初识穷举法
穷举法算法结构 按照问题解的特征可以分为“解分量只有 按照问题解的特征可以分为“ 一个” 解分量有多个”二类。 一个”和“解分量有多个”二类。所谓解 分量个数指的是问题解包含特征参数的个 数。
解分量只有一个的情形
这种情形的问题求解由于只有一个解分量， 这种情形的问题求解由于只有一个解分量， 程序结构相对简单。由于只有一个解分量， 程序结构相对简单。由于只有一个解分量， 所以就可用一重循环来穷举所有的可能值， 所以就可用一重循环来穷举所有的可能值， 然后进行条件判断。 然后进行条件判断。
解分量有多个的情况
由于一重循环只能穷举问题解的一个解分量， 由于一重循环只能穷举问题解的一个解分量， 所以当问题解的分量有多个时， 所以当问题解的分量有多个时，就需要用多 重循环嵌套来穷举问题解的所有分量。 重循环嵌套来穷举问题解的所有分量。一般 的处理方法是一层循环穷举一个分量， 的处理方法是一层循环穷举一个分量，如果 个分量， 重循环嵌套。 有3个分量，就需要 重循环嵌套。 个分量 就需要3重循环嵌套

穷举法、贪心法、分枝限界法讲解人：一、穷举法（枚举法）（一）算法思路就是从可能的解的集合中一一枚举各元素，用题目给定的检验条件，判定哪些是无用的，哪些是有用的。

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

（二）例子（第二章介绍过的货郎担问题）假定以编号为1的城市为始发城市，那么就会有4！=24个不同的路线，我们只要列举出每一条路线并分别计算出相应的费用即可。

从中就可以找出最小费用及对应的路线。

（三）算法复杂度：O(n!)（四）算法评价优点：可得到精确值。

当n较小时，是可行的；缺点：较笨拙，由于须列举所有情况，且记录下每次的情况，需要大量的机时和内存空间。

当n较大时，该算法是不可行性的。

二、贪心法贪心法是一种对某些求最优解问题的更简单、更迅速的设计方法。

（一）引言在给出贪心法的具体定义和算法步骤之前，我们先来看两个例子。

例1 假设有4种硬币，它们的面值分别为1角、5分、2分和1分。

现要找给某顾客3角7分钱，这时，我们几乎不假思索地拿出3个l角、1个5分和1个2分的硬币交给顾客。

我们不仅能很快决定要拿哪些硬币，而且与其它找法相比．我们拿出的硬币的个数肯定是最少的。

在这里，我们实际使用了这样的算法：首先选出一个面值不超过3角7分的最大硬币(1角)，然后从3角7分中减去1角，剩下2角7分再选出一个不超过2角7分的最大硬币(另一个1角)，如此做下去，直到找足3角7分。

例2 如图1—1，其中，顶点可解释为城市，边上的代价可解释为两城市问的里程。

在图中找一条经过所有结点一次的回路，并使里程的总和为最小。

这同样还是货郎担问题。

在解此题时，我们可以按这样一个想法去做：首先在图中选一条代价最小的边。

为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点：1)不会有三条边(候选边及已入选边)与同一顶点相关联。

2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。

在满足以上两点的候选边中，挑选最短的边作为入选边。

如此做下去，直到得到一个经过所有顶点的回路。

第三讲穷举法一、穷举法的基本概念穷举方法是基于计算机特点而进行解题的思维方法。

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

这样解决问题的方法我们称之为穷举算法。

穷举算法特点是算法简单，但运行时所花费的时间量大。

有些问题所列举出来的情况数目会大得惊人，就是用高速的电子计算机运行，其等待运行结果的时间也将使人无法忍受。

因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。

二、穷举算法模式穷举算法模式：(1)问题解的可能搜索的范围：用循环或循环嵌套结构实现(2)写出符合问题解的条件。

(3)能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。

三、使用穷举法设计算法穷举法应用很多，比如一些密码破译软件通常就是用的穷举算法。

如在QQ上，OicqPassOver这个工具穷举你的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。

下面我们来以三个例子说明穷举法的具体应用。

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

分析：(1)本题是一个搜索问题，搜索范围 2～1000，找出该范围内的完全数；(2)完全数必须满足的条件：因子的和等于该数据的本身。

(3)问题关键在于将该数的因子一一寻找出来，并求出因子的和。

程序如下：Program p3_1 ;Var a , b,s :integer ;BeginFor a:=2 to 1000 doBeginS:=0 ;For b:=1 to a -1 doIf a mod b =0 then s:=s+b ; { 分解因子并求和 }If a=s then beginWrite( a, ‘=’ ,1, );For b:=2 to a -1 doIf a mod b=0 then write( ’+’, b );Writeln ;End;End;End.当程序运行后，输出结果：6 = 1 + 2 + 328 = 1 + 2 + 4 + 7 + 14496 =1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248实例二：（第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题）在A，B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20，且每条路段上的距离均为一个整数)。

第16章 穷举算法与实验穷举方法是基于计算机特点而进行解题的思维方法。

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

这样解决问题的方法我们称之为穷举算法。

穷举算法特点是算法简单，但运行时所花费的时间量大。

因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。

虽然穷举法效率并不高，但是适应一些没有明显规律可循的问题的解决。

因为穷举算法就是从所有可能的情况中搜索正确的答案，所以一般可按如下步骤： 第1步: 对于一种可能的情况，列举出来并计算其结果；第2步：判断结果是否满足要求，如果不满足则执行第1步来搜索下一个可能的情况，如果满足要求，则表示寻找到一个正确的答案，执行下一步操作，如寻找其他正确（合适）的答案或者中断循环。

16.1三角形数问题16.1.1 问题描述将 ,F ,E ,D ,C ,B ,A 这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。

求使三角形三条边上的变量之和相等的全部解。

如图就是一个解。

A 6B C 3 1D F 2 4E 516.1.2 问题分析程序引入变量123456,,,,,i i i i i i ，代表,F ,E ,D ,C ,B ,A 并让它们分别顺序取1至6的正整数，在它们互不相同的前提条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。

当这些变量取尽所有的组合后，程序就可得到全部可能的解。

细节见下面的程序。

【程序1】%穷举法解三角形数 for i1=1:6 for i2=1:6 if i1==i2 continue;endfor i3=1:6if i1==i3 || i2==i3continue;endfor i4=1:6if i1==i4 || i2==i4 || i3==i4continue;endfor i5=1:6if i1==i5 || i2==i5 || i3==i5 || i4==i5continue;endfor i6=1:6if i1==i6 || i2==i6 || i3==i6 || i4==i6 || i5==i6continue;endif i1+i2+i4==i1+i3+i6 && i1+i2+i4==i4+i5+i6fprintf ('%6d\n',i1) ;fprintf ('%4d%4d\n',i2,i3) ;fprintf ('%2d%4d%4d\n\n',i4,i5,i6) ;endendendendendendEnd16.1.3 问题讨论按穷举法编写的程序通常不能适应变化的情况。

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

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

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）一一列举可能的解，验证是否是问题的解例题：谁是小偷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说："我不是小偷"。

2.4 进制工具（二）
例如，一列火车可以在1~N这N个车站停车。每次 停车意味着可以多载顾客（不同的车站按照订单收益 不同），这方面可以提高火车的效益；但停车又意味 着时间的耽搁、站内费用的增加（不同的车站耗费不 同），这方面使收入减少。请给出一个策略，让火车 在某些站停车，使得收入最大化。
for (int i=0; i<2N; i++){ 把i解码成N位二进制串 用二进制串计算此次收益情况 如果此次收益大于最大值，则保存此次停车安排 }
2.3 排列工具(四)
给出一个尺寸是任意大小矩形和矩形中任意位置的6 个点，以这6个点为中心的气球先后膨胀：膨胀时触 到矩形的边或其他的气球则停止膨胀。问采用何种顺 序才能使得气球的总横切面积最大？
该如何采用穷举法中的排列工具解决这个问题？)
2.4 进制工具（一）
进制工具来源于k进制数。 k进制从小到大排列 （位数不足补0）时，数字呈现字典序。例如，000, 001, 010, … 111。又例如，000, 001, 002, 010, …, 222 进制状的数据变化各个位置上的数字可以自由变化， 而不像排列组合一样，受到其他位置上的制约 进制工具可以不使用类单独封装数据和方法，而是 直接用数进行循环，然后在循环中解码当前循环数
2.4 进制工具（三）
上述的进制情况是一种特殊情况，更普遍的情况是： 共有N个元素，每个元素可以独立取值0~ni (0<=i<N) 这种情况下，需要进制工具—一个类—来处理遍历 问题 进制工具是一个类CDigital，内部结构是一个数组， 对外接口是一个BOOL next()函数
2.4 进制工具（四）
2.2 组合工具的变种
基于0-1位的组合工具 基于0-1串的组合工具

For i = 100 To 999 取出百位数字 b = i\100 ____ 取出十位数字 s = ____ i \10 mod 10 mod 10 g=i ____ 取出个位数字 h= b^3+s^3+g^3 ____ 计算各位数字立方和 h=i Then Print i 比较，相等则输出 If ____ Next
用穷举法解决问题
穷举法
什么是穷举法？ 1、根据问题中条件，将可能情况一一列举出来 2、通过对这些情况逐个分析和判断，找出符合要求的解
穷举法也叫：列举法、枚举法
鸡兔同笼
枚举腿的数目 改进 2：枚举头的数目 设头数：鸡为 设腿数：鸡为j个，兔为 条，兔为t个， 条， 鸡兔总腿数为L条，总头数为h个 For j = 1 To 100 80 40 40 For t = 1 To 100 L = jj*2+t*4 +t h=j /2+t/4 j+t If L = 100 And h = 40 Then Print j/2; j; t t/4 End If Next t Next j 循环需要执行： 100*100=10000次 改进1：鸡最多有80个腿 循环执行80*100=8000次
循环次数为40次。80 Nhomakorabea例1、鸡和兔在一个笼里，共有100条腿， 40个头，问鸡、兔各有几只? 改进2：枚举头的数目 设头数：鸡为j个，兔为t个， 鸡兔总腿数为L条，总头数为h个 鸡最多40个头，兔子也是40个头 循环执行：40*40=1600次 改进3：枚举头的数目 设头数：鸡为j个，则兔为40-j个， 鸡兔总腿数为L条，总头数为h个， 鸡最多40个头，兔对应头数为40-j 循环次数为40次
水仙花数(穷举法）

例2：打印出所有的“水仙花数”。所谓“水仙花 数”是指一个三位正整数，其各位数字的立方和 等于该数本身，例如：153=13+53+33 。 • 穷举范围：即把所有的三位正整数100~999按题 意一一进行判断。 • 判断式：如果一个三位正整数n的百位、十位、 个位上的数字分别为i、j、k，则判断式为： n = i3 + j3 + k3 • 如何分解三位数n的百位、十位、个位： 百位：i = n/100; 十位：j = ( n/10 )%10; 个位：k = n%10;
main( ) { int x, y, z, j=1; printf("Possible solutions to buy 100 fowls whith 100 wen:\n"); for (x=0; x<=20; x++) for (y=0; y<=33; y++) { z=100-x-y; if (z%3==0&&5*x+3*y+z/3==100) { printf("%2d:cock=%-2d hen=%-2d chicken=%-2d\n", j, x, y, z); j++;} } }
穷举法
(Complete Search )
概述
• 穷举法的基本思想是不重复、不遗漏地穷举所有 可能情况(问题的规模不是特别大)，从中寻找满 足条件的结果。 • 穷举法充分利用了计算机处理的高速特性，避免 复杂的逻辑推理过程，使问题简单化。 • 使用穷举法的关键是要确定正确的穷举的范围和 满足判断式。
3 5 8 7 4 6
６．陈婷有一个E－MAIL邮箱的密码是一个5位数。 但因为有一段比较长的日子没有打开这个邮箱了， 陈婷把这个密码给忘了。不过陈婷自己是8月1日 出生，而她妈妈的生日则是9月1日，她特别喜欢 把同时是81和91的倍数用作密码。陈婷还记得这 个密码的中间一位(百位数)是1。你能设计一个程 序帮她找回这个密码吗？ 7.有5只猴子分桃子，第一只猴子先去分，把

特殊解题方法——穷举法解答某些数学题，可以把问题所涉及到的数量或结论的有限种情况，不重复不遗漏地全部列举出来，以达到解决问题的目的。

这种解题方法就是穷举法。

例1 从甲地到乙地有A、B、C三条路线，从乙地到丙地有D、E、F、G四条路线。

问从甲地经过乙地到达丙地共有多少条路线？（如图3．28）分析：从甲地到乙地有3条路线，从乙地到丙地有4条路线。

从甲地经过乙地到达丙地共有下列不同的路线。

解：3×4＝12答：共有12条路线。

例2 如果一整数，与1、2、3这三个数，通过加减乘除运算（可以添加括号）组成算式，能使结果等于24，那么这个整数就称为可用的。

在4、5、6、7、8、9、10、11、12这九个数中，可用的有_______个。

（1992年小学数学奥林匹克初赛试题）分析：根据题意，用列式计算的方法，把各算式都列举出来。

4×（1＋2＋3）＝24 （5＋1＋2）×3＝246×（3＋2－l）＝24 7×3十豆十2—248×3×（2－1）＝24 9×3—1—2—2410×2＋l＋3＝24 11×2＋3－l＝2412×（3＋1－2）＝24通过计算可知，题中所给的9个数与1、2、3都能够组成结果是24的算式。

答：可用的数有9个。

例3 从0、3、5、7中选出三个数字能排成_______个三位数，其中能被5整除的三位数有_________个。

（1993年全国小学数学竞赛预赛试题）分析：根据题中所给的数字可知：三位数的百位数只能有三种选择：十位数在余下的三个数字中取一个数字，也有3种选择；个位数在余下的两个数字中取一个数字，有2种选择。

解:把能排成的三位数穷举如下，数下标有横线的是能被5整除的。

305，307，350，357，370，375；503，507，530，537，570，573；703，705，730，735，750，753答：能排成18个三位数，其中能被5整除的有10个数。

穷举算法穷举，又叫枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是能使命题成立，即为其解。

应用到程序中，枚举有许多表现形式，比如把所有的组合都扫描一遍，找出符合要求的组合。

举个简单的例子，找素数。

1什么都不是，2是素数，3是，4不是，5是……，如此把所有的自然数（当然是不可能的，只能尽量多）都找一遍，就能找出所有的素数。

可以这么说，枚举是最简单，最基础，也是最没效率的算法，但是。

枚举拥有很多优点，以致于他能够活到现在而不被淘汰。

首先，枚举有超级无敌准确性，只要时间足够，正确的枚举得出的结论是绝对正确的。

其次，枚举拥有天下第一全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。

例：找偶数。

【题目一】把一元钞票换成一分、二分、五分硬币（每种至少一枚），有哪些种换法？【答案】461种提示：for i:=1 to 93 dofor j:=1 to 47 dofor k:=1 to 19 doif 100=i+2*j+5*k then n:=n+1;还有没有效率更高的算法呢？留给大家考虑。

【题目二】将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.分析：这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。

此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：for a:=1 to 9 dofor b:=1 to 9 do………for i:=1 to 9 do这样下去，枚举次数就有9９次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为９３，在细节上再进一步优化，枚举范围就更少了。

【题目三】：穷举法中穷举方案的选择：陈婷有一个E-MAIL邮箱的密码是一个5位数。

但因为有一段比较长的日子没有打开这个邮箱了，陈婷把这个密码给忘了。