1700414800
1700414801
作为程序员的修养，表5.1列出了笔者认为最低限度应该了解的典型算法。这些算法包括刚刚介绍过的求解最大公约数的“辗转相除法”，判定素数的“埃拉托斯尼筛选法”（将在后面介绍），检索数据的三种算法以及排列数据的两种算法。记住了这些典型算法固然好，但请注意绝不要丢掉自己思考算法的习惯。
1700414802
1700414803
表5.1 主要的典型算法
1700414804
1700414805
名称 用途
1700414806
1700414807
辗转相除法 求解最大公约数
1700414808
1700414809
埃拉托斯特尼筛选法 判定素数
1700414810
1700414811
顺序查找 检索数据
1700414812
1700414813
二分查找 检索数据
1700414814
1700414815
哈希查找 检索数据
1700414816
1700414817
冒泡排序 数据排序
1700414818
1700414819
快速排序 数据排序
1700414820
1700414821
再试着思考一个具体问题吧。这次请思考一下解决“求解12和42的最小公倍数”这个问题的算法。所谓最小公倍数就是指两个整数的公共倍数（是一个数几倍的数）中最小的那个数。最小公倍数的求解方法在中学的数学课上应该学过了，但很可惜求解步骤是依赖人类的直觉的。请再思考一个适用于计算机的机械的算法。说不定会想“反正会有经典算法的吧，比如‘某某法’，然后就纠结于是否还要自己思考。
1700414822
1700414823
但即使查了算法辞典之类的书，也还是找不到求解最小公倍数的算法。为什么呢？因为我们可以通过以下方法求解最小公倍数–用两个整数的乘积除以这两个整数的最大公约数，因此12和42的最小公倍数就是12*42/6=84了。如此简单的算法不能算典型算法，这个例子说明先自己思考算法，再云应用典型算法这一点很重要。
1700414824
1700414825
1700414826
1700414827
1700414829
计算机是怎样跑起来的 5.5 要点4：利用计算机的处理速度
1700414830
1700414831
这次再请思考求解“判定91是否是素数”这一问题的算法。在用于判定素数的典型算法中，有一个被称为“埃拉托斯特尼筛选法”的算法，在学习这个算法前，先请思考如果是在数学考试中遇到这道题，如何解答呢？
1700414832
1700414833
也许有人会这样想：用91分别除以比较它小的所有正整数，如果没有找到能够整除的数，那么91就是素数。但，如此繁琐的步骤可行吗？实际上这就是正确答案。埃拉托斯特尼筛选法是一种用于把某个范围内的所有素数筛选出来的算法，比如筛选100以内的所有素数，其基本思路就是用待判定的数除以比较它小的所有正整数。例如要判定91是否是素数，只要分别除以2-90之间的每个数就可以了（因为1肯定能够整除任何数，所以从2开始检测）。这个步骤用程序表示的话，就变成了如代码清单5.2所示的代码。Mod是用于求除法运算中余数的运算符。如果余数为0则表示可以整除，因此也就知道待判定的数不是素数了，程序执行结果如图5.4所示
1700414834
1700414835
代码清单5.2 判定是否是素数的程序
1700414836
1700414837
a=91
1700414838
1700414839
s=”素数”
1700414840
1700414841
For i=2 to (a-1)
1700414842
1700414843
If a Mod i =0 Then
1700414844
1700414845
s=”不是素数”
1700414846
1700414847
Exit For
1700414848
1700414849
End If
[
上一页 ]
[ :1.7004148e+09 ]
[
下一页 ]