| bbschat |
2008-03-19 01:52 |
测试题(00001) 从平凡到精彩！
本文应管理员 lgn21st 同志要求提供测试题(00001) 的解题思路而写。
题目：
求满足以下条件的所有数的和
1：小于1000的自然数
2：3或者5的倍数
不考虑任何算法，直接根据题意采用暴力枚举，我们可以得到如下的代码：
s = 0
1.upto(999) {|v| s += v if (v % 3 == 0 or v % 5 == 0)}
p s
调试，一秒不到程序通过，233168，恭喜你得到正确的结果！
上面这段代码很好理解，至少达到一个合格程序员的标准，相信你的项目经理绝不会因这段代码而为难你的。
如果你就此满足了，那好，就此打住，不用再往下看了。
如果你的层次再高些，比如一个项目经理，你也许会想，今天客户要1000以内3和5的倍数，
保不齐改天又想要10000以内3和7的倍数，那样的话，为了让程序具有共通性，我们得到如下的代码：
# 传入一个数组（所有约数，比如[3,5]）和一个数字v
# 如果v是数组中其中一个的倍数则返回v，否则返回0（表示不需要累加）
def c(a, v)
a.each {|k| return v if v % k == 0}
return 0
end
#传入一个数组（所有约数，比如[3,5]）和一个最大数
#1到（最大数-1）中进行枚举，将经过上个函数处理的结果进行累加
def f(a, x)
s = 0
1.upto(x - 1) {|v| s += c(a, v)}
return s
end
然后我们可以通过下面的函数调用得到结果。
p f([3,5], 1000)
OK，和前面的结果一样。
最大数加个0再试试
p f([3,5], 10000)
23331668！还是很快。
再加2个0试试，
p f([3,5], 1000000)
这下程序开始有点慢了，等了一下，答案才出来
233333166668
毕竟程序要循环近2百万次，慢点也是正常的。
总得来说感觉还是不错，能不能再进步一点呢？
现在让我们站在一个追求效率的高级程序员的角度上再研究一下第一个程序
哪里拖累了程序？
首先第一感觉就是判断
if (v % 3 == 0 or v % 5 == 0)
是否有可能去掉判断呢？
答案是肯定的，考察一下我们要处理的数字
3的倍数
3,6,9,12,15,18,21,24,27,30.......999
求和可以用
s1 = 0
3.step(999,3) {|v| s1 += v}
p s1
然后是5的倍数
5,10,15,20,25,30......995
求和可以用
s2 = 0
5.step(995,5) {|v| s2 += v}
p s2
项目经理出现了，拜托你写个共通的求和函数吧，OK
def s(a, x)
s = 0
a.step(x - 1,a) {|v| s += v}
return s
end
让我们来看看结果
p s(3, 1000) + s(5, 1000)
奇怪，怎么答案是266333，不是原来的233168？
仔细检查一下，原来我们把3和5共同的倍数也就是15的倍数计算了2遍！
那很简单，减掉就是咯
p s(3, 1000) + s(5, 1000) - s(15, 1000)
这下答案对了。
连续的输入3个1000让人感觉很不舒服，要是那个程序员不小心少输一个0，
找个BUG还真不容易，还是把最大值定义成常量比较好。
$max = 1000
def s(a)
s = 0
a.step($max - 1,a) {|v| s += v}
return s
end
p s(3) + s(5) - s(15)
这下舒服多了，给$max 加上3个0，1百万，看看，
速度比原来确实快了点。
还能再快吗？速度真的不能再提升了吗？
或者你已经累了，那就休息去吧，但你可能错过接下来最精彩的部分。
如果你还想更进一步，真的相信程序还有提升的空间，
那我们就继续往下看。
再考察这些3的倍数
3,6,9,12,15,18,21,24,27,30.......999
等等，好像他们都是3的倍数啊（废话 - -!）
那么我们似乎可以用
3 * （1 + 2 + 3 + 4 + ....333） 来计算他们的和。
括号里面的东西似曾相识吗？
那个小学就学过的课文，那个快速把1到100求和结果算出的不到10岁的高斯？
对了！
恭喜你，向最终解法接近了重要的一步。
让我们回忆一下高斯是怎么算的？
他将100个数头尾组合变成（1+101） + （2+99） +... + (49 + 52) + (50 + 51)
= 50 × 101 = 5050
整理成公式表达如下
1...n的求和公式是 n * (n + 1) / 2
那么 3 ... 3n 的求和公式是 3 * n * (n + 1) / 2
现在我们有思路了，修改一个上面的程序
先计算最大数以内满足 x 倍数的所有数的个数 n ，再对 1... n 求和，再将结果乘以 x。
$max = 999
def s(x)
n = $max / x
x * n * (n + 1) / 2
end
p s(3) + s(5) - s(15)
这里请注意函数的第一行
n = $max / x
因为是整数相除的结果付给一个变量 n，所以聪明的 Ruby 默认 n 也是一个整数，
如果 x 不能被 $max 整除，那么多余的小数点会被 Ruby 自动舍弃，正好满足我们的要求。
如果有自作聪明的同学想把第一行去掉，第 2 行改成
$max = 999
def s(x)
$max * ($max / x + 1) / 2 ，
end
呵呵，答案可就不对了，为什么，请自己思考……
再试一下最大值 $max 改成 1百万，1千万，1个亿，
程序再无停顿，每次都飞快的给出结果。
那是，没有循环，没有判断，只有简单的四则计算，程序当然快。
好了，程序至此，减无再减，快无再快，
最后回顾一下测试题(00001)
$max = 999
def s(x)
n = $max / x
x * n * (n + 1) / 2
end
完美境界终于达成～
感谢所有耐心看完全文的朋友，以此文与所有的Ruby程序员共勉！
[ 本帖最后由 bbschat 于 2008-3-19 15:25 编辑 ] |
|