资源简介

(共14张PPT)
枚举算法及其程序实现
图灵机
为现代计算机的逻辑工作方式奠定了基础。
图灵测试
用于判定机器是否具有智能的试验方法，是人工智能领域的先驱。
破译二战密码
二战期间，协助军方破解了德国著名的密码系统：英格玛(Enigma),，使战争提前两年结束，拯救了至少2千万人民的性命。
图中的人你认识吗？他有哪些贡献？
...
计算机科学与人工智能之父：艾伦·麦席森·图灵
第1位：
10以内的一个正整数。
破译密码大比拼！
打开桌面上的密码验证小程序，根据上面的提示进行密码破解。
第2、3位：
一个2位的质数
第4、5、6位：
一个三位平方数并且还是回文数。
第7、8、9、10位：
第515个质数。
7
73
676
？
枚举算法
逐一列举
针对要解决的问题，逐一列举它所有可能的情况。
逐一检验
逐个判断哪些符合问题所要求的情况，从而得到问题的解。
如何快速找出第515个质数？
利用计算机程序枚举！
使用计算机程序枚举，宜采用什么结构进行逐一列举？
A:顺序结构
B.循环结构
使用计算机程序枚举，逐一进行验证时，当满足什么条件时就可以确定该问题的解？
该数字是质数，并且是第515个。
1
2
想一想？
完成流程图的区域
流程图完善
开始
个数 = 0
当前数是质数吗？
false
true
个数 = 个数 + 1
是第515个质数吗？
false
true
输出第515个质数
判断下一个数
完善程序
for(i=2;;i=i+1) //从i=2开始，依次验证每一个数
{
for(j=2;j<填空;j=j+1) //循环验证除了1和i本身外，每一个可能的因子;
{
if(i%j==0) break; //如果i被j整除,退出循环
}
if(j==填空) //如果j=i,则i就是质数，质数个数+1
{
cnt=cnt+1; //质数个数+1
if(cnt==515) //如果是第515个质数
{
cout<<填空; //输出解
break; //退出循环
}
}
}
3691
如果要找出第10000个质数，程序该如何修改 ？试着修改，并运行后，你发现了什么？
程序运行速度变慢了许多！
为什么会变慢？从算法本身考虑，可以怎么优化，使程序运行速度变快，并试着修改和运行程序！
枚举因数只需要从2枚举到√i即可。
讨论
优化后的程序
(特别注意红色标注部分代码)
for(i=2;;i=i+1) //从2开始，对每一个整数进行验证
{
int t=sqrt(i);//sqrt(i)表示根号i
for(j=2;j<=t;++j) //判断当前的i，在区间[2,sqrt(i)]范围内是否存在i因数
{
if(i%j==0) //i能被j整除，说明[2,sqrt(i)]范围内存在i的因数
break; //范围内找到了因数，说明肯定不是质数，直接退出循环，验证下一个数
}
if(j==t+1) //j如果与sqrt(i)+1相等，说明j在区间[2,sqrt(i)]范围内没有找到因数，所以i一定是质数
{
cnt=cnt+1; //个数加1
if(cnt==10000)//是否是第10000个质数
{
cout<break;//退出循环
}
}
}
优化后
优化前
枚举算法基本思想
逐一列举
—— 总结 ——
确定枚举对象、枚举范围和判定条件；
逐一检验
枚举可能的解，验证是否是问题的解。
枚举算法的特点
由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解，算法的正确性比较容易证明；
可能做了很多的无用功，浪费了宝贵的时间，效率低下。所以一定要省去无关的枚举量，找到一定的关系跳过无用数据。
计算全班同学的信息技术成绩的平均分
1
2
3
4
课堂练习
动脑想一想枚举法的应用
寻找1000000以内能被57且67整除的数
自行车车轮胎漏气了，将轮胎充满气，分段浸入水中，寻找冒气泡的位置，以便确定破损处。
忘记了密码箱上的密码，通过不断尝试找回密码
课后作业
寻找质数，除了本节课所讲的枚举法，你还能想出其它方法吗？下节课一起讨论下！
谢谢聆听！

展开更多......

收起↑