《鄂教版信息技术九下第6课《逐一罗列穷举算法》ppt课件》由会员分享，可在线阅读，更多相关《鄂教版信息技术九下第6课《逐一罗列穷举算法》ppt课件（45页珍藏版）》请在金锄头文库上搜索。
1、穷举算法,穷举的定义,从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。 一般步骤 l 对命题建立正确的数学模型； l 根据命题确定的数学模型中各变量的变化范围（即可能解的范围）； l 利用循环语句、条件判断语句逐步求解或证明；,使用穷举的条件,可预先确定解的个数n 解变量a1、a2、an的可能值为一个连续的值域,算法归纳,设：ai1-解变量ai的最小值，aik-解变量ai的最大值（1=i=n） a11=a1=a1k a21=a2=a2k ai1=ai=aik an1=an=ank 我们称解变量为穷举变量，即解题过程中需要列举出的变量（
2、很明显，要列举出变量的每个值，我们一般都使用for循环） 例如某问题的穷举变量有三个：a1，a2，a3，其中1=a1=2；2=a2=4；5=a3=7 则可以列出本问题的所有可能解共18组（略） 在上述可能解的集合中，满足问题给定的检验条件的解元素就是问题的可能解 for a1:=a11 to a1k do for a2:=a21 to a2k do for a3:=a31 to a3k do for an:=an1 to ank do if (a1.a2.ai,an)满足检验条件 then 输出问题的解（a1,a2,ai,an）,穷举的优化,枚举法的特点是算法简单，但有时运算量大。 由于穷举是
3、列举出所有的值，当问题规模比较大的时候，运算的时间会变得很长，所以在设计算法时必须尽量减少搜索的范围，经常的做法就是将一组解设置为按小到大的顺序。这样可以避免一个重复出现的解。,百鸡问题,略,找数,将1,2.9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.,分析,这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举： for a:=1 to 9 do for b:=1 to 9 do for i:=1 to 9 do 这样下
4、去，枚举次数就有9次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为，在细节上再进一步优化，枚举范围就更少了。,var t,x:integer; s,st:string; c:char; begin for x:=123 to 321 do枚举所有可能的解 begin t:=0; str(x,st);把整数x转化为字符串，存放在st中 str(x*2,s); st:=st+s; str(x*3,s); st:=st+s; for c:=1 to 9 do枚举9个字符，判断是否都在st中 if pos(c,st)0 then inc(t) else break;如果不在
5、st中，则退出循环 if t=9 then writeln(x, ,x*2, ,x*3); end; end.,一元三次方程求解(noip2001tg),有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。 要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。 提示：记方程f(x)=0，若存在2个数x1和x2，且x1x2，f(x1)*(x2)0，则在(x1，x2)之间一定有一个根。 样例 输入：1 -5 -4 2
6、0 输出：-2.00 2.00 5.00,算法分析,由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解呢？再分析一下题目，根的范围在-100到100之间，结果只要保留两位小数，我们不妨将根的值域扩大100倍（-10000=x=10000），再以根为枚举对象，枚举范围是-10000到10000，用原方程式进行一一验证，找出方程的解。,var k:integer; a,b,c,d,x :real; begin read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if
7、 a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2, ); end; end.,用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。 这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？看到这里大家可能有点迷惑了。 在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入ax3+bx2+cx+d中，所得的结果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作为判断条件是不准确的。
8、,我们换一个角度来思考问题，设f(x)=ax3+bx2+cx+d，若x为方程的根，则根据提示可知，必有f(x-0.005)*(x+0.005)0，如果我们以此为枚举判定条件，问题就逆刃而解。另外，如果f(x-0.005)=0，哪么就说明x-0.005是方程的根，这时根据四舍5入，方程的根也为x。所以我们用(f(x-0.005)*f(x+0.005)0) 和 (f(x-0.005)=0)作为判定条件。为了程序设计的方便，我们设计一个函数f(x)计算ax3+bx2+cx+d的值，程序如下：,var k:integer; a,b,c,d,x:extended; function f(x:extend
9、ed):extended; 计算ax3+bx2+cx+d的值 begin f:=(a*x+b)*x+c)*x+d; end; begin read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if (f(x-0.005)*f(x+0.005)0) or (f(x-0.005)=0) then write(x:0:2, ); 若x两端的 函数值异号或x-0.005刚好是方程的根，则确定x为方程的根 end; end.,将19这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍, 第三行的三位数
10、是第一行的三倍, 应怎样填数。如图6:,填数,分析,本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。 但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。因此设计参考程序：,尺子刻度（红书231页）,尺子刻度。一根29cm长的尺子只允许上面刻7个刻度。要用它能量出1-29cm的各种长度，试问刻度应该怎样选择？,穷举产生解的可行性判断,1当枚举产生7个刻度值后，哪些长度是能被度量的？ 2如何判断1至29这些长度都能被度量？,1如果长度
11、ai能被度量，则29-ai也能被度量 2如果长度ai能被度量，则abs(ai-aj)也能被度量（ij=7）,答 案,穷举的程序段,for i:=1 to 7 do ai:=0; b29:=1; for a1:=1 to 28 do for a2:=1 to 28 do for a3:=1 to 28 do for a4:=1 to 28 do for a5:=1 to 28 do for a6:=1 to 28 do for a7:=1 to 28 do begin end;,判断解可行性,for i:=1 to 28 do bi:=0; for i:=1 to 7 do begin bai:
12、=1;b29-ai:=1; for j:=i+1 to 7 do babs(aj-ai):=1; end; j:=0; for i:=1 to 29 do j:=j+bi; if j=29 then for i:=1 to 7 do write(ai:4);,优化的分析,1在不漏掉正确解的情况下，我们不妨用a1,a2,a3.a7来分别存放7个不同刻度值，并且按照刻度值递增排列。 2为了能量出刻度1，显然刻度1是必须的，此时利用对称性，28也就可以度量了（而且29是不必有刻度的）。 3以前面1、2二点为基础，我们可以分析出，当有刻度a1,a2.ai(1=i=7)时，则可以量出的尺寸为ak,ak-
13、aj,29-ak|1=k=i,1=j=k-1,即通过a1,a2.a7可以量出的尺寸为：,a1,29-a1 a2, a2-a1,29-a2 a3,a3-a1,a3-a2,29-a3 a4,a4-a1,a4-a2,a4-a1,29-a4 a7,a7-a1,a7-a2,a7-a3,a7-a4,a7-a5,a7-a6,29-a7,缩小范围的界定,仅考虑aiai+1 ，且设定a1=1,其他枚举变量ai的值域范围为：ai-1ain-(7-i+2)（其中n-(7-i+2)为根据对称性确定的最大值，因为当a1=1时，28已经可以量出，所以a7的最大值不必为29，而应为29-2，又因为a6a7，所以a6的最大值
14、为a7-1=29-3,依次类推即可得。）。,优化后的程序结构,n:=29;a1:=1; for a2:=2 to n-7 do for a3:=a2+1 to n-6 do for a4:=a3+1 to n-5 do for a5:=a4+1 to n-4 do for a6:=a5+1 to n-3 do for a7:=a6+1 to n-2 do if 满足条件then 输出方案；,例题,来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况是, 没有人既会日语又会法语;A会日语,但D不会,A和D能互相交谈,B不会英语,但A和C交谈时却要B当翻译
15、,B,C,D三个想互相交谈,但找不到共同的语言,只有一种语言3人都会,编程确定A,B,C,D四位留学生各会哪两种语言。,分析：将中、法、日、英四种语言分别定义为CHN、FRH、JPN、ENG,则四种语言中取两种共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),( ENG,FRH),( ENG,JPN),(FRH,JPN)六种组合，分别定义为1、2、3、4、5、6。据已知，没有人既会日语又会法语;因此，组合6不会出现；A 会日语，所以A只可能等于3、5；D不会日语, 所以D只可能等于1、2、4；B不会英语，所以B只可能等于2、3；,type Language = (CHN,ENG,
16、FRH,JPN); TNoSet= set of Language; const No: array 1 5 of TNoSet= (CHN,ENG, CHN,FRH, CHN,JPN, ENG,FRH, ENG,JPN); var A, B, C, D: 1 5; Can1, Can2, Can3, Can4: Boolean; function Might(Lang: Language): Boolean; var Bool: Boolean; begin Bool:=false; if NoA * NoA * NoC = Lang then Bool := True; if NoA * NoB * NoD = Lang then Bool := True; if NoA
