1、第五章 算法实例的程序实现 一、 本章教材分析 1 内容框架结构 5.1 枚举算法的程序实现 实践体验 问题与练习 算法思想： 见 2.1 枚举算法 教学范例： 变形金刚装箱方案程序实现 变形金刚装箱的改进 方案、单据中被涂抹 的数字推算 纸币问题、物不知数问 题、因子分解问题等枚 举问题求解 算法思想： 见 2.2 解析算法 教学范例： 算并联电阻总阻值、储蓄顾问题程序实现 储蓄问题改进程序、 计算圆内正方形砖块 数问题 计算求和 S、计算 1900.1.1 之后某一天是 星期几问题 算法思想： 见 2.3 排序 教学范例： 选择排序算法的程序实现 冒泡排序算法的程序 实现 排序循环次数计算
2、、两 个已按增序排序数组合 并问题 算法思想： 见 2.4 查找 教学范例： 对分查找算法的程序实现 顺序查找算法的程序 实现 查找问题分析、查找算 法效率计算 算法思想： 见 5.5.1 什么是递归法 教学范例： 计算 n 的阶乘、汉诺塔（Hanoi）问题 汉诺塔问题的程序实 现 其它递归问题的算法设 计 本章练习 设计一个“9 选 3”的 游戏程序 设计一个简单的袖珍计 算器 学生活动 算 法 实 例 的 程 序 实 现 2 教材目标 知识目标： （1）能够根据具体问题的要求，使用枚举方法设计算法，编写程序求解问题。 （2）能够根据具体问题的要求，使用解析方法设计算法，编写程序求解问题。
3、（3）通过实例，掌握使用排序算法设计程序求解问题。 （4）通过实例，掌握使用数据查找算法设计程序求解问题。 （5）能够根据具体问题的要求，使用递归算法设计程序求解问题。 能力目标： （1）增强学生的知识迁移应用能力。 （2）提高学生运用程序设计语言 VB 的能力。 （3）增强学生通过设计算法编写程序解决实际问题的能力。 3教材分析 本章主要包括“枚举算法的程序实现” 、 “解析算法的程序实现” 、 “排序算法的程序实 现” 、 “查找算法的程序实现” 、 “递归算法实例及程序实现”等五个小节。 本章教材主要内容是学习使用程序设计语言 VB，编制在第二章中学习过的枚举算法、 解析算法、排序算法、
4、查找算法的有关实例的程序，并在计算机上实现这些算法，本章最 后还学习了递归算法，以及递归算法实例的程序实现。在第三章、第四章，已经学习了面 向对象程序设计的基本知识和程序设计语言，本章主要通过多个 VB 程序设计实例的 学习，提高学生的程序设计能力，能够对一些简单的实际问题，设计算法编制程序并在计 算机上实现，为今后在算法与程序设计方面的进一步研究和学习打下基础。 本章教学的重点是各个实例的程序实现，因而“实践体验”活动是本章最重要的活动 形式，在本章的实践活动中，要采用各种办法让学生获得成功的体验，算法设计就如同学 游泳一样，教了许多游泳的姿势，最终一定要下水去游起来，通过亲身体验才能掌握，
5、教 师的作用是组织和指导实践活动，努力让所有学生都获得这种成功的体验。教学的难点是 对递归算法的执行过程的理解，以及对枚举算法、解析算法、排序算法、查找算法、递归 算法的掌握和灵活运用。在教学过程中，对教学范例要进行充分分析，利用辅助教学软件 （Flash 动画）帮助学生掌握和理解算法，综合运用所学知识编制程序。对所有的实践活动 程序，教师都需要提供正确的样例程序和 EXE 文件，帮助学生体会、理解。每节后都安有 排有“实践体验”活动和“问题与练习” ，通过“问题与练习”中的习题能够做到举一反三， 熟练掌握同类问题的解决方法，所有设计的程序都需要在计算机进行验证。同时教师可以 通过教学网站向有
6、兴趣的学生、有能力的学生提供更多算法思想，拓展他们的知识层面。 4 课时分配建议 节号 内容 学生活动 课时 5.1 枚举算法的程序实现 实践体验：变形金刚装箱的改进方案、单据中被 涂抹的数字推算 2 5.2 解析算法的程序实现 实践体验：储蓄问题改进程序、计算圆内正方形 砖块数问题 2 5.3 排序算法的程序实现 实践体验：冒泡排序算法的程序实现 2 5.4 查找算法的程序实现 实践体验：顺序查找算法的程序实现 2 5.5 递归算法实例及程序实现 实践体验：汉诺塔问题的程序实现 2 综合探究：设计一个“9 选 3”的猜数字游戏程 1 序 本章练习：设计一个简单的袖珍计算器 1 合计 12 二
7、、各节教学要求和教学设计建议 第一节（教材 5.1） 枚举算法的程序实现 1.教学要求 理解怎么用来实现解决简单问题的枚举算法 2.教学设计建议 在第二章算法实例的学习中，学生已经了解什么是枚举算法，怎样用枚举方法来设 计算法的基本方法，通过辅助教学软件来帮助理解算法实例的程序流程，本节主要是掌 握用程序设计语言来实现有关枚举算法的实例。因而，在教学设计时，重点从算法 的实现入手， “变形金刚装箱方案”算法前面在第二章我们已经学习过，在教学时，教 师可将算法流程（Flash 动画）重新进行演示，再结合应用程序界面（结果程序演示） 的设计要求，详细讲解如何转换成 VB 程序，程序代码中的界面设计
8、部分学生在理解上 可能会存在困难，教师要详细加以说明。 “变形金刚装箱方案”的 VB 源程序也需要提 供给学生，以帮助学生理解、体会程序的实现过程。 “实践体验”和“问题与练习”中 的活动内容都需要学生在计算机上完成并验证。建议本节用 2 个课时，其中学生实践活 动的时间建议不少于所用课时数的 1/2，甚至要占到 2/3。 教学流程如图 5.1 所示： 枚举算法的基本思想是把问题所有的可能解，逐一罗列出来并加以验证，若是问题 的真正解，就予以采纳，否则就抛弃它。在设计过程中，要做到既不遗漏任何一个解， 也不重复和扩大罗列的范围。对于范围的确定，在讲解过程中，教师要重点加以引导、 分析，帮助学生
9、理解、体会、掌握。在例中， “前 1000 个奇自然数” ，这是一个十分 明确的已经条件，它们就是 1，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 个偶自然数、前 100
10、0 个 3 的倍数等等，这个例 子也可以使用循环语句 For i=1 to 2000 step 2 直接枚举前 1000 个奇自然数。在范例“变 形金刚装箱方案”中，根据条件分析得出小盒 X 的范围是 1 至 293，中盒 Y 的范围是 展示“变形金 刚装箱方案” 的 VB 演示程 序 展示“变形金刚 装箱方案”的算 法流程（Flash 动 画） 详细分析算法流 程和界面设计要 求，编写 VB 程 序。 提出“变形金刚 装箱改进方案” 的要求，并分析 如何修改算法。 图 5.1 “枚举算法的程序实现”教学过程框图 学生实践体验活动： 变形金刚装箱的改 进方案、单据中被 涂抹的数字推算 问题与练
11、习：纸 币问题、孙子算 经问题、因子问 题等枚举问题求 解 1 至 118，大盒 Z 的范围是 1 至 74，可以引导学生思考，能否进一步约束条件，当小盒 X 取 293 时，中盒、大盒能否达到最大范围？最多达到多少？通过小组讨论形式，能否 给出改进建议，减少搜索的范围，既不遗漏又不重复。在“一份单据中被涂抹的数字的 推算”问题中，确定枚举范围时，学生很容易错误的认为是 2500625996 之间的自然数， 使用循环语句 For j=25006 to 25996 ，实际上这样大大增加了罗列的范围，应该是 2500625996 之间所有个位数为 6 的自然数。在纸币问题中，根据条件进行分析，可以
12、 得到 1 元币的张数取值范围可以在 110 之间，2 元币的张数取值范围可以在 19 之间， 5 元币的张数取值范围可以在 14 之间。 关于学生实践活动实施建议 “实践体验”活动是学生实践活动的最重要环节，实践活动的目的是用 VB 编制枚 举算法实例的程序。在学生实践活动中，由于不同学生的能力存在差异，部分同学可能 会较快完成，而另一些同学却有许多困难，在实践过程中学生会遇到各种各样的问题， 教师可安排能力强的学生做小老师，帮助其它同学一起解决问题，共同提高编程能力。 在“变形金刚装箱改进方案”活动中，提示学生分析清楚新增加的约束条件的要求， 是总盒数不超过指定的最大盒数，也就是说在原来找
13、到正确解的基础上再进行筛选，找 出总盒数不超过指定的最大盒数的装箱方案。从文本框输入的最大盒数变量是一个数字 字符串，需要使用函数 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
14、统计数组 K 中 1 的个数,结果存放在变量 w 中 For b = a To 1 Step -1 If K(b) = 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 Com
15、mand1_Click() Dim j, n, c As Integer c = 0 List1.Clear For j = 0 To 99 n = 25006 + 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 Sub n=25006+j*10 可以产生出 25006、25016、2502625996
16、这 100 个自然数，能否可 以使用其它表达式或函数呢？设置 N 的初始值为 24996，在循环内 N 每次增加 10。 n=24996 For j=0 to 99 也可使用 for j=1 to 100，共 100 个自然数 n=n+10 If n Mod 37 = 0 Or n Mod 67 = 0 Then List1.AddItem Str(n) c = c + 1 End If Next j 同样地，也可以使用改变步长值的方法，直接产生 25006、25016、2502625996 这 100 个自然数，程序段代码参考如下： For n=25006 to 25996 step 10
17、If n Mod 37 = 0 Or n Mod 67 = 0 Then List1.AddItem Str(n) c = c + 1 End If Next j 在编制程序时，需要用到命令按钮和列表框，各控件属性需要做如下设置： 控件 属性 属性值 说明 Form1 Caption 推算被涂抹单据上的数字 显示程序的功能 Command1 Caption 计算 说明命令按钮的作用 List1 使用缺省值 显示所有运算结果 当按下命令按钮时，程序开始执行，在列表框中输出所有运算结果。 3.练习题解答及补充练习 （1） “问题与练习”中第一题纸币问题的分析见第二章 2.1 的练习题解答。 本题的
18、程序代码如下，取法共有 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 For 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 N
19、ext j Next i Label1.Caption = “种数：“ + Str(sum) End Sub 在编制程序时，需要用到命令按钮、标签和列表框，各控件属性需要做如下设置： 控件 属性 属性值 说明 Form1 Caption 取纸币 显示程序的功能 Command1 Caption 计算 说明命令按钮的作用 Label1 使用缺省值 显示取法种数 List1 使用缺省值 显示所有不同的取法 当按下命令按钮时，程序开始执行，在标签中显示取法种数，在列表框中输出所有不同取 法。 （2）这是孙子算经中提出的“物不知其数”的问题。现分析如下：所寻找之数 为满足某类条件的自然数，此条件是它以
20、 3 除余 2，以 5 除余 3，以 7 除余 2，程序将从 自然数 1 开始依次寻找，逐一判断某一自然数是否满足全部条件，直至在指定范围内找到 满足条件的所有自然数，参考程序代码如下： Private Sub Command1_Click() Dim sum As Integer Dim n, max As Integer List1.Clear sum = 0 max = Val(Text1.Text) 指定查找范围的最大自然数 n = 0 Do While n i，可以避免重复寻找 Sum=0 For i = 1 To 100 For j = i To 100 For k = j To
21、100 If i 2 + j 2 = k 2 Then 是否满足条件 List1.AddItem (Str(i) + Str(j) + Str(k) sum = sum + 1 统计个数 End If Next k Next j Next i Label1.Caption = “组数：“ + Str(sum) End Sub （3） “百钱买百鸡”问题。中国古代数学家张丘建在张丘建算经中提出一个问 题。 “鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问 鸡翁、母、雏各几何？” 。 答案：共有 4 组， （0 ，25， 75） ， （4 ，18，78 ） ， （8 ，11，81）
22、 ， （12 ，4，84） 。 题目的意思是说公鸡五钱一只，母鸡三钱一只，小鸡一钱三只，花一百钱恰好买一 百只鸡，问公鸡、母鸡、小鸡各多少只？参考程序代码如下： Private Sub Command1_Click() Dim sum As Integer Dim i, a, b, c As Integer List1.Clear For a = 0 To 20 公鸡五钱一只，可取范围0 ，20 For b = 0 To 33 母鸡三钱一只，可取范围0 ，33 c = 100 - a b 小鸡的数量可直接计算得到，共有 100 只鸡 If a * 5 + b * 3 + c / 3 = 100
23、 Then 判断是否满足条件，刚好 100 钱 List1.AddItem (Str(a) + Str(b) + Str(c) sum = sum + 1 统计组数 End If Next b Next a Label1.Caption = “组数：“ + Str(sum) End Sub 第二节（教材 5.2） 解析算法的程序实现 1教学要求 理解怎么用来编制解决简单问题的解析算法的应用程序，并在计算机上实现。 2教学设计建议 什么是解析算法，我们在第二章中已经学习过了。本节的任务主要是用 VB 来实现 简单问题的解析算法。算法的基本思想是能找到解决解决问题的正确的公式，用它来描 述问题的原
24、始数据与结果之间的关系。在编制程序过程中，必须注意计算过程描述的正 确性。例如求解一元二次方程，若方程有两个解，则其中一个解是 x= ，acb24 如果我们使用代码 x=(-b+sqr(b*b-4*a*c)/2*a 来计算时，实际计算的是 x= ， 2c 正确的代码应该是 x=(-b+sqr(b*b-4*a*c)/(2*a)，或者是 x=(-b+sqr(b*b-4*a*c) /2/a。 又例如判断正实数 a，b ，c 能否构成三角形的三条边，如何我们使用判断成立的条 件 a+bc 肯定是不完整的， a+bc And a-bc and abs(a-b)c And a+cb And b+ca。 在
25、教学设计时，同样可以利用第二章中的辅助教学软件（Flash 动画）来帮助复习 算法实例的程序流程，再结合应用程序界面（结果程序演示）要求，理解和掌握如何将 计算公式转化为 VB 程序，对程序中的界面设计部分学生可能存在的困难，教师要详细 加以说明。同时 VB 源程序的范例也需要提供给学生，以帮助学生理解、体会实现的过 程。 “实践体验”和“问题与练习”中的相关活动内容都需要学生上机完成并验证，运 行时不仅需要测试输入数据是否正确，还需要对错误的输入数据给出提示。本节建议用 2 个课时，其中学生实践活动的时间应不少于 1/2，甚至占 2/3。 教学流程如图 5.4 所示： 在 “计算并联电阻总阻
26、值”的范例中，控件使用比较多。在讲解时，教师需讲解 清楚如何根据程序的要求需要哪些控件，各控件的属性需要做哪些设置，在哪个事件发 生时处理哪些操作（见书本图 5.2.2） 。当用鼠标点击文本框 Text2 时，认为是程序开始， 为接收输入第一个电阻值做好准备，当在文本框 Text2 输入完一个数据后，以回车符作 为一个阻值输入完毕的标志，在 Text2_KeyPress 中处理输入的数据，对输入数据进行有 效性判断，并在 List1 中显示有效数据并进行计算。在源程序中，语句 Text2.text=”的作 用十分重要，该语句无论在输入数据是否有效，输入处理完成后都要置空，为下次输入 做好准备语
27、句，如果只有在输入有效数据后才执行，那么输入了一个无效数据，如负数 展示“计算并 联电阻总阻值” 的 VB 演示程 序 展示“计算并联 电阻总阻值”的 算法流程（Flash 动画） 详细分析算法流 程和界面设计要 求，编写 VB 程 序。 学生尝试根据算 法流程动画和结 果程序演示，完 成“储蓄顾问” 。 图 5.4 “解析算法的程序实现”教学过程框图 学生实践体验活动： 储蓄问题改进程序、 计算圆内正方形砖 块数问题 问题与练习：求 和计算、计算 1900.1.1 之后某一 天是星期几问题 或者非数字，则程序将不能再接收任何新的数据。 “储蓄顾问”问题，我们先只考虑在简单规则下的情况： （1
28、） 存期以年为单位，存款以元为单位； （2） 不论存期的长短，年利率均为 2.8%； （3） 不计复利； 确定一笔 M 元钱的存款，需要存 Y 年，才能得到至少 K 元本息，满足关系式： Y=Fix(K-M)/0.028*M)。这儿我们可以发现这样一个情况，如果 K1)，这样就得到了从前 一项计算出下一项的推导式子，当 i=1 时，已知 a1=1。整个算法流程图可参考如图 5.6 方 式描述： 图 5.6 计算 s=1+ k1 的流程图nk2)()! 参考程序代码如下。 Private Sub Command1_Click() Dim i, n As Integer Dim j, s As D
29、ouble j = 1 s = 1 n = Val(Text1.Text) For i = 2 To n j = j / (2 * i - 1) * (2 * i - 2) 计算 1/(2*i-1)! s = s + (-1) (i - 1) * j 累加通项式 初始化变量 S1 ，j1 in s s + (-1) (i - 1) * j ii+1 输出结果 S Y N j j / (2 * i - 1) * (2 * i - 2) 开始 输入变量 n i2 结束 Next i Text2.Text = Str(s) 结果显示到文本框 Text2.text 中 End Sub 求 S 问题测试
30、数据表 测试数据 运行结果 第一组 =1 S=1 第二组 N=5 S=0.841471009700176 第三组 N=8 S=0.841470984807894 （2）这是星期计算问题。平时我们在日常生活中遇到这样的问题，忘记了几月几日 是星期几，我们一般会采用这样的方法，从一个已知的某天开始推算，先计算已知星期几 的这一天距要推算的那天共相差几天，然后将天数除以 7 取余数，最后就可以推算出星期 几了。在这儿我们也使用这样的方法进行推算。我们已知公元元年 1 月 1 日是星期一，再 计算需推算的日子离元年 1 月 1 日相距多少天（W） ，再用天数 W 除以 7 的余数加上 1 就 是星期几
31、了，余 0 就是星期一，余 1 就是星期二.，但是我们在计算天数时会发现由于 中间会经历平年（365 天） 、闰年（366 天） ，每年的不同月份天数也不相同，这样计算量 是很大的，计算也十分困难。有没有改进的方法呢？我们考虑这样的例子，元年 1 月 5 日 是星期几？因为是元年的第五天，所以是星期五，那元年的 3 月 1 日呢？因为元年是平年， 2 月有 28 天， 3 月 1 日离元年元月 1 日共有 31+28+1=60 天，60 除以 7 的余数是 4，所 以是星期四，那公元 6 年 1 月 5 日呢？推算如下： 日子 星期 推算过程 公元元年 1 月 5 日 星期五 是当年的第五天
32、公元 2 年 1 月 5 日 星期六 离上一年的 1 月 5 日相离 365 天，除以 7 余 1 公元 3 年 1 月 5 日 星期日 离上一年的 1 月 5 日相离 365 天，除以 7 余 1 公元 4 年 1 月 5 日 星期一 离上一年的 1 月 5 日相离 365 天，除以 7 余 1 公元 5 年 1 月 5 日 星期三 离上一年的 1 月 5 日相离 366 天，除以 7 余 2 公元 6 年 1 月 5 日 星期四 离上一年的 1 月 5 日相离 365 天，除以 7 余 1 也就是说中间经历整 5 年，其中有 1 个闰年，4 个平年，平年 365 天，除以 7 余 1， 闰
33、年 366 天，除以 7 余 2，星期数是 7 天一轮回的，相距的天数可以看成经过的闰年数 *2+经过平年数 *1，也等价于经过的整年数 +经过的闰年数。于是有公式： W = Y-1 + (Y-1)/4 - (Y-1)/100 + (Y-1)/400 + D，其中 Y 是年分数，D 是推算日 子在当年中是第几天， 表示取整。判断闰年的规则是能够被 400 整除的年份和能够被 4 整除且不能被 100 整除的年份，y-1表示经过的整年数， (y-1)/4-(y-1)/100表示所经过的 能够被 4 整除且不能被 100 整除的的闰年个数，(Y-1)/400表示经过的能够被 400 整除的 闰年数
34、，将 W 除以 7 取余数，余数为 0 结果是星期日，余数为 1 是星期一，余数为 2 是星 期二。 如推算公元 6 年 1 月 5 日是星期几，W=6-1+(6-1)/4-(6-1)/100+(6-1)/400 +5=11， 6-1计算出经过的整年数（包括平年和闰年） ，(6-1)/4-(6-1)/100+(6-1)/400计算 出经过的闰年数，11 除以 7 余 4，所以推算结果是星期四。如推算 2006 年 1 月 1 日是星期 几，W=2006-1+(2006-1)/4-(2006-1)/100+(2006-1)/400+1=2492，2492 除以 7 余 0，所 以推算结果是星期日
35、。 但是的计算也是比较复杂的，每个月的天数是不一致的，2 月份还有平闰年之分， 蔡勒提出了新的最好用的公式：W = C/4 2*C + y + y/4 + 13 * (M+1) / 5 + d - 1 ，C 是 世纪数减一即年份前 2 位，y 是年份后两位，M 是月份，d 是日数。1 月和 2 月要按上一年 的 13 月和 14 月来算，这时 C 和 y 均按上一年取值， 表示取整。 如：推算 2006 年 1 月 1 日是星期几？ C=20，y=05（月按上一年 13 月来算，同时 y 取上一年的年份） ，M=13 （月按上 一年 13 月来算） ，d=1，=20/4-2*20+5+5/4+
36、13*(13+1)/5+1-1=7，所以推算是星期日， 与事实一致。这个公式最早是由德国数学家克里斯蒂安蔡勒（Christian Zeller, 1822-1899） 在 1886 年推导出的，因此通称为蔡勒公式（Zellers Formula） 。为方便口算，式中的13 * (M+1) / 5也往往写成26 * (M+1) / 10。 算法流程框图如图 5.7 所示： 图 5.7 计算某年某月某日是星期几的流程图 参考程序代码如下： Public Function leap(y As Integer) As Integer 判断是否为闰年函数 If y Mod 100 = 0 Then 是返
37、回 1，不是返回 0 If y Mod 400 = 0 Then leap = 1 Else leap = 0 函数说明见书 4.4.2 节 Else If y Mod 4 = 0 Then leap = 1 Else leap = 0 End If End Function 计算 c，y，m， d。C 是世纪数减一，y 是年份后两 位，M 是月份，d 是日数，1 月和 2 月要按上一年 的 13 月和 14 月来算，这时 C 和 y 均按上一年取 值 W C/4 2*C + y + y/4 + 13 * (M+1) / 5 + d - 1 ww mod 7 输出结果星期几 N 开始 输出“输
38、入有误” 结束 输入年月日 判断日期是否有效？ Y Private Sub Command1_Click() Dim year as integer, month, day, w, c, y, m, d, ok As Integer year = Val(Text1.Text) month = Val(Text2.Text) day = Val(Text3.Text) ok = 0 判断输入的日期是否是有效的日期，根据平年、闰年，不同月份的不同情况来判断 If (month = 1 Or month = 3 Or month = 5 Or month = 7 Or month = 8 Or m
39、onth = 10 Or month = 12) And (day = 1 And day = 1 Or day = 1 And day = 1 And day 2 then fib = fib(n-1)+fib(n -2) 计算公式 End Function 在汉诺塔问题中，每次只能搬动一个盘，同时被搬动的盘只能放在另外两个柱子中 的一个柱子上，并且所有柱子上的盘子只能是从小到大。按照递归展开的思想，先考虑把 规模为 n 的问题化解为规模为 (n-1)的问题。假定我们已经能够完成搬动 n-1 个盘的工作， 于是移动 N（n1 ）个盘从 A 柱移动至 C 柱的算法我们可以这样写出来： （1）
40、将（n-1）个盘从 A 柱搬动到 B 柱，在 C 柱帮助下 （2） 将第 N 个盘从 A 柱搬动到 C 柱 （3） 将（n-1）个盘从 B 柱搬动 C 柱，在 A 柱帮助下 移动规则是每次只能搬动一个盘，所以搬动（n-1）个盘时，肯定需要另一个柱子帮 助。 当 N=1 时，也就是搬动一个盘，那只要直接将这个盘从 A 柱搬到 C 柱就可以了。 在教学时，可以找三本不同大小的书让学生自己动手实践完成 3 个盘的搬动过程， 加深理解。搬动 n 个盘汉诺塔参考算法 hanoi 流程图如下： 过程 Hanoi(n,a,c,b)的含义是，将 N 个盘从 A 柱（源柱）搬至 C 柱（目标柱）在 B 柱（帮助
41、柱）的帮助下完成，这句话十分重要，它说明了过程 Hanoi 四个参数所表示的含 义。 搬动的次数 h(n)满足： h(n)=h(n-1)+1+h(n-1)=2h(n-1)+1 (n1) h(1)=1 (n=1) h(4)=2h(3)+1=2(2h(2)+1)+1=2(2 (2h(1)+1)+1)+1=2(2 (21+1)+1) n=1? A 柱C 柱，计数器加 1 Y N 开始 结束 Hanoi(n-1,A,B,C) A 柱C 柱,计数器加 1 Hanoi(n-1,B,C,A) 为了将 n-1 个盘从 A 柱搬动至 B 柱， 必须再次执行算法 hanoi 为了将 n-1 个盘从 B 柱搬动至
42、C 柱， 必须再次执行算法 hanoi 图 5.17 汉诺塔问题的算法 hanoi 每次搬动后，计 数器增加 1 +1，2(2 (21+1)+1)+1 恰好是二进制数 1111 的十进制值，为 24-1=15 整个程序参考程序代码如下： Dim num As Long num 为记录搬动次数 Sub hanoi(n As Integer, a As String, c As String, b As String) Hanoi 过程四个参数分别是 N 个盘数，源柱，目标柱，帮助柱，过程的意思是将 N 个盘从源柱搬动到目标柱通过帮助柱帮助下。 If (n = 1) Then 当只有一个盘时 nu
43、m = num + 1 List1.AddItem (Str(num) + “:“ + a + “-“ + c) 搬动一个盘从源柱到目标柱 Else Call hanoi(n - 1, a, b, c) 搬动 N-1 个盘从 A 柱到 B 柱，在 C 柱帮助下 num = num + 1 List1.AddItem (Str(num) + “:“ + a + “-“ + c) Call hanoi(n - 1, b, c, a) 搬动 N-1 个盘从 B 柱到 C 柱，在 A 柱帮助下 End If End Sub Private Sub Command1_Click() Dim n As I
44、nteger n = Val(Text1.Text) 将 N 个盘从 A 柱（源柱）搬至 C 柱（目标柱）在 B 柱（帮助柱）的帮助下 Call hanoi(n, “A“, “C“, “B“) Call 为过程调用 List1.AddItem (“共“ + Str(num) + “次“) End Sub Private Sub Text1_Click() num = 0 计数器清 0 List1.Clear 列表框清空 Text1.Text = “ 输入文本框清空 End Sub 参考界面设计如下： 图 5.18 汉诺塔问题的程序界面 根据程序要求需要使用到文本框、标签、列表框、命令按钮等控件
45、，各控件的属性设 置参考如下： 控件 属性 属性值 说明 Form1 Caption 汉诺塔问题 显示程序的功能 Command1 Caption 计算 说明命令按钮的作用 Text1 text 空串 输入盘片数 n Lable1 Caption 输入盘片数 说明文本框 text1 的作用 List1 输出搬动过程及搬动次数 汉诺塔问题是一个经典的 NP 问题，对于计算机来说仍然是一个“难”的问题， “难” 主要是说程序执行步数随着 N 的增长呈指数级增长，如果塔上有 64 个盘，则搬动次数是 二进制 11111111（64 个 1）的值，十进制数值为 264-1=18446744073709
46、551615，目前我 们的个人电脑运算速度已经很快，可以达到每秒几亿十几亿次运算一次，假设每秒可以完 成 10 亿次搬动（大约是 230） ，也需要 234 秒，大约是 198841 天，约 544 年，看来在有生之 年是无法看到所有的搬动过程，这类问题就叫做“NP 问题” 。 关于学生实践活动实施建议 汉诺塔问题本身的搬动过程是一个十分复杂的过程，在学生进行实践体验活动之前， 教师一定要分析清楚递归的算法的含义，以及递归的展开和返回的整个过程中涉及的 各种操作，在充分理解之后，学生才能正确地完成这个实践活动。 在活动评价时，可根据界面设计合理情况及测试数据执行情况进行评价，评价指标 可参照书
47、本的要求进行，也可参照如下评价表的指标进行。 测试数据执行结果表 盘数 搬动次数 搬动过程 N=1 1 1：AC N=2 3 1：AB 2：AC 3：BC N=3 7 1：AC 2：AB 3：CB 4：AC 5：BA 6：BC 7：AC N=10 1023 1：AB 2：AC 3：BC 4：AB 5：CA 6：CB 7：AB 1021：AB 1022：AC 1023：BC 参考评价指标表 活动主题 评价指标（活动满分 6 分） 搬动次数正确、搬动过程全正确、界面设计合理 6 分 搬动次数正确、搬动过程部分正确、界面设计合理 5 分 搬动次数、搬动过程不全正确 3 分 汉诺塔 问题 算法表达有错
48、误，或者程序无法运行 2 分 3.练习题解答及补充练习： （1）递归算法设计思路如下： 1） 写出递归表达式 f(n)=n*n+f(n-1) (n1) f(1)=1 (n=1) 2）画出递归算法流程图 图 5.19 计算 2 的递归算法流程图 nk1 3）参考程序代码如下： Function f(n As Integer) As Long If n 1) f(1)= -0.5 (n=1) 2）画出递归算法流程图 图 5.20 计算 s= k 递归方法流程图nk1)(2 3）参考程序代码如下： Function f(n As Integer) As single If n 0 and k mod 5=0 Then 寻找满足条件的方案 K=k5 List1.AddItem (“1 元：“ + Str(i) + “张 2 元：“ + Str(j) + “张 5 元：“ + Str(k) + “张“) sum = sum + 1 计算种数 End If Next j Next i 使用枚举算法解决问题，由于有时要枚举的可能解个数十分巨大，如背包问题、中国 邮路问题，就需要不断改进算法，
