发布网友 发布时间:2024-08-17 23:34
共1个回答
热心网友 时间:2024-08-17 23:45
在进行归纳推理时,如果逐个考察了某类事件的所有可能情况,因而得出一般结论,那么这结论是可靠的,这种归纳方法叫做枚举法. 一、特点:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,合适就保留,不合适就丢弃。例如: 找出1到100之间的素数。需要将1到100之间的所有整数进行判断。 枚举算法因为要列举问题的所有可能的答案,所有它具备以下几个特点: 1、得到的结果肯定是正确的; 2、可能做了很多的无用功,浪费了宝贵的时间,效率低下。 3、通常会涉及到求极值(如最大,最小,最重等)。 二、枚举算法的一般结构:while循环。 首先考虑一个问题:将1到100之间的所有整数转换为二进制数表示。 算法一: for i:=1 to 100 do begin 将i转换为二进制,采用不断除以2,余数即为转换为2进制以后的结果。一直除商为0为止。 end; 算法二:二进制加法,此时需要数组来帮忙。 program p; var a:array[1..100] of integer; {用于保存转换后的二进制结果} i,j,k:integer; begin fillchar(a,sizeof(a),0); {100个数组元素全部初始化为0} for i:=1 to 100 do begin k:=100; while a[k]=1 do dec(k); {找高位第一个为0的位置} a[k]:=1; {找到了立刻赋值为1} for j:=k+1 to 100 do a[j]:=0; {它后面的低位全部赋值为0} k:=1; while a[k]=0 do inc(k); {从最高位开始找不为0的位置} write('(',i,')2='); for j:=k to 100 do write(a[j]); {输出转换以后的结果} writeln; end; end. 枚举法乎丛,常常称之为穷举法,是指从可能的集合中一一枚举各个元素,用题目给定的约束条件判定哪些是无用的,哪些是有用的。能使命题成立者,即为问题的解。 采用枚举算法解题的基本思路: (1) 确定枚举对象、枚举范围和判定条件; (2) 一一枚举可能的解,验证是否是问题的解 下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定,这三个方面来探讨余旁如何用枚举法解题。 例1:百钱买百鸡问题:有一个人有一百块钱,打算买一百只鸡。到市场一看,大鸡三块钱一只,小鸡一块钱三只,不大不小的鸡两块钱一只。现在,请你编一程序,帮他计划一下,怎么样买法,才能刚好用一百块钱买一百只鸡? 算法分析:此题很显然是用枚举法,我们以三种鸡的个数为枚举对象(分别设为x,y,z),以三种鸡的总数(x+y+z)和买鸡用去的钱的总数(x*3+y*2+z div 3=100)为判定条件,穷举各种鸡的个数。 下面是解这个百鸡问题的程序 var x,y,z:integer; begin for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do{枚举所有可能的解} if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z); {验证可能的解,并输出符合题目要求的解} end. 上面的条件还有优化的空间,三种鸡的和是固定的,我们只要枚举二种鸡(x,y),第三种鸡就可以根据约束条件求得(z=100-x-y),这样就缩小了枚举范围,请看下面的程序: var x,y,z:integer; begin for x:=0 to 100 do for y:=0 to 100-x do begin z:=100-x-y; if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z); end; end. 未经优化的岁毁樱程序循环了1013 次,时间复杂度为O(n3);优化后的程序只循环了(102*101/2)次 ,时间复杂度为O(n2)。从上面的对比可以看出,对于枚举算法,加强约束条件,缩小枚举的范围,是程序优化的主要考虑方向。 在枚举算法中,枚举对象的选择也是非常重要的,它直接影响着算法的时间复杂度,选择适当的枚举对象可以获得更高的效率。如下例: 例2、将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数. 例如:三个三位数192,384,576满足以上条件。(NOIP1998pj) 算法分析:这是1998年全国分区联赛普及组试题(简称NOIP1998pj,以下同)。此题数据规模不大,可以进行枚举,如果我们不加思地以每一个数位为枚举对象,一位一位地去枚举: for a:=1 to 9 do for b:=1 to 9 do ……… for i:=1 to 9 do 这样下去,枚举次数就有99次,如果我们分别设三个数为x,2x,3x,以x为枚举对象,穷举的范围就减少为93,在细节上再进一步优化,枚举范围就更少了。程序如下: var x,a,b,c:integer; begin for x:=1 to 9 do{枚举所有可能的解} begin a:=x; b:=2x; c:=3x; if (a+b+c=100)and(a*100+b*10+c=192)and(b*10+c=384)and(c=576)then writeln('a=',a,'b=',b,'c=',c); end; end. 在枚举法解题中,判定条件的确定也是很重要的,如果约束条件不对或者不全面,就穷举不出正确的结果, 我们再看看下面的例子。 例3 一元三次方程求解(noip2001tg) 问题描述 有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值>=1