资源预览内容
第1页 / 共56页
第2页 / 共56页
第3页 / 共56页
第4页 / 共56页
第5页 / 共56页
第6页 / 共56页
第7页 / 共56页
第8页 / 共56页
第9页 / 共56页
第10页 / 共56页
亲,该文档总共56页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
穷穷 举举 OicqPassOver这个工具可以用来探测QQ 的口令,它根据机器性能最高可以每秒测试 20000个口令,如果口令简单,一分钟内, 密码就会遭到破译。 这些密码破译软件通常就是用的 穷举算法。 穷举的策略应该是直接基于计算机 特点而使用的思维方法,在一时找不 到解决问题的更好途径(比如数学公 式或规律规则)时,可以根据问题中 的部分(约束)条件,将可能解的情 况列举出来,然后一一验证是否符合 整个问题的求解要求。 实例:编一个程序找出三位数到七位数中所 有的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数 ,它的定义如下:若一个n位自然数的各位数字的n 次方之和等于它本身,则称这个自然数为阿姆斯 特朗数。例如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 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的取值范围为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); writeln(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+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),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年全国信息学奥林匹克 竞赛高中组复赛第一题,如果考虑解方 程的话则比较麻烦。我们可以换个角度 思考问题,在-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*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) 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).这时数列中剩下的未被 筛去那些数就都是素数. 筛选法找素数的过程实际上是一个去合数的过程,显然所 有被去掉的数都是合数,那么上述的筛选步骤到底 要做到第几步才能保证没有合数剩下来呢? 沿用前面的质数判断定理,因为任何一个合数一定有一个 因子的平方小于等于它本身,所以对任意的n,只要将所有的 i(i*i=n)的倍数筛去, 就能保证没有一个合数剩下来.如n=25 时, 筛去5的倍数后就不用再往下做了.为了实现以上算法我们 首先可以把2到n这n-1个自然数放在一个数组中,可以用各种 方法来表示数组元素中的值已被筛去,例如给数组元素置0或 负数. 筛法求素数 const maxn=1000; var i,j,n:integer; prime:array 2.maxn 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个皇 后,要求任意两个皇后不在同一行、不 在同一列、不在同一对角线上,输出所 有的方案。 实例三: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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号