论文部分内容阅读
【摘要】算法优化是程序设计教学的重要内容,对培养学生创新思维和良好编程风格具有重要作用。本文以古代“百钱买百鸡”为教学案例,通过数学推导论证,深入讨论了穷举算法逐步优化的方法和分析,在提高学生的编程兴趣和技能训练方面取得了良好的教学效果。
【关键词】程序设计 穷举算法 优化
【中图分类号】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)
作者简介:
陈永华,男,博士、副教授,研究方向为计算机图形学、地理信息系统。