Pascal 穷举.ppt

《Pascal 穷举.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、穷举法2008夏令营执教：江苏省丹阳高级中学荆晓虹一、引入实例一：编一个程序找出三位数到七位数中所有的阿姆斯特朗数。阿姆斯特朗数也叫水仙花数,它的定义如下:若一个n位自然数的各位数字的n次方之和等于它本身,则称这个自然数为阿姆斯特朗数。例如153(153=1*1*1+3*3*3+5*5*5)是一个三位数的阿姆斯特朗数,8208则是一个四位数的阿姆斯特朗数。穷举法算法分析：程序只能采用穷举法,一一验证范围内的数是否阿姆斯特朗数,若是则打印之。一、引入算法描述：forI:=100to9999999dobegin验证是否是阿姆斯特朗数，若是则输出；end;穷举

2、法一、引入实例二：从键盘输入一个正整数N，验证其是否为质数，若是则输出“YES”，否则输出“NO”。穷举法算法分析：程序采用穷举法,一一验证范围内的数是否是N的因子,若是做标记。一、引入算法描述：Read(n);forI:=2ton-1dobegin验证i是否是n的因子，若是则做标记；end;穷举法二、穷举法的基本概念穷举法穷举方法是基于计算机特点而进行解题的思维方法。穷举算法特点是算法简单，但运行时所花费的时间量大。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。根据问题中的的部分条件（约束条件）将所有可

3、能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。三、穷举算法模式穷举法1、问题解的可能搜索范围：用循环或循环嵌套结构实现3、能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。forI:=100to9999999do2、写出符合问题解的条件。forI:=2ton-1do四、穷举法应用穷举法穷举法应用很多，比如一些密码破译软件通常就是用的穷举算法。如在QQ上，OicqPassOver这个工具穷举你的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。下面我们来以两个例子说明穷举

4、法的基本应用。实例二：有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。样例输入：1  -5  -4  20输出：-2.00  2.00  5.00四、穷举法应用本题是2001年全国信息学奥林匹克竞赛高中组复赛第一题，如果考虑解方程的话则比较麻烦。我们可以换个角度思考问题，在-100到100之间找三个满足方程的实数，由于穷

5、举时必须用整型变量，题目又要求保留两位小数，我们只需将循环变量扩大100倍即可顺利穷举，最后只要将所求结果再缩小100倍即可。四、穷举法应用程序如下：Vara,b,c,d,x:real;i,x1,x2,x3:Integer;BeginRead(a,b,c,d);x1:=MaxInt;x2:=x1;x3:=x1;四、穷举法应用Fori:=-10000To10000DoBeginx:=i/100;IfThenIfi

6、(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四、穷举法应用穷举法实例三：学校名次。问题描述：有A，B，C，D，E5所学校。在一次检查评比中，已知E校肯定不是第2名或第3名，他们互相进行推测。A校有人说，E校一定是第1名；B校有人说，我校可能是第2名；C校有人说，A校最差；D校有人说，C校不是最好的；E校有人说，D校会获第1名。结果只有第1名和第2名学校的人猜对了。编程指出这5所学校的名次。四、穷举法应用穷举法分析：本题是一个逻辑判

7、断题，一般的逻辑判断题都采用穷举法进行解决。我们对5所学校所得名次的各种可能情况进行穷举。在每种情况中，为了防止不同学校取相同的名次，设立了逻辑数组x，x[I]为false表示已有某校取第I名。此题的难点在于确定判断条件。我们设立逻辑变量b0来描述这一条件，主要有两个条件：“E校不是第2名或第3名”与“只有第1名和第2名的学校的人猜对”，后一条件要判断：1）是否只有两人说法正确？2）说得正确的人是否是取得第1名和第2名的学校的人？要判断是否仅有两人说正确，须统计正确命题的个数。为此，设立了函数bton，将逻辑量数值化。四、穷举法应用穷举法程序：progr

8、aml3(output);vari,a,b,c,d,e,m:integer;x: