算法的程序实现.ppt

第四章算法的程序实现第四章算法的程序实现本节掌握枚举算法的基本思想、程序实现方法、多重循环的程序实现方法，难点是理解内循环与外循环的概念，并能根据算法编写简单的多重循环代码。掌握常见素数问题算法与最大公约数问题算法。考查方式为选择题与非选择题。1．枚举算法的基本思想枚举，就是将问题的可能解一个个地列举，逐一判断，即使中途找到符合的解也要继续找下去，将所有可能都找完才结束。枚举算法又叫穷举算法，其基本思想是把问题所有的解一一地罗列出来，并对每一个可能解进行判断，以确定这个可能解是否是问题的真正解。若是，就采纳这个解，否则就抛弃它。2．枚举算法的实现要点(1)列举与检验过程既不重复也不遗漏；(2)尽可能地使可能解的罗列范围最小，以提高解决问题的效率；(3)用循环语句(For语句)在一定范围内列举所有可能的解；(4)用选择语句(If语句)判断和选择真正的解。3．枚举算法的一般格式4．双重循环某些枚举算法的问题比较复杂，需要通过复杂的双重循环来实现。双重循环就是循环的嵌套，在一层循环结构内部又是另一层循环，其结构如下所示：此结构由两个For循环构成，外循环是循环变量为i的循环，内循环是循环变量为j的循环，这两个循环之间的关系是嵌套关系，循环变量为i的循环将循环变量为j的循环包含在内，在循环执行时，外循环变量i每变化一次，都要执行一次完整的内循环。在枚举算法中，有很多时候用到循环的嵌套来解决问题。5．循环嵌套循环嵌套的层数没有具体限定，选考时的多重循环结构一般只要求到双重循环。多重循环在使用时，每个循环必须只有一个唯一的变量名作为循环变量；在Next语句结束循环时，必须内循环先结束，不得出现互相交叉。6．编写枚举算法的程序要注意两个要点(1)For循环的范围要尽可能的小，这决定可能解的范围是否已经尽可能的小；(2)条件表达式必须要正确无误，这决定哪些解才是真正的解。7．素数问题(1)素数的概念素数(质数)就是一个大于等于2的整数，并且只能被1和本身整除，而不能被其他整数整除的数。(2)算法说明判别某数n是否是素数的经典算法是，对于n，从i＝2,3,4，……，n－1依次判别能否被i整除，只要有一个能整除，n就不是素数，否则n是素数。(3)代码实现8．最大公约数问题(1)最大公约数：就是几个数共同最大的约数。(2)算法说明：用辗转相除法求两自然数m、n的最大公约数，再由最大公约数求出最小公倍数。①首先，对于已知两数m、n，比较并使得m>n；②m除以n得余数r；③若r＝0，则n为求得的最大公约数，算法结束；否则执行步骤㈣；④使m＝n，n＝r再重复执行㈡。(3)代码实现：【例1】下列问题中适合使用枚举算法解决的是()A．计算两个电阻的并联值B．计算五个同学的平均身高C．查找100以内所有能被6整除的数D．超市的促销方案【例1解题】本题考查枚举算法的特点。选项A、B和D都适用________算法，用数学公式求解。选项C的解决方法符合________算法的基本思想，先列举再验证。【答案1】________【例2】[浙江高考]某工厂购入100千克原材料，每4千克原材料可以生产一件A产品，每5千克原材料可以生产一件B产品。下列VB程序的功能是：计算恰好用尽这些原材料时，生产A产品和B产品数量的各种可能，并在列表框中输出。请在划线处填入合适代码。PrivateSubCommand1_Click()DimxAsInteger,yAsInteger′x为A产品数量，y为B产品数量Forx＝0To25Fory＝0To20If____(1)____ThenList1.AddItem”A产品”＋Str(x)＋”件，”＋”B产品”＋Str(y)＋”件”EndIf____(2)____NextxEndSub【例2解题】本题考查枚举算法的程序实现。设100千克原材料产生了x件A产品、y件B产品，它们必须满足等式4x+5y=100。当y取最小值0时，x可以取到最大值25，同样，当x取最小值0时，y可以取到最大值20。本题中程序采用嵌套循环的方法来进行枚举，执行时，外层的For循环当x的取值为0时，内层的For循环完整执行一次，即y取值为0～20之间的整数，然后判断这些数y与x的组合能否满足条件4x+5y=100，若满足，则在对象List1列表框中输出一组x、y，一次循环结束后，外循环变量x增加1，再次执行一次完整的内层For循环，还是y取值为0～20之间的整数……依此类推，可把x取值为0～25与y取值为0～20的所有可能组合（共有26×21=546种组合）都判断是否满足条件4x+5y=100，若条件成立则在列表框List1输出一组x、y。故题中（1）就是条件表达式4*x+5*y=100，内层For循环语句的循环变量是y，它应先结束；（2）为Nexty，放在外层循环的Nex