从“水仙花数”谈起——漫谈设计思路对程序效率的影响

主题：从“水仙花数”谈起——漫谈设计思路对程序效率的影响

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:37:51

水仙花数的算法本身，因为其总消耗都没有多少，在硬件速度和容量不断飞速发展的情况下，不论如何改进都没有多大的意义。但用它来从程序的设计思路方面探讨算法的改进，说明算法改进的意义、改进的方法等，还是有些价值的。

所谓“水仙花数”，是指将一个数字各位都看成一个独立的数字，并将这些独立的数字各自立方然后求和，若这个和与原数想等，那么这个原数就是“水仙花数”。这里说的都是正整数，说小数没有意义，因为各位数独立后的立方和都是整数；而负数则因为没有规定符号的处理，也没有意义。

至于“水仙花”这个名称的来源，因与算法没有关系，不予考证。

本文示例以三位数为例，代码则用vb6.0书写。

本帖地址： http://bbs.pfan.cn/post/410571.html

回复列表（共19个回复）

沙发

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:41:17

一、定义算法

Private Sub Command1_Click()
   Dim m As Integer, n As Integer
   Dim a As Integer, b As Integer, c As Integer
   Cls
For m = 100 To 999
       a = Int(m / 100)
       b = Int((m - a * 100) / 10)
       c = m - a * 100 - b * 10
       n = a ^ 3 + b ^ 3 + c ^ 3
       If n = m Then Print m
   Next m
End Sub

这是依据“水仙花数”的定义做出的代码。作为初学者练习循环控制、数位转换，这个代码已经能达到目的了。

但是这是最原始的算法，效率低，内存开销较小。循环控制1个执行900次，乘方2700次、除法1800次、乘法2700次、减法2700次、加法1800次、取整运算1800次、赋值3600次、相等判断900次，输出4次。变量共使用存储单元5个双字节，即10个字节。

板凳

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:44:19

二、改进细

变量n，它表示立方和。在算法里，被计算出来后，只因用了一次，就被放弃。没有单独使用变量的价值，可以取消。但取消后，可能减弱程序的易读性。变量a、b、c都存在这一问题。

变量c，表示个位的数值。其计算思路是原值减去整百、减去整十后获得。Basic提供有一个取余运算，可以用来简化为，原数整除10后的余数。

Private Sub Command1_Click()
   Dim m As Integer
   Dim a As Integer, b As Integer, c As Integer
Cls
   For m = 100 To 999
       a = Int(m / 100)
       b = Int((m - a * 100) / 10)
       c = m Mod 10
       If a ^ 3 + b ^ 3 + c ^ 3 = m Then Print m
   Next m
End Sub

这样一来，新的代码循环控制1个执行900次，乘方2700次、除法1800次、乘法900次、减法900次、加法1800次、取整运算1800次、取余运算900次、赋值2700次、相等判断900次，输出4次。变量共使用存储单元4个双字节，即8个字节。

主要减少了乘法1800次、减法1800次，增加了取余900次。

当然，b、c两个变量也可以不用，全部纳入判断表达式内，可以再减少4个字节的占用，更中的是减少1800次赋值（变量a不但在计算离方式要用，而且在计算b时也要用，所以跟b、c不一样）。但是，之所以没有这样做，不单纯是考虑程序的易读性，同时更考虑到乘方是一个巨大的运算，试图在后面从根本上改变它。这就涉及到了空间占用和时间占用之间的折中平衡问题。在本题中，空间占用很少而时间占用很大，能够用空间换取时间的时候，我们应积极考虑。反之亦然，在空间占用很大而时间占用很少的时候，我们赢考虑用时间换取空间。

3 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:47:01

四、利用数据类型

Basic提供了赋值时按照被赋值变量的类型自动转换，没有特殊情况时，不需要再次使用类型转换函数。有鉴于此，我们的两个取整函数都可以不要了，这就有可以省去1800次取整运算。

更进一步，Basic还提供了一种运算叫做整除，整除的运算效率被浮点除法的效率当然要高，而我们代码周发给您的除法恰恰都是为了获得商的整数部分，而不需要考虑小数或者余数，所以我们将除法运算换成整除运算。

至此，代码修改为：

Private Sub Command1_Click()
    Dim m As Integer
    Dim a As Integer, b As Integer, c As Integer
    For m = 100 To 999
        a = m \ 100
        b = (m - a * 100) \ 10
        c = m Mod 10
        If a ^ 3 + b ^ 3 + c ^ 3 = m Then Print m
    Next m
End Sub

新的代码循环控制1个执行900次，乘方2700次、乘法900次、整除1800次、减法900次、加法1800次、取余运算900次、赋值2700次、相等判断900次，输出4次。变量共使用存储单元4个双字节，即8个字节。

这次改进只是将1800次浮点除法变为1800次整除运算、取消1800次取整运算。

4 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:48:44

四、一种极

到此为止，小打小闹的常规思路已经再难做出什么改进了，唯一能做的就是取消1800次赋值运算和2个变量。

Private Sub Command1_Click()
    Dim m As Integer
    For m = 100 To 999
        a = m \ 100
If  a ^ 3 + ((m -  a * 100) \ 10) ^ 3 + (m Mod 10) ^ 3 = m Then Print m
    Next m
End Sub

这段代码循环控制1个执行900次，乘方2700次、乘法900次、整除1800次、减法900次、加法1800次、取余运算900次、赋值900次、相等判断900次，输出4次。变量共使用存储单元2个双字节，即4个字节。

5 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:50:08

五、空间换时间

如前所述，对这段代码而言，其变量使用内存很少，而数学计算不但量大而且复杂。降低计算代价是最重要的，哪怕为此多设一点变量多开销些内存也是值得的。

抓主要矛盾，这是辩证唯物主义的核心之一。在这里，最该段的数学运算是乘方，而且次数高大2700次，也是所有运算里次数最多的！所以，在这里乘方运算的改良已经是我们的首要对象了。

两个思路，一个是彻底不用乘方；二一个是减少乘方的运输次数。两相比较，第二种思路较容易实现。因为我们考察就会发现，不论百位、十位还是个位，我们计算了2700次乘方，都是些什么，都是0³、1³、2³……9³，一共就这个九个，反反复复计算了2700次！那么我们设10个变量，也就是用20个字节就可以换回2690次的乘方运算，这是极为划算的。当然为此，我们还有些微辅助工作的代价也要付出。按此思路，代码初步改为：

Private Sub Command1_Click()
    Dim m As Integer, Lf(9) As Integer
    Dim a As Integer
    For m = 0 To 9
        Lf(m) = m ^ 3
    Next m
    For m = 100 To 999
        a = m \ 100
        If Lf(a) + Lf((m - a * 100) \ 10) + Lf(m Mod 10) = m Then Print m
    Next m
End Sub

新的思路，循环控制2个，一个执行10次，一个执行900次，乘方10次、乘法900次、整除1800次、减法900次、加法1800次、取余运算900次、赋值910次、相等判断900次，输出4次。变量共使用存储单元12个双字节，即24个字节。

增加了一个循环控制，10次循环和10个变量（共20字节），以及赋值10次；减去了890次乘方。这是很值得的。

6 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:52:01

六、取消乘方

乘方的运算原理是，先对底数取自然对数，在乘以指数，然后再以积作为指数、e为底数的乘方运算。其复杂程度是相当大的，所以在有条件的情况下，尽量将其处理为乘法运算。但是①乘方的指数不确定，也就是为变量时显然我们不能改为乘法，②指数很大，例如成千上万的时候，改为乘法得不偿失，③指数不是整数的情况，也不能改为乘法。不过恰好，我们的问题不在此列，是可以改为乘法的。

Private Sub Command1_Click()
    Dim m As Integer, Lf(9) As Integer
    Dim a As Integer
    For m = 0 To 9
        Lf(m) = m * m * m
    Next m
    For m = 100 To 999
        a = m \ 100
        If Lf(a) + Lf((m - a * 100) \ 10) + Lf(m Mod 10) = m Then Print m
    Next m
End Sub

循环控制2个，一个执行10次，一个执行900次，乘法920次、整除1800次、减法900次、加法1800次、取余运算900次、赋值910次、相等判断900次，输出4次。变量共使用存储单元12个双字节，即24个字节。

增加了乘法20次，取代了10次乘方运算。至此，彻底不在使用乘方了。

7 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:55:46

七、字符串的妙用

但是，是不是上面的代码就是一个完美的算法呢？还有大量的数学运算在里面，这些还有没有改进的余地呢？

现在，剩余的数学运算除了为计算立方的20次乘法外，都是计算原数的各位数值的了。那么，我们人类看数字，各个位的值是这样算出来的吗？不是，我们可以直接读出来呀？计算机能不能也这样呢？答案是肯定的，Basic有一种字符串处理功能，就很接近我们人类读写数字了。Mid函数可以一位一位的读取数值。

Private Sub Command1_Click()
    Dim m As Integer, Lf(9) As Integer
    For m = 0 To 9
        Lf(m) = m * m * m
    Next m
    For m = 100 To 999
        If Lf(Mid(m, 1, 1)) + Lf(Mid(m, 2, 1)) + Lf(Mid(m, 3, 1)) = m Then Print m
    Next m
End Sub

字符串思路下，共用循环控制2个，一个执行10次，一个执行900次，乘法20次，字符串截取运算2700次，加法1800次，赋值10次，相等比较900次，输出4次，使用变量11个（共22字节）。

这次改进减少乘法900次、整除1800次、减法900次、取余900次、赋值900次；增加字符串截取运算2700次。

8 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:57:41

八、组合的思路

上述所有的方法都是先确定原数，再将其多位数拆分为单独的数字进行的。有时候，我们可以反过来，用各位数去构建一个原数。

Private Sub Command1_Click()
    Dim s As Integer, l As Integer, m As Integer, n As Integer
    Dim Lf(9) As Integer
    For m = 0 To 9
        Lf(m) = m * m * m
    Next m
    For l = 1 To 9
        For m = 0 To 9
            For n = 0 To 9
                s = l * 100 + m * 10 + n
                If Lf(l) + Lf(m) + 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次。乘法1820次、加法3600次、赋值900次、相等判断900次，输出4次。使用变量14个（计28字节）。

显然，这是一个未经优化的方法。

9 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 10:59:19

九、组合的优化

我们仔细思考就会发现，里面有些东西在被反复计算。例如，核心计算s同900次，其中前100次l*100的都是在做“1*100”的计算，后边“2*100”“3*100”……“9*100”，呵呵，都连续做了100次。那么，能减少吗？它们都是百位的值，而且连续，应该是可以的。

Private Sub Command1_Click()
    Dim S As Integer, l As Integer, m As Integer, n As Integer
    Dim Lf(9) As Integer, Bw 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
            For n = 0 To 9
                S = Bw + m * 10 + n
                If Lf(l) + Lf(m) + Lf(n) = S Then Print S
            Next n
        Next m
    Next l
End Sub

这里又增加了一个变量，用来将900次乘法减少为9次，减少了891次。

10 楼

老大徒伤悲 [专家分：29120] 发布于 2014-12-22 11:01:50

十、继续优化（一）

那么计算十位的乘法能不能类似处理减少乘法的运算呢？能！只是效果没有这么大而已。

Private Sub Command1_Click()
    Dim S As Integer, l As Integer, m As Integer, n As Integer
    Dim Lf(9) As Integer, Bw As Integer, Sw 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
            Sw = m * 10
            For n = 0 To 9
                S = Bw + Sw + n
                If Lf(l) + Lf(m) + Lf(n) = S Then Print S
            Next n
        Next m
    Next l
End Sub

这里再次增加一个变量Sw，用来减少乘法，将原来计算十位的900次乘法减少到90次。

共使用循环控制4个，实际建立和撤销循环控制l：1次（执行9次）；m：1+9次（执行10次和90次）；n：90次（执行900次），共计101次。乘法20+9+90=119次、加法3600次、赋值10+9+90+900=1009次、相等判断900次，输出4次。使用变量16个（计32字节）。

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：从“水仙花数”谈起——漫谈设计思路对程序效率的影响

回复列表（共19个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题： 从“水仙花数”谈起——漫谈设计思路对程序效率的影响

回复列表 （共19个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：从“水仙花数”谈起——漫谈设计思路对程序效率的影响

回复列表（共19个回复）