《常用算法》PPT课件.ppt

1、常 用 算 法-,排序算法 -比较互换 选择法 冒泡法 查找算法 -顺序查找 折半查找 素数的求法 -定义法 筛选法 解一元方程 -牛顿迭代法 二分法 数值积分 -矩形法 梯形法 辛普生法 数值转换 -BODH,7.1 常用的排序算法,1：比较互换法 基本过程（以降序为例）：将第一个元素顺序与其后面的元素比较，比第一个大则进行交换，第一轮完毕后，最大的元素被挪到了第一个位置，第二轮从第二个元素开始重复上面的过程，结束后得到第二个最大的元素，如此下去经过 N-1 轮的比较，可将 N 个数排好,:举例 原始数据： 1，2，3，5，4 要求：降序,第 一 轮 比 较 ：,1 2 3 5 4,2 1

2、3 5 4,3 1 2 5 4,5 1 2 3 4,5 1 2 3 4,第一轮结束，找到最大值 5,第 二 轮 比 较 ：,5 1 2 3 4,5 2 1 3 4,5 3 1 2 4,5 4 1 2 3,第二轮结束，找到第二最大值 4,第三轮结果：5 4 3 1 2,第四轮结果：5 4 3 2 1,公式表示：(N为排序的维数, OP为操作，降序为 “”) for (i=1 to N-1)外层循环N-1次 for (j=i+1 to N)内层依赖外层 if （S(j) OP S(i)）then t=S(i):S(i)=S(j):S(j)=t交换 End if Next j Next IVB例题点

3、此进入,2：选择法排序,特点：比较後不立即互换元素，而是记下其位置并在每一轮比较完毕后和（）互换 首先，比较的元素不同，以降序为例，是当前元素与上次比较後的最大元素进行比较，因此，在进行比较之前，要有一个初始化最大元素的过程 其次，确定完毕的元素的互换是在每一轮完成后进行的，而不是在比较後进行的 再次，互换元素的不同，为（i）和（iMax） :举例 原始数据： 3，5，7，9，4 要求：降序,第一轮比较，初始化设最大元素下标为 3579 iMax=1 iMax=2 3579 iMax=2 iMax=3 3579 iMax=3 iMax=4 3579 iMax=4 iMax=4 S(1) S(i

4、Max)的结果 9573,如此下去，第二轮找到7，第三轮5， 选择法的公式表示：,For i=1 to N-1 iMax=I初始化iMax,在每轮比较开始处 for j=I+1 to N if(S(j) OP S(iMax) then iMax=j next j 注意比较对象的转变 t=S(i):S(i)=S(iMax):S(iMax)=t 注意互换的时间 Next IVB例题点此进入,：冒泡法排序 如果按升序排序，则方法为： 将相邻两个数比较，把小数对调到前边，如此进行一轮後，就会把最大的数互换到最后，再进行一次，则会把第二大数排在倒数第二的位置上，进行次後，整个数列即可排好 在这种排序过程

5、中，小数如气泡一样逐层上伏，而大数逐个下沉，因此，被形象的喻为“冒泡” 特征： 当数据的大小顺序与要求不符时（逆序），才进行互换操作,第 一 轮 比 较 ：,9 4 7 5 2,4 9 7 5 2,4 7 9 5 2,4 7 5 9 2,4 7 5 2 9,第一轮结束，最大值 9沉到最底,第 二 轮 比 较 ：,4 7 5 2 9,4 7 5 2 9,4 5 7 2 9,4 5 2 7 9,第二轮结束，次大值7沉到倒数第二,冒泡法的公式表示：,For i=1 to N-1 for j=1 to N-i比较次数逐次减少 if(S(j) OP S(j+1) then t=S(j):S(j)=S(j

6、+1):S(j)=t立即互换 end if next j next i,7.2 常用的查找算法,7.2.1 顺序查找 顺序查找表现是把待查找的数与数组中的数从头到尾逐一比较，用一变量 P 来表示当前比较的位置，初始为1，当待查找的数与数组中 P 位置的元素相等时即可结束,否则 P=P+1 继续比较，当 P 大于 数组的最大长度,也应该结束 注意退出的两种情况，分别为找到和P大于数组的最大长度,用Do While进行顺序查找（为待查找的数）：,P=1初始化比较位置 Do while xS(p) And pN p=p+1 Loop 退出的两种情况 If x=S(p) then 找到，处理 else

7、 没找到，处理 end ifVB例题点此进入,用For Next进行顺序查找（为待查找的数）：,For p = 1 To N If a(p) = x Then Exit For End If Next 退出的两种情况 If p N Then 没找到，处理 Else 找到，处理 End If VB例题点此进入,7.2.2 折半查找 折半查找法是对有序数列进行查找的一种高效查找办法，其基本思想是逐步缩小查找范围，因为是有序数列，所以采取半分作为分割范围可使比较次数最少. 比较过程:（设数列已做降序排序处理） 设置三个指针,分别指向数组序列 S 的Top,Bottom和Middle,其中Middle

8、=(Top+Bottom)/2,进行下列判断,1 3 4 6 8 10 12 15 18 20 25,X = 15,1) 若待查找的数 X 等于S(Middle),则已经找到,位置就是Middle.否则进行下面的判断. 2) 如果 X 小于 S(Middle),因为是有序数列,则 X 必定落在Top 和 Middle-1的范围之内,下一步查找只需在此范围之内进行即可.即Top位置不动,Bottom变为 Middle-1.重复 1) 即可. 3) 如果 X 不小于 S(Middle),则 X 必定落在 Middle+1 和 Bottom之间,下一步查找范围应该是 Top=Middle+1 和 B

9、ottom,设定完Top後即可转到 1) 继续判断. 注意: 在此循环过程中,Top,Middle,Bottom都是表示位置的整数,如果循环到 Top=Middle 或者 Middle=Bottom,则表明此数列中没有我们要找的数.应该退出循环.,result = False初始化逻辑变量 Top = 1:bottom = N:middle=(top+bottom)/2 初始化指针 Do While (result = False and middlebottom) 构造循环 middle = (bottom +Top) / 2 初始化指针 If X = S(middle) Then判断 re

10、sult = True找到 Else If X S(middle) Then根据大小 Top = middle + 1确定下一步比较范围 Else bottom = middle - 1 End If End If Loop下一步通过分析result的真值来区分是否找到,折半查找的公式表示：,7.3 素数的判定和求法,素数的定义: 除了1与本身之外，不能被其他正整数整除的数，叫作素数，也叫质数。 按照习惯规定，1 不算素数，最小的素数是 2，其余的是 3、5、7、11、13、17、19等等。 7.3.1 由定义判断素数 对于数 M ,从I=2,3,4,5到 m-1 判断 m 能否被 I 整除,

11、如果全部不能整除,则 m 是素数,只要有一个能除尽,则 m 不是素数,为了压缩循环次数,可将判断范围从 2 - m-1 改为 2 - int(sqr(m),根据定义判断是否素数的公式表示,I=2:j=sqr(m)初始化 Do While(I0 I=I+1 Loop 根据退出的两种情况来判断是否素数 If Ij then 是素数 else 有整除情况 end ifVB例题点此进入,7.3.2 用筛选法求素数(用来找出指定范围的所有素数) 算法简介: 首先把 2 - m 内所有数放入筛中,然后找出筛中最小的素数,并将该数在范围之内的所有倍数的数去掉,依次进行,直到筛中的最小的素数已经超出 m 的范

12、围. 理解: 最小素数去掉所有倍数以后的数中近邻的数即是下次循环的最小素数. 退出的条件是:最小素数已经等于最大的数,即指定的查找范围.,筛选法的算法表示:,P=2:Flag=True 初始化最小素数和退出标志 Do Do while pm and Array(p)=0 找数组中最小素数 p=p+1 Loop if p=m then Flag=False判断是否退出 For i=p+p to m-1 step p置倍数的数为0 Array(p)=0 Next i p=p+1为下一次循环准备 Loop while Flag=True外层循环,上述循环完成以后,数组中所有不为 0 的元素即为 m

13、范围内的所有素数集合. 注意: 在查找素数之前要初始化一个大小至少为 m 数组来进行比较. 非素数标志可以把数值置为零或者其他标志 最小素数从 2 开始 VB例题点此进入,7.4 解一元方程,迭代法的基本思想 迭代算法是一种重要的逐次逼近的方法，是常用算法之一，其基本思想是将非线性方程 F(x)=0 逐步转化某种线性方程并求解，直到此线性方程和一元方程在根处的线性方程非常相似即可认为找到根。步骤如下： 1、将F(x)=0 转化为x=g(x)的形式 2、给出一个初值x0，由式子求出 x1= g(x0) 3、判断|x1-x0|是否成立，如不成立，将 x0 = x1 4、转去继续执行第2步 可见迭代

14、要利用上一次的迭代结果，所以必须初始化一个迭代初值。通常表现为 根 所在的近似位置。,7.4.1 牛顿迭代法的基本思想,其中，F(X)为F(X)的导数方程,因为迭代要利用上一次的迭代结果，所以必须初始化一个迭代初值。通常表现为 根 所在的近似位置。,牛顿迭代公式为： Xn+1=Xn - F(Xn)/F(Xn),牛顿迭代法解一元方程,三要素：迭代初值，元方程，导数方程 X0=a :X1=X0 （X1=a）初始化迭代初值 Do X0=X1为下一次迭代做准备 F (x)= F (x)= X1=X0-F(x)/F(x)计算下一次的迭代值 Loop While Abs(X1-X0)Precision直到

15、结果非常相近 X1 即为结果 其中 Precision为要求的精度.,VB例题点此进入,7.4.2 二分法解一元方程,二分法的基本思想： 任取两点 X1, X2，判断在（X1,X2）之间有无一个实根。其方法是：如果F(X1)*F(X2)=0，即F(X1)和F(X2)符号相反，说明（X1,X2）之间有一实根，取(X1,X2)的中点X,继续检查F(X),F(X1)的符号，如果异号，则实根在（X1,X）之间。这样，寻根的范围便减少了一半。继续用同样的办法缩小查找范围，直到区间相当小即可。 这个方法的前提是F(X)在（X1,X2）区间范围内是单调递增或者递减的，即F(X)在初始的X1,X2范围内是有实

16、根的，如果F(X1)和F(X2)同符号，则必须重新选择X1,X2直到F(X1)*F(X2)异号。 舍弃的办法是：如果F(X)与F(X2)同号，则用X作为新的X2,这就舍弃了(X,X2)区间。如果F(X)与F(X1)同号，则用X作为新的X1,这就舍弃了原来的(X1,X)区间。,二分法解一元方程的公式表示：,F1=F(X1):F2=F(X2) Do X=(X1+X2)/2:F=F(X) if (F*F1)=0 then X1=X:F1=F End if If (F*F1)Precision And FPrecision_of_F,在退出的两种条件之中，其中之一是X1和X2的范围足够小，另一个是F(

17、X)足够小。可以用退出的条件 FPrecision_of_F来判断。 VB例题点此进入,7.5 数值积分,数值积分法是用来求“不可求”或者“很难求”原函数的函数的积分的一种方法，是通过利用计算机快速的计算能力来组合积分值的一种方法。 其基本思想是： 对于函数F(X)，在区间a, b上的定积分，其几何意义是求F(X)曲线和直线x=a, y=0,x=b所谓成的曲边梯形的面积。如图：,a,b,F(X),为求出此面积，将区间a, b分成若干个小区间，每个区间的长度为( b-a )/n，那么定积分就是每个区间所围成的小曲边梯形的面积之和区间分得越小，则近似程度越高如图：,a,a+h,b,b-h,F(X)

18、,F(b),F(a),计算小曲边梯形的面积的方法常用的有矩形法，梯形法和辛普生法，其中以矩形法最为简便，即用小矩形来近似代替小曲边梯形其中的矩形面积可用底高来表示，其中底和分解的份数有关系，为（-）/，高为（+（-），累加所有的小矩形面积即为积分值 其他方法如梯形法和辛普生法类似,数值积分的基本公式表示（矩形法）,N=?积分等份，积分的精度 h=(b-a)/N底线宽度 s=0面积初始值 x=a初始位置 for i=1 to N s=s+h*f(x)面积累加 x=x+h递增小矩形 Next i VB例题点此进入,7.7 数制转换的基本编写方法,数值转换的一般编写方法是从数值转换的定义入手，常用的是十进制，二进制，八进制和十六进制之间的转换其中又以十进制，十六进制和二进制的转换最为重要 中数值转换的关键函数是（）函数，在其各种用法中（“”）作用是把代表十六进制数的对象转变为十进制数各种十六进制到其他进制的转换都以此为基础 例如十六进制到二进制的转换要按位经由十进制除二取余法进行 数