现在的位置: 首页 > 综合 > 正文

穷举法

2013年10月13日 ⁄ 综合 ⁄ 共 1513字 ⁄ 字号 评论关闭

枚举法,常常称之为穷举法,是指从可能的集合中一一枚举各个元素,用题目给定的约束条件判定哪些是无用的,哪些是有用的。能使命题成立者,即为问题的解。

采用枚举算法解题的基本思路:
(1)    确定枚举对象、枚举范围和判定条件;
(2)    一一枚举可能的解,验证是否是问题的解
下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定,这三个方面来探讨如何用枚举法解题。
例1:百钱买百鸡问题:有一个人有一百块钱,打算买一百只鸡。到市场一看,大鸡三块钱一只,小鸡一块钱三只,不大不小的鸡两块钱一只。现在,请你编一程序,帮他计划一下,怎么样买法,才能刚好用一百块钱买一百只鸡?
算法分析:此题很显然是用枚举法,我们以三种鸡的个数为枚举对象(分别设为x,y,z),以三种鸡的总数(x+y+z)和买鸡用去的钱的总数(x*3+y*2+z)为判定条件,穷举各种鸡的个数。
下面是解这个百鸡问题的程序

 

上面的条件还有优化的空间,三种鸡的和是固定的,我们只要枚举二种鸡(x,y),第三种鸡就可以根据约束条件求得(z=100-x-y),这样就缩小了枚举范围,请看下面的程序:

 

程序循环了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
  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;{如果不在st中,则退出循环}
      if t=9 then   writeln(x,' ',x*2,' ',x*3);
  end;
end.
本文转自:http://blog.chinaunix.net/u/18135/showart_173867.html

抱歉!评论已关闭.