枚举算法第一节.doc

《枚举算法第一节.doc》由会员分享，可在线阅读，更多相关《枚举算法第一节.doc（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一节（教材5.1） 枚举算法的程序实现1.教学要求理解怎么用来实现解决简单问题的枚举算法2.教学设计建议在第二章算法实例的学习中，学生已经了解什么是枚举算法，怎样用枚举方法来设计算法的基本方法，通过辅助教学软件来帮助理解算法实例的程序流程，本节主要是掌握用程序设计语言来实现有关枚举算法的实例。因而，在教学设计时，重点从算法的实现入手，“变形金刚装箱方案”算法前面在第二章我们已经学习过，在教学时，教师可将算法流程（Flash动画）重新进行演示，再结合应用程序界面（结果程序演示）的设计要求，详细讲解如何转换成VB程序，程序代码中的界面设计部分学生在理解上可能会存在困难，教师要详细加以说明。“变形

2、金刚装箱方案”的VB源程序也需要提供给学生，以帮助学生理解、体会程序的实现过程。“实践体验”和“问题与练习”中的活动内容都需要学生在计算机上完成并验证。建议本节用2个课时，其中学生实践活动的时间建议不少于所用课时数的1/2，甚至要占到2/3。教学流程如图5.1所示：枚举算法的基本思想是把问题所有的可能解，逐一罗列出来并加以验证，若是问题的真正解，就予以采纳，否则就抛弃它。在设计过程中，要做到既不遗漏任何一个解，也不重复和扩大罗列的范围。对于范围的确定，在讲解过程中，教师要重点加以引导、分析，帮助学生理解、体会、掌握。在例中，“前1000个奇自然数”，这是一个十分明确的已经条件，它们就是1，3，

3、5，7，91999，而在中使用循环语句For i=1 to 1000，这样就遗漏了1001到1999之间的可能解，在中使用循环语句For i=1 to 2000，这样在枚举过程中，可能解罗列的范围太大了，把偶数也包括在内了，在中使用循环语句For i=1 to 1000，表示共有1000个数，再使用公式j=2*i-1计算出第i个奇自然数j，这样的程序设计思想，学生在刚开始学习时不容易掌握，需要教师通过增加练习来巩固，如前1000个偶自然数、前1000个3的倍数等等，这个例子也可以使用循环语句For i=1 to 2000 step 2 直接枚举前1000个奇自然数。在范例“变形金刚装箱方案”中

4、，根据条件分析得出小盒X的范围是1至293，中盒Y的范围是1至118，大盒Z的范围是1至74，可以引导学生思考，能否进一步约束条件，当小盒X取293时，中盒、大盒能否达到最大范围？最多达到多少？通过小组讨论形式，能否给出改进建议，减少搜索的范围，既不遗漏又不重复。在“一份单据中被涂抹的数字的推算”问题中，确定枚举范围时，学生很容易错误的认为是2500625996之间的自然数，使用循环语句For j=25006 to 25996 ，实际上这样大大增加了罗列的范围，应该是2500625996之间所有个位数为6的自然数。在纸币问题中，根据条件进行分析，可以得到1元币的张数取值范围可以在110之间，2

5、元币的张数取值范围可以在19之间，5元币的张数取值范围可以在14之间。关于学生实践活动实施建议“实践体验”活动是学生实践活动的最重要环节，实践活动的目的是用VB编制枚举算法实例的程序。在学生实践活动中，由于不同学生的能力存在差异，部分同学可能会较快完成，而另一些同学却有许多困难，在实践过程中学生会遇到各种各样的问题，教师可安排能力强的学生做小老师，帮助其它同学一起解决问题，共同提高编程能力。在“变形金刚装箱改进方案”活动中，提示学生分析清楚新增加的约束条件的要求，是总盒数不超过指定的最大盒数，也就是说在原来找到正确解的基础上再进行筛选，找出总盒数不超过指定的最大盒数的装箱方案。从文本框输入的最

6、大盒数变量是一个数字字符串，需要使用函数Val（）转换为整数类型，如果在程序中遗漏了类型转换，在后面进行x+y+z1999 Dim a, b, c As Integer Dim i, j, w As Integer Form1.Show c = 0 For i = 1 To 1000 a = 0 采用除2取余法将十进制数化二进制数，结果存放在数组K中 j = i * 2 - 1 Do While j 0 a = a + 1 K(a) = j Mod 2 j = j 2 Loop w = 0 统计数组K中1的个数,结果存放在变量w中 For b = a To 1 Step -1 If K(b)

7、= 1 Then w = w + 1 Next b If w = 3 Then c = c + 1 统计二进制数中恰好有三位1的个数 Next i Print 在前1000个奇自然数中,恰好有三位为1的二进制数的个数有; c; 个。End Sub“推算被涂抹单据上的数字”参考程序如下，其中判断n是否为37的倍数可以用表达式n mod 37=0来表示，也可以用int(n/37)*37=n等不同形式来表示。Private Sub Command1_Click() Dim j, n, c As Integer c = 0 List1.Clear For j = 0 To 99 n = 25006 +

8、 j * 10 产生出25006、25016、2502625996这100个自然数 If n Mod 37 = 0 Or n Mod 67 = 0 Then List1.AddItem Str(n) c = c + 1 End If Next j List1.AddItem 总计有 + Str(c) + 个五位数End Subn=25006+j*10可以产生出25006、25016、2502625996这100个自然数，能否可以使用其它表达式或函数呢？设置N的初始值为24996，在循环内N每次增加10。n=24996For j=0 to 99 也可使用 for j=1 to 100，共100个

9、自然数n=n+10 If n Mod 37 = 0 Or n Mod 67 = 0 Then List1.AddItem Str(n) c = c + 1 End IfNext j同样地，也可以使用改变步长值的方法，直接产生25006、25016、2502625996这100个自然数，程序段代码参考如下：For n=25006 to 25996 step 10 If n Mod 37 = 0 Or n Mod 67 = 0 Then List1.AddItem Str(n) c = c + 1 End IfNext j在编制程序时，需要用到命令按钮和列表框，各控件属性需要做如下设置：控件 属性

10、 属性值 说明Form1 Caption 推算被涂抹单据上的数字 显示程序的功能Command1 Caption 计算 说明命令按钮的作用List1 使用缺省值 显示所有运算结果当按下命令按钮时，程序开始执行，在列表框中输出所有运算结果。3.练习题解答及补充练习（1）“问题与练习”中第一题纸币问题的分析见第二章2.1的练习题解答。本题的程序代码如下，取法共有23种。Private Sub Command1_Click() Dim sum As Integer Dim i, j, k As Integer List1.Clear For i = 1 To 10 For j = 1 To 9 Fo

11、r k = 1 To 4 If i + j * 2 + k * 5 = 24 Then寻找满足条件的方案List1.AddItem (1元： + Str(i) + 张2元： + Str(j) + 张5元： + Str(k) + 张) sum = sum + 1计算种数 End If Next k Next j Next i Label1.Caption = 种数： + Str(sum)End Sub在编制程序时，需要用到命令按钮、标签和列表框，各控件属性需要做如下设置：控件 属性 属性值 说明Form1 Caption 取纸币 显示程序的功能Command1 Caption 计算 说明命令按钮

12、的作用Label1 使用缺省值 显示取法种数List1 使用缺省值 显示所有不同的取法当按下命令按钮时，程序开始执行，在标签中显示取法种数，在列表框中输出所有不同取法。（2）这是孙子算经中提出的“物不知其数”的问题。现分析如下：所寻找之数为满足某类条件的自然数，此条件是它以3除余2，以5除余3，以7除余2，程序将从自然数1开始依次寻找，逐一判断某一自然数是否满足全部条件，直至在指定范围内找到满足条件的所有自然数，参考程序代码如下：Private Sub Command1_Click() Dim sum As Integer Dim n, max As Integer List1.Clear s

13、um = 0 max = Val(Text1.Text) 指定查找范围的最大自然数 n = 0 Do While n = max n = n + 1 从自然数1开始不断往上寻找 If n Mod 3 = 2 And n Mod 5 = 3 And n Mod 7 = 2 Then List1.AddItem Str(n) 找到后在list1中显示结果 sum = sum + 1 统计个数 End If Loop List1.AddItem (共计 + Str(sum) + 个)End Sub此算法还可以作如下改进，已知该数一定满足以7除余2，则从满足此条件的最小自然数9开始，依次从9，16，2

14、3，的序列中寻找满足同时以3除余2，以5除余3的数，则可以缩小搜索的范围，上面的程序段： n = 0 Do While n = max n = n + 1 从自然数1开始不断往上寻找 If n Mod 3 = 2 And n Mod 5 = 3 And n Mod 7 = 2 Then List1.AddItem Str(n) sum = sum + 1 统计个数 End If Loop可改为： n = 9 Do While n = max n = n +7 从以7除余2的自然数中进行寻找 If n Mod 3 = 2 And n Mod 5 = 3 Then List1.AddItem Str(n) sum = sum + 1 统计个数 End If Loop