《信息奥赛—穷举》由会员分享，可在线阅读，更多相关《信息奥赛—穷举（56页珍藏版）》请在金锄头文库上搜索。
1、穷穷 举举 OicqPassOver这个工具可以用来探测QQ 的口令，它根据机器性能最高可以每秒测试 20000个口令，如果口令简单，一分钟内， 密码就会遭到破译。 这些密码破译软件通常就是用的 穷举算法。 穷举的策略应该是直接基于计算机 特点而使用的思维方法，在一时找不 到解决问题的更好途径（比如数学公 式或规律规则）时，可以根据问题中 的部分（约束）条件，将可能解的情 况列举出来，然后一一验证是否符合 整个问题的求解要求。 实例：编一个程序找出三位数到七位数中所 有的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数 ,它的定义如下:若一个n位自然数的各位数字的n 次方之和等于它本身,则称这个自然数为
2、阿姆斯 特朗数。例如153(153=1*1*1+3*3*3+5*5*5) 是一个三位数的阿姆斯特朗数,8208则是一个四 位数的阿姆斯特朗数。 算法描述： for I:=100 to 9999999 do begin 验证是否是阿姆斯特朗数，若是则输出； end; 钞票换硬币 把一元钞票换成一分、二分、五分硬币（每种 至少一枚），有哪些种换法？ 461种 var i,j,k,total:integer; begin total:=0; 总数设为 for i:=1 to 99 do i:二分硬币最多99枚 for j:=1 to 49 do j:二分硬币最多49枚 for k:=1 to 19
3、do k:五分硬币最多19枚 if i*1+j*2+k*5=100 then begin writeln(i:3,j:3,k:3); inc(total); 总数加 end; writeln(total); readln; end. 百钱买百鸡 【题目】一只公鸡值元，一只母鸡值元， 只小鸡值元，现用一百元要买一百只鸡。问有 什么方案？ 这是一个古典数学问题，设一百只鸡中公鸡、母鸡、 小鸡分别为x，y，z，问题化为三元一次方程组： 这里x,y,z为正整数，且z是3的倍数；由于鸡和钱的总数 都是100，可以确定x,y,z的取值范围： 1) x的取值范围为120 2) y的取值范围为133 3) z
4、的取值范围为399，步长为3 对于这个问题我们可以用穷举的方法，遍历x,y,z的所有 可能组合，最后得到问题的解。 下式算式中不同的字母代表不同的数字，编程 打印出下列算式 A+BC+DEF=GHIJ 可以确定d=9,g=1,h=0. 分书问题 有、五本书，要分给张 、王、刘、赵、钱五位同学，每人只能选一本, 事先让每人把自己喜爱的书法填于右表，编程 找出让每人都满意的方案。 A B C D E 张 王 刘 赵 钱 张 王 刘 赵 钱 var z,w,l,zh,q,total:byte; procedure output; begin writeln(zhang:,chr(z+64); wri
5、teln(wang:,chr(w+64); writeln(liu :,chr(l+64); writeln(zhao:,chr(zh+64); writeln(qian:,chr(q+64); writeln; inc(total); end; begin total:=0; for z:=3 to 4 do for w:=1 to 5 do if (w3) and (w4) then for l:=2 to 3 do for zh:=1 to 4 do if zh3 then for q:=2 to 5 do if (q3) and (q4) then begin if z+w+l+zh+
6、q=15 then if z*w*l*zh*q=120 then output; end; write(total); end. 实例：砝码称重（NOIP T96-4） 设有1g、2g、3g、5g、10g、20g的砝码各若干枚（ 其总重=1000），输出用这些砝码能称出的不同重量 的个数，但不包括一个砝码也不用的情况。 算法分析：最容易想到的方法就是枚举出有 几个1g，几个2g，几个3g几个20g，然 后统计有几种不同的重量。用数组w1w6 表示砝码的重量，q1q6表示选择方案。 Total:array0.1000of integer; fillchar(total,sizeof(total)
7、,0); for q1:=0 to a1 do for q2:=0 to a2 do for q3:=0 to a3 do for q4:=0 to a4 do for q5:=0 to a5 do for q6:=0 to a6 do begin sum:=0; For i:=1 to 6 do sum:=sum+qi*wi; if sum=1。要求由小到大依次在 同一行输出这三个实根(根与根之间留有空格) ，并精确到小数点后2位。 样例 输入：1 -5 -4 20 输出：-2.00 2.00 5.00 穷举法应用 本题是2001年全国信息学奥林匹克 竞赛高中组复赛第一题，如果考虑解方 程的
8、话则比较麻烦。我们可以换个角度 思考问题，在-100到100之间找三个满 足方程的实数，由于穷举时必须用整型 变量，题目又要求保留两位小数，我们 只需将循环变量扩大100倍即可顺利穷 举，最后只要将所求结果再缩小100倍 即可。 For i:=-10000 To 10000 Do Begin x:=i/100; If Then If ix1 Then x1:=i Else If ix2 Then x2:=i Else If ix3 Then x3:=i;确保x1x2x3 End; Writeln(x1/100:0:2, ,x2/100:0:2, ,x3/100:0:2); End. Abs(a
9、*x*x*x+b*x*x+c*x+d)0.000001 筛法求素数 用筛选法实现求N以内的所有素数(就是质数)。 并按每行10个数的形式打印出来.n=25时,用筛 选法选素数的过程如下: (1) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 (2) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 (3) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 (4
10、) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 (5) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 首先确定2是素数,接着把凡是2的倍数的那 些数筛去,过程见步骤(2),其中带有删除线的数就 是被筛去的数.接着把凡是3的倍数的那些数筛去 , 过程见步骤(3). 接着把凡是4的倍数的那些数 筛去, 过程见步骤(4).接着把凡是5的倍数的那些 数筛去, 过程见步骤(5).这时数列中剩下的未被 筛去那些数就都是素数. 筛选法找素数的过
11、程实际上是一个去合数的过程,显然所 有被去掉的数都是合数,那么上述的筛选步骤到底 要做到第几步才能保证没有合数剩下来呢? 沿用前面的质数判断定理,因为任何一个合数一定有一个 因子的平方小于等于它本身,所以对任意的n,只要将所有的 i(i*i=n)的倍数筛去, 就能保证没有一个合数剩下来.如n=25 时, 筛去5的倍数后就不用再往下做了.为了实现以上算法我们 首先可以把2到n这n-1个自然数放在一个数组中,可以用各种 方法来表示数组元素中的值已被筛去,例如给数组元素置0或 负数. 筛法求素数 const maxn=1000; var i,j,n:integer; prime:array 2.ma
12、xn of integer; begin write(Input n:); readln(n); for i:=2 to maxn do primei:=1; i:=2; while i*i=n do begin j:=i*2; while j=n do begin primej:=0; j:=j+i end; i:=i+1 end; for i:=2 to n do if primei=1 then write(i:8); writeln end. 实例：4皇后问题。 问题描述：在44的棋盘上安置4个皇 后，要求任意两个皇后不在同一行、不 在同一列、不在同一对角线上，输出所 有的方案。 实例
13、三：4皇后问题。 问题描述：在44的棋盘上安置4个皇 后，要求任意两个皇后不在同一行、不 在同一列、不在同一对角线上，输出所 有的方案。 S1:第一行皇后的列号 S2:第二行皇后的列号 4皇后问题 Q2Q3 Q1Q2Q3 Q Q3Q2Q1 function check:boolean; var i,j:integer; begin for i:=1 to n-1 do for j:=i+1 to n do if (si=sj)or(abs(i-j)=abs(si-sj) ) then begin check:=false; exit; end; check:=true; end; begin for i1:=1 to n do for i2:=1 to n do
