您所在位置：社区首页 — Visual Basic讨论区 — 从“水仙花数”谈起——漫谈设计思路对程序效率的影响
老大徒伤悲
[专家分：29120] 发布于 2014-12-22 10:37:51
水仙花数的算法本身，因为其总消耗都没有多少，在硬件速度和容量不断飞速发展的情况下，不论如何改进都没有多大的意义。但用它来从程序的设计思路方面探讨算法的改进，说明算法改进的意义、改进的方法等，还是有些价值的。
所谓“水仙花数”，是指将一个数字各位都看成一个独立的数字，并将这些独立的数字各自立方然后求和，若这个和与原数想等，那么这个原数就是“水仙花数”。这里说的都是正整数，说小数没有意义，因为各位数独立后的立方和都是整数；而负数则因为没有规定符号的处理，也没有意义。
至于“水仙花”这个名称的来源，因与算法没有关系，不予考证。
本文示例以三位数为例，代码则用vb6.0书写。
11 楼
老大徒伤悲 [专家分：29120] 发布于 2014-12-22 11:04:29
十一、 继续优化（二）
乘法的运算次数减下来后，加法的运算次数成为最多的了，能不能用减少乘法的方法减少加法呢？
Private Sub Command1_Click()
Dim l As Integer, m As Integer, n As Integer
Dim Lf(9) As Integer, Bw As Integer
Dim S As Integer, S2 As Integer, Lf2 As Integer
For m = 0 To 9
Lf(m) = m * m * m
Next m
For l = 1 To 9
Bw = l * 100
For m = 0 To 9
S2 = Bw + m * 10
Lf2 = Lf(l) + Lf(m)
For n = 0 To 9
S = S2 + n
If Lf2 + Lf(n) = S Then Print S
Next n
Next m
Next l
End Sub
引入前两位的和（S2）和前两位数目立方和（Lf2），减少部分重复计算。
共使用循环控制4个，实际建立和撤销循环控制l：1次（执行9次）；m：1+9次（执行10次和90次）；n：90次（执行900次），共计101次。乘法119次、加法1980次、赋值1099次、相等判断900次，输出4次。使用变量17个（计34字节）。
与第六种算法（取消乘方）比较，乘法减少了801次，整除运算1800次、减法900次、取余900次全取消，加法增加了1980-1800=180次，赋值增加了189次，循环增加了2个层次共99次创建和撤销。总体看，应该是取得了好的效果的。
12 楼
老大徒伤悲 [专家分：29120] 发布于 2014-12-22 11:07:01
十二、 字符串的组合
那么，这种多层次循环的组合方案是否可以套用到字符串方式上呢？如果能，有能取得些什么？是优化，还是劣化？我们来试试看。
Private Sub Command1_Click()
Dim l As Integer, m As Integer, n As Integer
Dim Lf(9) As Integer
Dim S As Integer, S2 As Integer, Lf2 As Integer
For m = 0 To 9
Lf(m) = m * m * m
Next m
For l = 1 To 9
For m = 0 To 9
S2 = l & m
Lf2 = Lf(l) + Lf(m)
For n = 0 To 9
S = S2 & n
If Lf2 + Lf(n) = S Then Print S
Next n
Next m
Next l
End Sub
共使用循环控制4个，实际建立和撤销循环控制l：1次（执行9次）；m：1+9次（执行10次和90次）；n：90次（执行900次），共计101次。乘法20次、加法990次、字符串拼接990次、赋值1100次、相等判断900次，输出4次。使用变量16个（计32字节）。
与上一算法（继续优化（二））比较，控制部分完全相同，乘法少了99次、加法少了990次，变量少用了一个；赋值多了1次、字符串拼接多了990次。其余相同。相差不大，可以说稍有改良。
与字符串拆分算法（字符串的妙用）相比较：控制方面，循环多了两层，多99次创建和撤销。运算方面，加法少了810次、字符串截取2700次全取消；字符串拼接增加了990次、赋值增加了1090次；其余乘法、判断、输出都一样。变量上多用5个。总体可以认为有所改进。
13 楼
老大徒伤悲 [专家分：29120] 发布于 2014-12-22 11:08:44
本文仅以水仙花数为例从设计思路的角度谈了算法的设计。当然，算法的精髓远不在于此，例如复杂度等概念，都没有涉及到；再例如内存的占用上只考虑了变量占用空间，没有考虑程序本身的占用空间等等。
另外，不同语言的一些具体指令，也对设计思路有着一定的影响。
14 楼
孙瑞 [专家分：590] 发布于 2015-01-03 16:48:54
点赞！
从我的经历来看，优化程序主要是简单的几点：
1、重复用的数据使用变量缓存起来（空间换时间）
2、计算性的东西改成取数性的（建立表，查表提高效率）
3、减少循环、堆栈。
16 楼
孙瑞 [专家分：590] 发布于 2015-01-17 22:01:08
您尚未登录，请登录后再回复。点此登录或注册
