《常用算法》PPT课件.ppt

《《常用算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《常用算法》PPT课件.ppt（37页珍藏版）》请在三一办公上搜索。

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

2、,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)）thent=S(i):S(i)=S(j):S(j)=t交换End ifNext jNext IVB例题点此进入,2：选择法排序,特点：比较後不立即互换元素，而是记

3、下其位置并在每一轮比较完毕后和（）互换首先，比较的元素不同，以降序为例，是当前元素与上次比较後的最大元素进行比较，因此，在进行比较之前，要有一个初始化最大元素的过程其次，确定完毕的元素的互换是在每一轮完成后进行的，而不是在比较後进行的再次，互换元素的不同，为（i）和（iMax）:举例原始数据：3，5，7，9，4 要求：降序,第一轮比较，初始化设最大元素下标为3579 iMax=1 iMax=23579 iMax=2 iMax=33579iMax=3 iMax=43579iMax=4 iMax=4S(1)S(iMax)的结果9573,如此下去，第二轮找到7，第三轮5，选择法的公式表示：,For

4、i=1 to N-1iMax=I初始化iMax,在每轮比较开始处for j=I+1 to Nif(S(j)OP S(iMax)then iMax=jnext 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-1for j=1 to N-i比较次数逐次减少if(S(j)OP S(j+1)thent=S(j):S(j)=S(j+1):S(j)=t立即互换end ifnext jnext i,7.2 常用的查找算法,7.2.1 顺序查找 顺序查找表现是把待

6、查找的数与数组中的数从头到尾逐一比较，用一变量 P 来表示当前比较的位置，初始为1，当待查找的数与数组中 P 位置的元素相等时即可结束,否则 P=P+1 继续比较，当 P 大于 数组的最大长度,也应该结束注意退出的两种情况，分别为找到和P大于数组的最大长度,用Do While进行顺序查找（为待查找的数）：,P=1初始化比较位置Do while xS(p)And pNp=p+1Loop退出的两种情况If x=S(p)then 找到，处理else没找到，处理end ifVB例题点此进入,用For Next进行顺序查找（为待查找的数）：,For p=1 To N If a(p)=x Then Exi

7、t For End If Next退出的两种情况 If p N Then 没找到，处理 Else 找到，处理 End IfVB例题点此进入,7.2.2 折半查找折半查找法是对有序数列进行查找的一种高效查找办法，其基本思想是逐步缩小查找范围，因为是有序数列，所以采取半分作为分割范围可使比较次数最少.比较过程:（设数列已做降序排序处理）设置三个指针,分别指向数组序列 S 的Top,Bottom和Middle,其中Middle=(Top+Bottom)/2,进行下列判断,1 3 4 6 8 10 12 15 18 20 25,X=15,1)若待查找的数 X 等于S(Middle),则已经找到,位置就

8、是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 和 Bottom,设定完Top後即可转到 1)继续判断.注意:在此循环过程中,Top,Middle,Bottom都是表示位置的整数,如果循环到 Top=Middle 或者 Middle=Bottom

9、,则表明此数列中没有我们要找的数.应该退出循环.,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判断result=True找到Else If X S(middle)Then根据大小 Top=middle+1确定下一步比较范围 Else bottom=middle-1 End IfEnd IfLoop下一步通过分析result的真值来区分是否找到,

10、折半查找的公式表示：,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 整除,如果全部不能整除,则 m 是素数,只要有一个能除尽,则 m 不是素数,为了压缩循环次数,可将判断范围从 2-m-1 改为 2-int(sqr(m),根据定义判断是否素数的公式表示,I=2:j=sqr(m)初始化Do While(I0I=I+1Loop根据退出的两种情况来判断是否素数

11、If Ij then 是素数else有整除情况end ifVB例题点此进入,7.3.2 用筛选法求素数(用来找出指定范围的所有素数)算法简介:首先把 2-m 内所有数放入筛中,然后找出筛中最小的素数,并将该数在范围之内的所有倍数的数去掉,依次进行,直到筛中的最小的素数已经超出 m 的范围.理解:最小素数去掉所有倍数以后的数中近邻的数即是下次循环的最小素数.退出的条件是:最小素数已经等于最大的数,即指定的查找范围.,筛选法的算法表示:,P=2:Flag=True 初始化最小素数和退出标志DoDo while pm and Array(p)=0 找数组中最小素数p=p+1Loopif p=m th

12、en Flag=False判断是否退出For i=p+p to m-1 step p置倍数的数为0Array(p)=0Next ip=p+1为下一次循环准备Loop while Flag=True外层循环,上述循环完成以后,数组中所有不为 0 的元素即为 m 范围内的所有素数集合.注意:在查找素数之前要初始化一个大小至少为 m 数组来进行比较.非素数标志可以把数值置为零或者其他标志最小素数从 2 开始VB例题点此进入,7.4 解一元方程,迭代法的基本思想 迭代算法是一种重要的逐次逼近的方法，是常用算法之一，其基本思想是将非线性方程 F(x)=0 逐步转化某种线性方程并求解，直到此线性方程和一元

13、方程在根处的线性方程非常相似即可认为找到根。步骤如下：1、将F(x)=0 转化为x=g(x)的形式 2、给出一个初值x0，由式子求出 x1=g(x0)3、判断|x1-x0|是否成立，如不成立，将 x0=x1 4、转去继续执行第2步 可见迭代要利用上一次的迭代结果，所以必须初始化一个迭代初值。通常表现为 根 所在的近似位置。,7.4.1 牛顿迭代法的基本思想,其中，F(X)为F(X)的导数方程,因为迭代要利用上一次的迭代结果，所以必须初始化一个迭代初值。通常表现为 根 所在的近似位置。,牛顿迭代公式为：Xn+1=Xn-F(Xn)/F(Xn),牛顿迭代法解一元方程,三要素：迭代初值，元方程，导数方

14、程X0=a:X1=X0（X1=a）初始化迭代初值DoX0=X1为下一次迭代做准备F(x)=F(x)=X1=X0-F(x)/F(x)计算下一次的迭代值Loop While Abs(X1-X0)Precision直到结果非常相近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

15、,X）之间。这样，寻根的范围便减少了一半。继续用同样的办法缩小查找范围，直到区间相当小即可。这个方法的前提是F(X)在（X1,X2）区间范围内是单调递增或者递减的，即F(X)在初始的X1,X2范围内是有实根的，如果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)DoX=(X1+X2)/2:F=F(X)if(F*F1)=

16、0 thenX1=X:F1=FEnd ifIf(F*F1)Precision And FPrecision_of_F,在退出的两种条件之中，其中之一是X1和X2的范围足够小，另一个是F(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

17、分成若干个小区间，每个区间的长度为(b-a)/n，那么定积分就是每个区间所围成的小曲边梯形的面积之和区间分得越小，则近似程度越高如图：,a,a+h,b,b-h,F(X),F(b),F(a),计算小曲边梯形的面积的方法常用的有矩形法，梯形法和辛普生法，其中以矩形法最为简便，即用小矩形来近似代替小曲边梯形其中的矩形面积可用底高来表示，其中底和分解的份数有关系，为（-）/，高为（+（-），累加所有的小矩形面积即为积分值其他方法如梯形法和辛普生法类似,数值积分的基本公式表示（矩形法）,N=?积分等份，积分的精度h=(b-a)/N底线宽度s=0面积初始值x=a初始位置for i=1 to Ns=s+h*

18、f(x)面积累加x=x+h递增小矩形Next iVB例题点此进入,7.7 数制转换的基本编写方法,数值转换的一般编写方法是从数值转换的定义入手，常用的是十进制，二进制，八进制和十六进制之间的转换其中又以十进制，十六进制和二进制的转换最为重要中数值转换的关键函数是（）函数，在其各种用法中（“”）作用是把代表十六进制数的对象转变为十进制数各种十六进制到其他进制的转换都以此为基础例如十六进制到二进制的转换要按位经由十进制除二取余法进行数值转换的注意点是转换之前要进行合法性检查VB例题点此进入,7.8 VB的其他应用,7.8.1 Rnd()函数的使用Rnd()函数用来生成一个随机的小数，和一个整数相乘以后就可以得到指定范围内的一个随机整数例子：随机星空VB例题点此进入,7.8.2 进度条的使用进度条的属性设置里面.value属性代表当前进度,只要设定.value即可控制进度条的进度显示.具体应用见例题VB例题点此进入7.8.3 Calendar对象的应用Calendar对象属性中.year可以得到当前选择的年,.Month得到月份.Day得到当前日.具体应用见例题VB例题点此进入,