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

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

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

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

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

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

二、穷举算法模式穷举算法模式：(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，且每条路段上的距离均为一个整数)。

A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。

通路上路段距离之和称为通路距离(最大距离≤1000)。

当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。

例如：下图所示是当N=1时的情况：从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。

算法说明：本题采用穷举算法。

数据结构：N：记录A，B间路站的个数数组D(I，0)记录第I-1到第I路站间路段的个数D(I，1)，D(I，2)，…记录每个路段距离数组G记录可取到的距离PROGRAM CHU7_6；VAR I，J，N，S：INTEGER；B：ARRAY[0..100]OF INTEGER；D：ARRAY[0..100，0..20]OF INTEGER；G ：ARRAY[0..1000]OF 0..1；BEGINREADLN(N)；FOR I:=1 TO N+1 DOBEGINREADLN(D[I，0])；FOR J:=1 TO D[I，0]DO READLN(D[I，J])；END；D[0，0]:=1；FOR I:=1 TO N+1 DO B[I]:=1；B[0]:=0；FOR I:=0 TO 1000 DO G[I]:=0；WHILE ①DOBEGINS:=0；FOR I:=1 TO N+1 DOS:= ②G[S]:=1；J:=N+1；WHILE ③DO J:=J-1；B[J]:=B[J]+1；FOR I:=J+1 TO N+1 DO B[I]:=1；END；S:=0；FOR I:=1 TO 1000 DO④；WRITELN(S)；READLN；END.答案：① B[0]=0② S+D[I,B[I]]; ③ B[J]=D[J,0] ④S:=S+G[I]实例三（第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题）将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2问题求解:求出一种分法,使P为最小(若有多种方案仅记一种)程序说明:数组:a[1],a[2],...A[N]存放原数s[1],s[2],...,s[K]存放每个部分的和b[1],b[2],...,b[N]穷举用临时空间d[1],d[2],...,d[N]存放最佳方案程序:program exp4;Var i,j,n,k : integer;a :array [1..100] of integer;b,d:array [0..100] of integer;s :array[1..30] of integer;beginreadln(n,k);for I:=1 to n do read(a[I]);for I:=0 to n do b[I]:=1;cmin:=1000000;while (b[0]=1) dobeginfor I:=1 to k do ①for I:=1 to n do②sum:=0;for I:=1 to k-1 dofor j:= ③sum:=sum+(s[I]-s[j])*(s[I]-s[j]);if ④ thenbegincmin:=sum;for I:=1 to n do d[I]:=b[I];end;j:=n;while ⑤ do j:=j-1;b[j]:=b[j]+1;for I:=j+1 to n do ⑥end;writeln(cmin);for I:=1 to n do write(d[I]:40);writeln;end.四、穷举算法的深入应用实例一：一根29厘米长的尺子, 只允许在上面刻七个刻度, 要能用它量出1～29 厘米的各种长度。

试问这根尺的刻度应该怎样选择?分析：(1) 从1～29 厘米中选择七个刻度的所有可能情况数是:C7 29= 29·28·26·25·24·23 = 29·9·26·5·2·23= 29·26·23·90= 15607801·2·3·4·5·6·7(2) 对于每一组刻度的选择都需要判断是否能将1～29 厘米的各种刻度量出来, 例如选择的刻度为: a1,a2,a3,a4,a5a,6,a7 那么能量出的刻度为：a1, 29-a1; 2a2, a2-a1, 29-a2; 3a3, a3-a1 ,a3-a2, 29-a3 ; 4a4, a4-a1, a4-a2, a4-a3, 29-a4; 5a5, a5-a1, a5-a2, a5-a3, a5-a4, 29-a5; 6a6, a6-a1, a6-a2, a6-a3, a6-a4, a6-a5, 29-a6; 7a7-a1, a7-a2, a7-a2, a7-a3, a7-a4, a7-a5, a7-a6, 29-a7; 8 共可量出2+3+4+5+6+7+8 种刻度, 即35 种刻度, 事实上其中有许多刻度是重复的, 不可能复盖1～29。

例如：取a1, a2, a3, a4, a5, a6, a7为1, 3, 6, 10, 15, 21, 28能量出的刻度为：1 , 283, 2, 266, 5, 3, 2310, 9, 7, 4, 1915, 14, 12, 9, 5, 1421, 20, 18, 15, 11, 6, 828, 27, 25, 22, 18, 13, 7, 1缺16,17,24 ( 29 即尺子长度)如果找出了刻度a1, a2, a3, a4, a5, a6, a7 那么我们可以利用其对称性29-a1,29-a2,29-a3,29-a4,29-a5,29-a6,29-a7, 也是一组解, 所以求解过程中可仅考虑a1<a2<a3<a4<a5<a6<a7 的情况。

很显然要使1,28 两种刻度能量出来, 则在七个刻度就必须有 1 或28; 这样就可设a1=1 ( 或a1=28 )。

本题就变成了只要在2～27 中选取六个刻度问题了。

其刻度选择的数目为C6= 26·25·24·23·22·21 = 26·5·23·11·7 = 230230261·2·3·4·5·6这样解的范围就从百万变成了十万的数量级, 大大减少运行次数。

因此，我们在用穷举法求问题解时，应注意程序的优化，尽可能减少搜索时间。

{ 程序优化}(3) 为了判定七个刻度是否能够度量1～29的所有长度, 可以用集合的方法, 也可以用数组的0，1数据判断。

下面的程序使用了数组的0，1方法。

Program p12_2 ;Const n=29 ; m=1;Var a：array [1..7] of integer;b：array [1..n] of 0..1 ; { 记录能量的刻度}f：Boolean ;I , j ：integer ;BEGINa[1]:=m;for a[2]:=2 to n-7 dofor a[3]:=a[2]+1 to n-6 dofor a[4]:=a[3]+1 to n-5 dofor a[5]:=a[4]+1 to n-4 dofor a[6]:=a[5]+1 to n-3 dofor a[7]:=a[6]+1 to n-2 dobeginfor i:=1 to 29 do b[i]:=0;for i:=1 TO 7 dobeginb[a[i]]:=1; b[n-a[i]]:=1; b[n]:=1 ; { 初始化}for j:=i+1 TO 7 do b[abs(a[j]-a[i])]:=1end;j: =0;for i;=1 to n do j:=j + b[i];if j=n then beginfor i:=1 to 7 do write (a[i]:4);writeln ;end ;end;end.运行程序的结果: 当m=1 时得出两组刻度1 2 14 18 21 24 271 4 10 17 22 24 27m=28 时也可获得两组刻度28 2 5 7 13 19 2528 2 5 8 11 15 27这两组刻度实际上是m=1 的对称情况, 所以问题的解实质上为两组结果。