常用算法

常用算法--------------------------•排序算法--〉比较互换选择法冒泡法•查找算法--〉顺序查找折半查找•素数的求法--〉定义法筛选法•解一元方程--〉牛顿迭代法二分法•数值积分--〉矩形法梯形法辛普生法•数值转换--〉B-O-D-H7.1常用的排序算法1：比较互换法基本过程（以降序为例）：将第一个元素顺序与其后面的元素比较，比第一个大则进行交换，第一轮完毕后，最大的元素被挪到了第一个位置，第二轮从第二个元素开始重复上面的过程，结束后得到第二个最大的元素，如此下去经过N-1轮的比较，可将N个数排好:举例原始数据：1，2，3，5，4要求：降序第一轮比较：1235421354312545123451234第一轮结束，找到最大值5第二轮比较：51234521345312454123第二轮结束，找到第二最大值4第三轮结果：54312第四轮结果：54321公式表示：(N为排序的个数,OP为操作，降序为“”)for(i=1toN-1)‘外层循环N-1次for(j=i+1toN)‘内层依赖外层if（S(j)OPS(i)）thent=S(i):S(i)=S(j):S(j)=t‘交换EndifNextjNextI例题见7-1.vbp2：选择法排序特点：比较後不立即互换元素，而是记下其位置并在每一轮比较完毕后和Ｓ（ｉ）互换．首先，比较的元素不同，以降序为例，是当前元素与上次比较後的最大元素进行比较，因此，在进行比较之前，要有一个初始化最大元素的过程．其次，确定完毕的元素的互换是在每一轮完成后进行的，而不是在比较後进行的．再次，互换元素的不同，为Ｓ（i）和Ｓ（iMax）:举例原始数据：3，5，7，9，4要求：降序第一轮比较，初始化设最大元素下标为ｉＭａｘ＝１3579４iMax=1iMax=23579４iMax=2iMax=33579４iMax=3iMax=43579４iMax=4iMax=4S(1)S(iMax)的结果9573４如此下去，第二轮找到7，第三轮5，．．．．选择法的公式表示：Fori=1toN-1iMax=I‘初始化iMax,在每轮比较开始处forj=I+1toNif(S(j)OPS(iMax))theniMax=jnextj‘注意比较对象的转变t=S(i):S(i)=S(iMax):S(iMax)=t‘注意互换的时间NextI例题见7-2.vbp３：冒泡法排序如果按升序排序，则方法为：将相邻两个数比较，把小数对调到前边，如此进行一轮後，就会把最大的数互换到最后，再进行一次，则会把第二大数排在倒数第二的位置上，进行Ｎ－１次後，整个数列即可排好．在这种排序过程中，小数如果气泡一样逐层上伏，而大数逐个下沉，因此，被形象的喻为“冒泡”．特征：当数据的大小顺序与要求不符时（逆序），才进行互换操作．第一轮比较：9475249752479524759247529第一轮结束，最大值9沉到最底第二轮比较：47529475294572945279第二轮结束，次大值7沉到倒数第二冒泡法的公式表示：Fori=1toN-1forj=1toN-i‘比较次数逐次减少if(S(j)OPS(j+1))thent=S(j):S(j)=S(j+1):S(j)=t‘立即互换endifnextjnexti7.2常用的查找算法7.2.1顺序查找顺序查找表现是把待查找的数与数组中的数从头到尾逐一比较，用一变量P来表示当前比较的位置，初始为1，当待查找的数与数组中P位置的元素相等时即可结束,否则P=P+1继续比较，当P大于数组的最大长度,也应该结束．注意退出的两种情况，分别为找到和P大于数组的最大长度．用DoWhile进行顺序查找（ｘ为待查找的数）：P=1‘初始化比较位置DowhilexS(p)AndpNp=p+1Loop‘退出的两种情况Ifx=S(p)then‘找到，处理else‘没找到，处理endif例题见7-3.vbp用ForNext进行顺序查找（ｘ为待查找的数）：Forp=1ToNIfa(p)=xThenExitForEndIfNext‘退出的两种情况IfpNThen‘没找到，处理Else‘找到，处理EndIf7.2.2折半查找折半查找法是对有序数列进行查找的一种高效查找办法，其基本思想是逐步缩小查找范围，因为是有序数列，所以采取半分作为分割范围可使比较次数最少.比较过程:（设数列已做降序排序处理）设置三个指针,分别指向数组序列S的Top,Bottom和Middle,其中Middle=(Top+Bottom)/2,进行下列判断13468101215182025BottomTopMiddleX=151)若待查找的数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和Bottom,设定完Top後即可转到1)继续判断.注意:在此循环过程中,Top,Middle,Bottom都是表示位置的整数,如果循环到Top=Middle或者Middle=Bottom,则表明此数列中没有我们要找的数.应该退出循环.result=False‘初始化逻辑变量Top=1:bottom=N:middle=(top+bottom)/2‘初始化指针DoWhile(result=Falseandmiddlebottom)‘构造循环middle=(bottom+Top)/2‘初始化指针IfX=S(middle)Then‘判断result=True‘找到ElseIfXS(middle)Then‘根据大小Top=middle+1‘确定下一步比较范围Elsebottom=middle-1EndIfEndIfLoop‘下一步通过分析result的真值来区分是否找到例题见7-4.vbp折半查找的公式表示：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)‘初始化DoWhile(I=j)and(mModi)0I=I+1Loop‘根据退出的两种情况来判断是否素数IfIjthen‘是素数else‘有整除情况endif例题见7-5.vbp7.3.2用筛选法求素数(用来找出指定范围的所有素数)算法简介:首先把2-m内所有数放入筛中,然后找出筛中最小的素数,并将该数在范围之内的所有倍数的数去掉,依次进行,直到筛中的最小的素数已经超出m的范围.理解:最小素数去掉所有倍数以后的数中近邻的数即是下次循环的最小素数.退出的条件是:最小素数已经等于最大的数,即指定的查找范围.筛选法的算法表示:P=2:Flag=True‘初始化最小素数和退出标志DoDowhilepmandArray(p)=0‘找数组中最小素数p=p+1Loopifp=mthenFlag=False‘判断是否退出Fori=p+ptom-1stepp‘置倍数的数为0Array(p)=0Nextip=p+1‘为下一次循环准备LoopwhileFlag=True‘外层循环上述循环完成以后,数组中所有不为0的元素即为m范围内的所有素数集合.注意:在查找素数之前要初始化一个大小至少为m数组来进行比较.非素数标志可以把数值置为零或者其他标志最小素数从2开始例题见7-6.vbp7.4解一元方程7.4.1牛顿迭代法的基本思想迭代算法是一种重要的逐次逼近的方法，是常用算法之一，其基本思想是将非线性方程F(x)=0逐步转化某种线性方程并求解，直到此线性方程和一元方程在根处的线性方程非常相似即可认为找到根。牛顿迭代公式为：Xn+1=Xn*F(Xn)/F’(Xn)其中，F’(X)为F(X)的导数方程,因为迭代要利用上一次的迭代结果，所以必须初始化一个迭代初值。通常表现为根所在的近似位置。牛顿迭代法解一元方程三要素：迭代初值，元方程，导数方程X0=a:X1=X0（X1=a）‘初始化迭代初值DoX0=X1‘为下一次迭代做准备F(x)=‘F’(x)=‘X1=X0-F(x)/F’(x)‘计算下一次的迭代值LoopWhileAbs(X1-X0)Precision‘直到结果非常相近‘X1即为结果其中Precision为要求的精度.例题见7-8.vbp7.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范围内是有实根的，如果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)=0thenX1=X:F1=FEndifIf(F*F1)=0thenX2=X:F2=FEndifLoopwhileAbs(X1-X2)PrecisionAndFPrecision_of_F在退出的两种条件之中，其中之一是X1和X2的范围足够小，另一个是F(X)足够小。可以用退出的条件FPrecision_of_F来判断。例题见7-9.vbp7.5数值积分数值积分法用来求“不可求”或者“很难求”原函数的函数的积分的一种方法，是通过利用计算机快速的计算能力来组合积分值的一种方法。其基本思想是：对于函数F(X)，在区间[a,b]上的定积分，其几何意义是求F(X)曲线和直线x=a,y=0,x=b所谓成的曲边梯形的面积。如图：abF(X)为求出此面积，将区间[a,b]分成若干个小区间，每个区间的长度为(b-a)/n，那么定积分就是每个区间所围成的小曲边梯形的面积之和．区间分得越小，则近似程度越高．如图：aa+hbb-hF(X)F(b)F(a)计算小曲边梯形的面积的方法常用的有矩形法，梯形法和辛普生法，其中以矩形法最为简便，即用小矩形来近似代替小曲边梯形．其中的矩形面积可用底＊高来表示，其中底和分解的份数有关系，为（ｂ－ａ）／Ｎ，高为Ｆ（ａ＋（ｉ－１）ｈ），累加所有的小矩形面积即为积分值．其他方法如梯形法和辛普生法类似．数值积分的基本公式表示（矩形法）N=?‘积分等份，积分的精度h=(b-a)/N‘底线宽度s=0‘面积初始值x=a‘初始位置fori=1toNs=s+h*f(x)‘面积累加x=x+h‘递增小矩形Nexti例题见7-11.vbp7.7数制转换的基本编写方法数值转换的一般编写方法是从数值转换的定义入手，常用的是十进制，二进制，八进制和十六进制之间的转换．其中又以十进制，十六进制和二进制的转换最为重要．ＶＢ中数值转换的关键函数是Ｖａｌ（）函数，在其各种用法中Ｖａｌ（“＆ｈ”＆Ｓｔｒｉｎｇ）作用是把代表十六进制数的Ｓｔｒｉｎｇ对象转变为十进制数．各