《第6课 枚举算法》参考课件

第6课枚举算法豫科版七年级下册1.理解枚举算法思想。2.运用枚举法编程解决问题。学习目标新课导入生活中，小朋友们在玩捉迷藏游戏时，会在一定范围内逐个地方去查找。这种找人的方法就是枚举算法思想。在解决问题时，人们如果采用枚举法会显得笨拙和烦琐，但计算机的高速运算处理能力保证了枚举法的可行性。本课将学习枚举算法思想，体验并尝试用枚举思维编程解决问题。知识链接枚举法，又称为穷举法，是计算机处理问题最常用的算法思想之一。算法的基本原理是根据已知条件，在给定的数据范围内，按某种顺序逐一列举所有可能的答案并检验。使用该算法需要满足两个条件：①可预先确定候选答案的数量或范围；②候选答案的范围在求解之前必须有一个确定的集合。例如，可以用枚举法求两个正整数的最大公约数。问题分析：设x，y为两个正整数，它们的最大公约数一定在[1，min（x，y）]区间，min（x，y）表示x，y的最小值。从最小值开始，向下枚举，第一个能同时整除x，y的数，就是两数的最大公约数。程序代码如下所示。知识链接#include<bits/stdc++.h>usingnamespacestd;inta,x,y,t;intmain(){ cout<<"请输入两个大于1的自然数："; cin>>x>>y; if(x<y)a=x;elsea=y;//最大公约数不大于两数的最小值

while(y%a!=0||x%a!=0){//如果a不是x,y的公因子继续向下枚举

a=a-1; } cout<<x<<"和"<<y<<"的最大公约数是："<<a<<"\n"; return0;}实践活动质数就是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。质数在数学和日常生活中有很多神奇的应用，从出现质数概念到如今，对质数的研究一直就没停止过，设计算法使计算机能够判断输入的正整数是否为质数。1.分析问题，设计算法根据质数的定义，判断某个数x是不是质数，需要验证在[2,x-1]范围中是否存在x的因数，方法如下。依次取[2,x-1]中的整数i，判断是不是x的因子，并统计因子的个数。如果x的因数个数为0，则说明x除了1和它本身没有其他因数，x是质数，否则x是合数。算法流程如图所示。实践活动统计x因数的计数器清零确定枚举的初始值实践活动2.程序实现分析（1）需要定义几个变量存放数据；数据类型如何设定。（2）枚举的过程用什么语句控制；枚举的范围如何表示。（3）如何判断一个数是另一个数的因数。（4）程序中判断质数的依据如何设定？用什么语句实现？实践活动3.编写程序C&C++程序参考如图。4.调试运行程序探究活动1.分析求质数的算法，讨论算法存在的问题，并尝试进行优化改良。2.讨论日常生活中哪些问题适用枚举算法，选一个典型问题编程解决。拓展阅读神奇的质数质数最主要的应用在密码学--RSA加密。它在网络安全领域中相当重要，利用质数对信息进行加密，可以保护国家情报和战时的军事机密，使安全性大大提高。举个例子，数字60可以分解成2×30，而30又可以分解成2×3×5，也就是说数字60可以由2、3、5这几个素数构成，这几个数字是不能继续分解的，整个过程被称为60的质因数分解。根据这个道理，如果将几个极大的素数a，b，c相乘，得到数字A，对于一个不知道任何信息的外部人员来说，想要对A质因数分解是相当困难的，重点是数学界也没有找到对极大数的快速质因数分解的算法。所以在战争时期，重要信息加入大量素数进行加密，哪怕被敌方截获也无法破解获得真实情报。拓展阅读神奇的质数在汽车变速箱齿轮的设计上，相邻两个大小齿轮的齿数设计成质数，可以使两齿轮内两个相同的齿相遇啮合次数的最小公倍数最大化，使齿轮间的磨损更均匀一些，增强耐用度，减少机械故障。从实践中发现，农药的使用周期以质数次数的使用最为合理。这是综合考虑了害虫体内产生的抗药性、害虫的繁殖周期、喷洒农药后害虫对农作物的损害情况等产生的结果。练习提升1.阅读程序，代码如下所示，填写运行结果。#include<bits/stdc++.h>usingnamespacestd;intx,y,z,i,n;intmain(){ cin>>n; x=1;y=1; cout<<x<<''<<y;//两个单引号间有一空格符

for(i=3;i<=n;i=i+1){ z=x+y; cout<<''<<z; x=y;y=z; } cout<<'\n'; return0;}输入：10输出：

。练习提升2.数学上的水仙花数是一个3位数，设3位数为abc，若abc=a3+b3+c3，则称abc为水仙花数。例如，153是水仙花数，因为13+53+33=153。完善程序，代码如下所示：#include<bits/stdc++.h>usingnamespacestd;inta,b,c,x;intmain(){ for(x=

;x<

;x=