论文部分内容阅读
【摘要】算法优化是程序设计教学的重要内容，对培养学生创新思维和良好编程风格具有重要作用。本文以古代“百钱买百鸡”为教学案例，通过数学推导论证，深入讨论了穷举算法逐步优化的方法和分析，在提高学生的编程兴趣和技能训练方面取得了良好的教学效果。
【关键词】程序设计 穷举算法 优化
【中图分类号】G642 【文献标识码】A 【文章编号】2095-3089（2013）09-0127-02
穷举算法是计算机程序设计中常用的一种问题求解策略。其基本思想是对问题的所有可能状态一一测试，直到找到解或将全部可能状态都测试过为止。求解此类问题往往要排除明显不符合条件的情况，使问题得以简化。虽然计算机运算速度很快，用穷举算法求解，一般问题可很快得出结果，但从程序可读性、正确性和算法效率等角度考虑，借助数学分析方法，实现此类问题的过程优化，对于培养良好的编程风格具有重要的影响和作用。
本文以古代的“百钱买百鸡”问题为例，通过对该例VB程序设计教学的实例分析，探讨程序设计优化的过程和方法，以及对学生创新思维培养的作用。
1.问题的引入
穷举问题是一种重复性算法，一般以计数方法设定循环次数，然后逐步测试，完成测试次数后结束循环，得到全部符合条件的结果。
如百钱买百鸡问题：已知公鸡三元一只，母鸡二元一只，小鸡一元钱三只，现要求用一百元买一百只鸡，给出买鸡方案。
设定可买公鸡X只，母鸡Y只，小鸡Z只，则可建立数字模型
X+Y+Z=100 （1）
5×X+3×Y+Z/3=100 （2）
从题意出发，可容易地建立三重循环实现如下基本程序：
程序一：
Private Sub Command1_Click（）
Dim x as integer， y as integer， z as integer
Dim count As Long
Cls
For x = 0 To 100
For y = 0 To 100
For z = 0 To 100
If x + y + z = 100 And 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next z
Next y
Next x
Print “循环次数”； count
End Sub
程序运行后，结果如图1：其中内层循环体执行次数为103万次，运行效率低下。
2.算法的初步优化
在穷举算法程序设计中，有许多种情况是明显不符合要求的，可在程序优化中先消除掉[1]。
上例中，公鸡X，母鸡Y的循环次数，因售价所限，取值分别为 0<=X<=20， 0<=Y<=33，小鸡为3的倍数，所以上面程序中循环部分的上界和步长可改写为：
程序二：
Private Sub Command2_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 20
For y = 0 To 33
For z = 0 To 100 Step 3
If x + y + z = 100 And 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next z
Next y
Next x
Print “循环次数”； count
End Sub
初步改进后，内层循环体执行次数降低为24276次，运行效率提高50倍。
3.算法中循环层数的简化
穷举算法程序一般根据相关因素的个数建立多层循环嵌套构成，而各层循环之间与问题所要求的条件具有密切的联系，因此，在教学过程中，引导学生通过分析有关条件，可将有的循环层进行简化或去掉。对学生的素质训练是一个重要的提高。
上例中，由于X+Y+Z=100，故可去掉Z层循环，Z值由Z=100-X-Y确定。
程序三：
Private Sub Command3_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 20
For y = 0 To 33
z = 100 - x - y
If 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next y
Next x
Print “循环次数”； count
End Sub
去掉Z层循环，内层循环体执行次数降低为714次，运行效率提高30倍。
与学生一起进一步分析，上述过程中，条件5*x+3*y+z/3=100需要做三次乘除运算，且除法实数运算复杂， 比整数运算效率差异较大。一种解决办法是，将除法的分母去掉，即条件改为：15*x+9*y+z==300，则只需做两次乘法运算。但该方法降低了程序的可读性。因此，程序设计过程中，需考虑运行效率与可读性之间的矛盾和取舍。 第二个问题是，本节以X，Y建立两重循环，同学们还可以以X，Z或Y，Z建立两重循环，测试内层循环体执行次数是否减少优化。
4.数学论证对程序优化的作用
通过前面的讨论，程序运行效率提高数十成百倍，基本达到了学生优化意识训练目的，有关教材的讨论也到此为止了[2，3]多数学生也认为这已是最好的结果。
但是程序优化的问题多数是数学求解问题，因此引导学生对问题的运行结果进行数学分析，用数学推导为程序优化提供充分的依据，甚至得出更好的优化结果[4，5]。这个提示引起学生极大的兴趣，课后全班学生积极研究探讨，取得了一系列优秀成果。整理总结有以下几个方面的内容。
4.1 循环变量上下界的取值范围的优化
由（2）式乘3，可得
15×X+9×Y+Z==300 （3）
（3） -（1）除 2 得 7×X+4×Y=100 （4）
由 （4） 得
X=（100-4Y）/ 7 <= 100/7 <15 （5）
所以 X为 0 <=X <=14 中的整数
同理， Y=（100-7×X）/ 4 <=25 （6）
所以 Y为 0 <=Y <=25 中的整数
通过推导X，Y的取值范围，循环可改为：
程序四：
Private Sub Command4_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 14
For y = 0 To 25
z = 100 - x - y
If 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next y
Next x
Print “循环次数”； count
End Sub
由此，内层循环体执行次数降低为390次。
同样，可推导Z的取值为，75<=Z<=85的整数。
4.2 运行结果的数学分析
阅读运行结果，我们发现有如下结论：a.X取值为4的整数倍，Z的取值为3的整数倍；b.Y取值为公差为 7 的等差数列。同学们也做了完整的论证。
例如，由（6）式 Y=（100-7×X）/4，因为Y为整数，所以7×X/4为整数，故X为4的整数倍。因此循环可改为：
程序五：
Private Sub Command5_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 14 Step 4
For y = 0 To 25
z = 100 - x - y
If 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next y
Next x
Print “循环次数”； count
End Sub
由此，内层循环体执行次数降低为104次。
4.3 通过数学推导建立单层循环
一些同学做了更深入的讨论，在一、二节数学分析的结论支持下，进一步提出将X，Y的取值通过Z的函数关系求得，由此建立Z的单层循环实现。
由（1）（3）式消去Y，得到
X=4×Z/3-100 （7）
结合一、二节的相关结论，循环可改为：
程序六：
Private Sub Command6_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For z = 75 To 85 Step 3
x = 4 * z / 3 - 100
y = 100 - x - z
Print x， y， z
count = count + 1
Next z
Print “循环次数”； count
End Sub
这样，内层循环体执行次数只需4次，且每次循环做两次乘除法运算！
确实让我们感受到数学方法对程序优化过程的强大作用。
5.程序优化的效率分析
综述以上各节的讨论，以内层循环执行次数为主要指标，可列出下表：
6.结语
由本文以上分析可以看出，随着程序的逐步优化，程序运行效率得以成百上千倍的提高。但是引入数学方法后，程序运行效率提高更为明显，但是程序的可读性明显降低，需要在程序代码中添加注释详细予以说明。因此，程序的优化过程要考虑运行效率和程序可读性的取舍平衡。
虽然计算机运算速度不断提高，小型程序优化与否对运行时间影响有限。但是程序优化技能的培养，数学工具的应用，对学生增强编程兴趣，提高创新意识，尤其在大型软件过程设计质量的提高方面具有重大作用。
参考文献：
[1]石海鹤，石海鹏，郑宇军.算法程序变换研究与进展[J].计算机科学.2007（11）
[2]王贺明. Visual Basic程序设计教程[M].北京：高等教育出版社，2009：101
[3]龚沛曾. Visual Basic程序设计教程（第2版） [M].北京：高等教育出版社，2003：98-99
[4]郑远攀，石岩，金钊.数学分析在程序算法设计教学中的应用[J].华北水利水电学院学报（社科版），2013（3）
[5]王沁，李磊，陆成勇.平均计算时间复杂度优化的动态粒子群优化算法[J].计算机科学.2010（3）
作者简介：
陈永华，男，博士、副教授，研究方向为计算机图形学、地理信息系统。
【关键词】程序设计 穷举算法 优化
【中图分类号】G642 【文献标识码】A 【文章编号】2095-3089（2013）09-0127-02
穷举算法是计算机程序设计中常用的一种问题求解策略。其基本思想是对问题的所有可能状态一一测试，直到找到解或将全部可能状态都测试过为止。求解此类问题往往要排除明显不符合条件的情况，使问题得以简化。虽然计算机运算速度很快，用穷举算法求解，一般问题可很快得出结果，但从程序可读性、正确性和算法效率等角度考虑，借助数学分析方法，实现此类问题的过程优化，对于培养良好的编程风格具有重要的影响和作用。
本文以古代的“百钱买百鸡”问题为例，通过对该例VB程序设计教学的实例分析，探讨程序设计优化的过程和方法，以及对学生创新思维培养的作用。
1.问题的引入
穷举问题是一种重复性算法，一般以计数方法设定循环次数，然后逐步测试，完成测试次数后结束循环，得到全部符合条件的结果。
如百钱买百鸡问题：已知公鸡三元一只，母鸡二元一只，小鸡一元钱三只，现要求用一百元买一百只鸡，给出买鸡方案。
设定可买公鸡X只，母鸡Y只，小鸡Z只，则可建立数字模型
X+Y+Z=100 （1）
5×X+3×Y+Z/3=100 （2）
从题意出发，可容易地建立三重循环实现如下基本程序：
程序一：
Private Sub Command1_Click（）
Dim x as integer， y as integer， z as integer
Dim count As Long
Cls
For x = 0 To 100
For y = 0 To 100
For z = 0 To 100
If x + y + z = 100 And 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next z
Next y
Next x
Print “循环次数”； count
End Sub
程序运行后，结果如图1：其中内层循环体执行次数为103万次，运行效率低下。
2.算法的初步优化
在穷举算法程序设计中，有许多种情况是明显不符合要求的，可在程序优化中先消除掉[1]。
上例中，公鸡X，母鸡Y的循环次数，因售价所限，取值分别为 0<=X<=20， 0<=Y<=33，小鸡为3的倍数，所以上面程序中循环部分的上界和步长可改写为：
程序二：
Private Sub Command2_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 20
For y = 0 To 33
For z = 0 To 100 Step 3
If x + y + z = 100 And 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next z
Next y
Next x
Print “循环次数”； count
End Sub
初步改进后，内层循环体执行次数降低为24276次，运行效率提高50倍。
3.算法中循环层数的简化
穷举算法程序一般根据相关因素的个数建立多层循环嵌套构成，而各层循环之间与问题所要求的条件具有密切的联系，因此，在教学过程中，引导学生通过分析有关条件，可将有的循环层进行简化或去掉。对学生的素质训练是一个重要的提高。
上例中，由于X+Y+Z=100，故可去掉Z层循环，Z值由Z=100-X-Y确定。
程序三：
Private Sub Command3_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 20
For y = 0 To 33
z = 100 - x - y
If 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next y
Next x
Print “循环次数”； count
End Sub
去掉Z层循环，内层循环体执行次数降低为714次，运行效率提高30倍。
与学生一起进一步分析，上述过程中，条件5*x+3*y+z/3=100需要做三次乘除运算，且除法实数运算复杂， 比整数运算效率差异较大。一种解决办法是，将除法的分母去掉，即条件改为：15*x+9*y+z==300，则只需做两次乘法运算。但该方法降低了程序的可读性。因此，程序设计过程中，需考虑运行效率与可读性之间的矛盾和取舍。 第二个问题是，本节以X，Y建立两重循环，同学们还可以以X，Z或Y，Z建立两重循环，测试内层循环体执行次数是否减少优化。
4.数学论证对程序优化的作用
通过前面的讨论，程序运行效率提高数十成百倍，基本达到了学生优化意识训练目的，有关教材的讨论也到此为止了[2，3]多数学生也认为这已是最好的结果。
但是程序优化的问题多数是数学求解问题，因此引导学生对问题的运行结果进行数学分析，用数学推导为程序优化提供充分的依据，甚至得出更好的优化结果[4，5]。这个提示引起学生极大的兴趣，课后全班学生积极研究探讨，取得了一系列优秀成果。整理总结有以下几个方面的内容。
4.1 循环变量上下界的取值范围的优化
由（2）式乘3，可得
15×X+9×Y+Z==300 （3）
（3） -（1）除 2 得 7×X+4×Y=100 （4）
由 （4） 得
X=（100-4Y）/ 7 <= 100/7 <15 （5）
所以 X为 0 <=X <=14 中的整数
同理， Y=（100-7×X）/ 4 <=25 （6）
所以 Y为 0 <=Y <=25 中的整数
通过推导X，Y的取值范围，循环可改为：
程序四：
Private Sub Command4_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 14
For y = 0 To 25
z = 100 - x - y
If 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next y
Next x
Print “循环次数”； count
End Sub
由此，内层循环体执行次数降低为390次。
同样，可推导Z的取值为，75<=Z<=85的整数。
4.2 运行结果的数学分析
阅读运行结果，我们发现有如下结论：a.X取值为4的整数倍，Z的取值为3的整数倍；b.Y取值为公差为 7 的等差数列。同学们也做了完整的论证。
例如，由（6）式 Y=（100-7×X）/4，因为Y为整数，所以7×X/4为整数，故X为4的整数倍。因此循环可改为：
程序五：
Private Sub Command5_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For x = 0 To 14 Step 4
For y = 0 To 25
z = 100 - x - y
If 5 * x + 3 * y + z / 3 = 100 Then
Print x， y， z
End If
count = count + 1
Next y
Next x
Print “循环次数”； count
End Sub
由此，内层循环体执行次数降低为104次。
4.3 通过数学推导建立单层循环
一些同学做了更深入的讨论，在一、二节数学分析的结论支持下，进一步提出将X，Y的取值通过Z的函数关系求得，由此建立Z的单层循环实现。
由（1）（3）式消去Y，得到
X=4×Z/3-100 （7）
结合一、二节的相关结论，循环可改为：
程序六：
Private Sub Command6_Click（）
Dim x%， y%， z%
Dim count As Long
Cls
For z = 75 To 85 Step 3
x = 4 * z / 3 - 100
y = 100 - x - z
Print x， y， z
count = count + 1
Next z
Print “循环次数”； count
End Sub
这样，内层循环体执行次数只需4次，且每次循环做两次乘除法运算！
确实让我们感受到数学方法对程序优化过程的强大作用。
5.程序优化的效率分析
综述以上各节的讨论，以内层循环执行次数为主要指标，可列出下表：
6.结语
由本文以上分析可以看出，随着程序的逐步优化，程序运行效率得以成百上千倍的提高。但是引入数学方法后，程序运行效率提高更为明显，但是程序的可读性明显降低，需要在程序代码中添加注释详细予以说明。因此，程序的优化过程要考虑运行效率和程序可读性的取舍平衡。
虽然计算机运算速度不断提高，小型程序优化与否对运行时间影响有限。但是程序优化技能的培养，数学工具的应用，对学生增强编程兴趣，提高创新意识，尤其在大型软件过程设计质量的提高方面具有重大作用。
参考文献：
[1]石海鹤，石海鹏，郑宇军.算法程序变换研究与进展[J].计算机科学.2007（11）
[2]王贺明. Visual Basic程序设计教程[M].北京：高等教育出版社，2009：101
[3]龚沛曾. Visual Basic程序设计教程（第2版） [M].北京：高等教育出版社，2003：98-99
[4]郑远攀，石岩，金钊.数学分析在程序算法设计教学中的应用[J].华北水利水电学院学报（社科版），2013（3）
[5]王沁，李磊，陆成勇.平均计算时间复杂度优化的动态粒子群优化算法[J].计算机科学.2010（3）
作者简介：
陈永华，男，博士、副教授，研究方向为计算机图形学、地理信息系统。