《常用算法》PPT课件.ppt

1,第八章 常用算法的程序 设计举例,2,本 章 要 点,数值积分: 矩阵法 梯型法 辛普生法 解一元方程(近似求解) 迭代法 牛顿迭代法 二分法 弦截法 求函数的最大值以及打印图案与仿真,3,概要,通过前面的学习我们初步具备了编写简单程序的能力. 我们知道: 程序=数据结构+算法 本章我们继续学习常用算法基础 要求: 切实掌握基本算法的设计方法和技巧,并能在此基础上举一反三,也就是掌握各类算法的原理和基本规律.,4,8.1 数值积分,求一个函数F(x)在a, b上的定积分: 其几何意义就是求曲线F(x)与直线X=A,Y=0,X=B所围成的曲边梯形面积.,a,A+h,A+(i-1)h,A+(i)h,5,8.1 数值积分,为了求出近似面积,可将a, b区间分成若干个小区间,每个区间的宽度为(b-a)/n , n为区间个数. 首先求出每个小曲边梯形面积的近似值, 然后将n个小曲边梯形面积相加起来就是总面积的近似值. N值愈大, 近似程度就愈高.,6,8.1 数值积分,求近似小曲边梯形面积的方法有如下三种: 用小矩形代替小曲边梯形,求出单个小矩形的面积,然后累加之; 用小梯形代替小曲边梯形; 在小区间范围内,用一个抛物线来代替该区间的F(x),然后求出由该抛物线与x=a+(i-1)h, y=0, x=a+ih 围成的小曲边梯形面积.,7,8.1 数值积分,8.1.1 矩形法 先求出第一个小矩形的面积: 底为: (b-a)/n , 高为: f(a) 或 f(a+h) 第i 个小矩形的面积: Si=hf(a+(i-1)h),8,8.1.1 矩形法程序设计举例,Exa8_1.FOR,9,输入 a, b ,n,X=a (第一个矩形的底的起点),H=(b-a)/n (求出底长),F0=f(x) (第一个矩形的高,即:x=a),S=0 (总面积),Si=f0*h (第i个矩形面积),S=s+si,X=x+h (下一个矩形的底的起点),F0=f(x) (下一个矩形的高),打印面积S,Do i=1,n,用矩形求 积分的基 本方法。,10,READ(*,*) A, B, N X=A H=(B-A)/N F0=EXP(X) S=0.0 DO 10,I=1,N SI=F0*H S=S+SI X=X+H F0=EXP(X) 10 CONTINUE WRITE(*,100) A,B,N WRITE(*,200) S 100 FORMAT(1X,A=,F10.3,3X,B=,F10.3,3X,N=,I4) 200 FORMAT(1x, S=,F15.8) END,第一个小矩形的底长,第一个小矩形的高,单个小矩形的面积,11,12,8.1 数值积分,8.1.2 梯形法(用小梯形代替小矩形) 先求出第一个小梯形的面积: 上底为: f(a) ,下底为: f(a+h) , 高: h 第i 个小梯形的面积: Si=h(f(a+ih)+f(a+(i-1) h)/2,13,READ(*,*) A,B,N X=A H=(B-A)/N S=0.0 DO 10,I=1,N SI=(SIN(I-1)*H)+SIN(I*H)*H/2.0 S=S+SI 10 CONTINUE WRITE(*,100) A, B, N WRITE(*,200) S 100 FORMAT(1X,A=,F10.3,3X,B=,F10.3,3X,N=,I4) 200 FORMAT(1X,S=,F15.8) END,Si=(EXP(I-1)*H)+EXP(I*H)*H/2.0,14,15,READ(*,*) A,B,N H=(B-A)/N S=0.0 F1=SIN(A) DO 10,I=1,N F2=SIN(A+I*H) SI=(F1+F2)*H/2.0 S=S+SI F1=F2 10 CONTINUE WRITE(*,100) A, B, N WRITE(*,200) S 100 FORMAT(1X,A=,F10.3,3X,B=,F10.3,3X,N=,I4) 200 FORMAT(1X,S=,F15.8) END,实际上第一个梯形的下底就是下一个梯形的上底,16,17,8.1 数值积分,8.1.2 梯形法 我们也可以用n个小梯形面积的代数和公式, 就是设f0、f1、f2、f3fn 分别是x等于x0、 x1、x2、x3xn时函数F(X)的值。,18,8.1 数值积分,8.1.2 梯形法,19,READ(*,*) A,B,N F0=SIN(A) H=(B-A)/N S=F0 D0 10, I=1,N F=SIN(A+I*H) S=S+2.0*F 10 CONTINUE S=(S-SIN(B)*H/2.0 WRITE(*,*) A, B, N WRITE(*,200) S 100 FORMAT(1X,A=,F10.3,3X,B=,F10.3,3X,N=,I4) 200 FORMAT(1X,S=,F15.8) END,利用n个小梯形面积的代数和公式求积分,20,21,8.1 数值积分,8.1.3 辛普生法(Sinpson) 基本思想： 在一个小区间内用一抛物线f1(x)代替原来的曲线f(x) 抛物线f1(x)的确定：取a, b中点c,其坐标为(b+a)/2, 0) 通过c点可求出F(c).也就是通过f(a)f(b)f(c)三点作出唯一一条抛物线f1(x)。可以证明f1(x)等于：,22,由上面的公式可以看出: X=a时, f1(a)=f(a); X=b时,f1(b)=f(b); X=c时,f1(c)=f(c). 因此在区间a, b的定积分（1）可由（2）代替 根据抛物线定积分求值公式(已知抛物线上三点)：,（1）,（2）,23,8.1 数值积分,8.1.3 辛普生法(Sinpson) 我们可以再进一步将区间a, c取中点，再做抛物线。根据精度的需要可以做n次。最后得到公式为：,24,辛普生法举例,Exa8_3.For,25,READ(*,*) A, B, N H=(B-A)/(2.0*N) S=0.0 FA=1.0/(1.0+A) FB=1.0/(1.0+B) X=A+H F2=0.0 F4=1.0/(1.0+X) DO 10,I=1,N-1 X=X+H F2=F2+1.0/(1.0+X) X=X+H F4=F4+1.0/(1.0+X) 10 CONTINUE S=H/3.0*(FA+FB+4.0*F4+2.0*F2) WRITE(*,100) A, B, N WRITE(*,200) S 100 FORMAT(1X,A=,F8.2,3X,B=,F8.2,3X,N=,I4) 200 FORMAT(1X,S=,F16.7) END,26,27,8.1 数值积分,三种求定积分的比较： 矩形法较大； 梯形法居中； 辛普生法最好。,在n值相同的情况下 近似值的比较,NEXT,28,8.2 解一元方程,下面我们要学习的是用几种不同的方法求一元方程的根,且都是用近似法求根.通过逐步逼近(多次迭代)获得需要的精度.我们知道:只有少数方程是可以通过解析方法来求出准确的根值,一般的情况下,用解析方法是难做到的.因此在计算机中常采用如下四种方法来求解一元方程: 1)迭代法; 2)牛顿迭代法; 3)二分法; 4)弦截法.,这是常用的四种方法，事实上还有许多其它的方法。,29,8.2 解一元方程,8.2.1 迭代法 迭代算法是一种重要的逐次逼近的方法，是常用算法之一，其基本思想是将非线性方程 F(x)=0 逐步转化某种线性方程并求解，直到此线性方程和一元方程在根处的线性方程非常相似即可认为找到根.,30,8.2 解一元方程,8.2.1 迭代法 用迭代法求一元方程的根的基本方法如下： 将F(X)改写成求X的式子：即X=G(X)的形式； 估计根的范围，给出X的初值X0, 代入上式的右边，求出X的第一次近似值X1(注意收敛的问题) 再将 X1代入X=G(X)中，求出X2.即： 直到|Xn+1-Xn|,31,1)首先选择输入一个近似根，如X0=3 计算出X1 2)将代入方程算出x2, 3)判断Xn-1与Xn的绝对值之差,32,8.2 解一元方程,8.2.1 迭代法 说明: 用迭代法求一元方程F(X)中,对于 X=G(X) ,对同一方程我们能得到不同的 G(X)形式. 而且有的G(X)是收敛的,有的 不收敛.即使是同一个G(X), 有的X0是收 敛的,有的X0不是收敛的.一般来说: 只要G(X)的一阶导数连续: 则X=G(X)对任意X0是收敛的.,33,迭代法举例,Exa8_4.For,34,READ(*,*) X, M DO 10,I=1, M X1=(-X*3-2.0*X*X-2.0)/2.0 WRITE(*,100) I, X1 IF(ABS(X-X1).GT.1E-6) THEN X=X1 ELSE STOP ENDIF 10 CONTINUE WRITE(*,200) M 100 FORMAT(1X,I=,I3, 5X,X1=, F15.7) 200 FORMAT(1X, I4) END,X3+2x2+2x+2=0 x=(-x3-2x2-2)/2 估计在0附近有一个根，设x0=0,M控制次数,35,36,8.2 解一元方程,8.2.2 牛顿迭代法 用牛顿迭代法求F(x)=0在X0附近的一个实根的方法是: 选一个接近于X的真实根的近似根X1 通过X1求出F(X1)。就是当X=X1时，交f(x)于f (x1) 过f(x1)作f(x)的切线，交X轴于X2,可以用公式求X2 通过X2求出F(X2); 再通过f(X2) 作F(X)的切线交X轴于X3; 再通过X3求出F(X3) ，。直到接近真实的根，也就是两次求出根的差为：|Xn+1-Xn|,图,37,一阶导数:,38,用牛顿迭代法求:x3-2x2+4x+1=0在x=0附近的一个实根,1)先求出一阶导数: F(x)=3x2-4x+4 2)编写程序: READ(*,*) x n=1 10 x1=x F=x1*3-2.0*x1*2+4.0*x1+1.0 F1=3.0*x1*2-4.0*x1+4.0 x=x1-F/F1 write(*,100) n, x1, x n=n+1 if(abs(x-x1).gt.1e-6) goto 10 100 format(1x,n=,I3,3x,x1=,F15.7,3x,x=,F15.7) end,初始值,输入迭代次数,一阶导数,使用直到循环,39,40,用牛顿迭代法求:x3-2x2+4x+1=0在x=0附近的一个实根,1)先求出一阶导数: F(x)=3x2-4x+4 2)编写程序: READ(*,*) x n=1 do 10,while(N.eq.1).OR.(ABS(X-X1).GT.1e-6) x1=x F=x1*3-2.0*x1*2+4.0*x1+1.0 F1=3.0*x1*2-4.0*x1+4.0 x=x1-F/F1 write(*,100) n, x1, x n=n+1 10 continue 100 format(1x, n=,I3,3x, x1=,F15.7,3x, x=,F15.7) End,使用当型循环,NEXT,41,42,8.2 解一元方程,8.2.3 二分法 这个方法的前提是F(X)在（X1,X2）区间范围内是单调递增或者递减的，即F(X)在初始的X1,X2范围内是有实根的. 在X轴上取两点X1和X2, 判断该区间有无一个实根如果F(X1)和F(X2)符号相反,说明区间(X1, X2)有一个实根.再取该区间的中点X, 判断F(X)和F(X1)是否同号; 如果符号相反, 则区间(X , X1)内有实根.用这种办法不断缩小范围,最后接近真根,图,43,8.2.3 二分法 如果F(X)与F(X1)不同符号,则用X作为新的X2, 这样就去掉了一半区间(X , X2). 如果F(X)与F(X1)同号,则用X作为新的X1,这样就去掉了一半区间(X1, X). 再根据新的X1、X2来找中点X. 重复以上过程。,8.2 解一元方程,44,READ(*,*) X1,X2 F1=X1*3-6.0*X1-1.0 F2=X2*3-6.0*X2-1.0 10 X=(X1+X2)/2.0 F=X*3-6.0*X-1.0 IF(SIGN(F,F1).EQ.F) THEN X1=X F1=F ELSE X2=X F2=F ENDIF IF(ABS(X1-X2).GT.1E-5).AND.(ABS(F).GT.1E-6) GOTO 10 IF(ABS(F).GT.1E-6) X=(X1+X2)/2.0 WRITE(*,100) X 100 FORMAT(1X,X=,F15.7) END,F与F1是否同号,取x1=0,x2=5,图,X点是x1与x2的中点,45,46,8.2 解一元方程,8.2.4 弦截法 弦截法与二分法有些相似。它是取F(x1)与F(x2)的连线与X轴的交点X，从两个区间（X1, X）与(X, X2)中舍去一个。取舍的方法与二分法相同。求X点的方法是：,图,弦线与X轴 的交点,47,10 READ(*,*) X1,X2 F1=X1*3-2.0*X1*2+7.0*X1+4.0 F2=X2*3-2.0*X2*2+7.0*X2+4.0 IF(SIGN(F1,F2).EQ.F1) GOTO 10 F=1.0 20 IF(ABS(X1-X2).GT.1E-5).AND.(ABS(F).GT.1E-6) THEN X=X2-(X2-X1)/(F2-F1)*F2 F=X*3-2.0*X*2+7.0*X+4.0 IF(SIGN(F,F1).EQ.F) THEN X1=X F1=F ELSE X2=X F2=F ENDIF GOTO 20 ENDIF IF(ABS(F).GT.1E-6) X=(X1+X2)/2.0 WRITE(*,100) X 100 FORMAT(1X,X=,F15.7) END,先假设F=1.0,为了开始的IF条件,X3-2x2+7x+4=0 要求进行到前后二次求出的x的值之差不超过10-6,X点是按公式求出的交于X轴的点,F是交x轴点的函数值,48,49,8.3 求函数的最小值,求函数的最小值是在给定的区间上用近似的方法逐步找出其最小值。 常采用的方法是： FIBONACCI搜索法（黄金值搜索法或0.618法）,low,high,F(x),F(x1),x1,x2,F(x2),Y,X,先假设在High与Low之间有最小值.,50,8.3 求函数的最小值,FIBONACCI搜索法： 选两点High和点Low,设该区间有一函数的最小值。 在该区间选择: (1)X1与Low的距离为： X1=low+0.618(High-Low) (2)X2与High的距离为： X2=high-0.618(High-Low) 计算函数值：F(X1)和F(X2),如果： F(X1)F(X2),则最小值在（Low,X1）中，舍弃区间（X1,High）; 可以证明:X2正好在（Low,X1）的0.618处.这样就可以将X1High X2X1 再确定另一个X2 如果F(X2)F(X1),则最小值在（X2,High）中，舍弃区间（X2,low）。可以将X2low X1X2 再确定另一个X1,51,Exa8_8.For (运行举例),用黄金分割法求: F(x)=x2-4x+5的最小值,52,读入:LOW和HIGH,求X1=low+0.618(high-low) x2=high-0.618(high-low),求F1=F(x1) F2=F(x2),打印F1 F2 x1 x2,F1F2 ?,T,T,F,High=x1 X1=x2 X2=high-0.618(high-low),low=x2 X2=x1 X1=low+0.618(high-low),求F1=F(x1) F2=F(x2),F1F2 ?,T,F,F=F2 X=X2,F=F1 X=X1,打印 F,当High-low10-4,53,REAL LOW,HIGH,X1,X2 READ(*,*) LOW,HIGH WRITE(*,200) X1=LOW+0.618*(HIGH-LOW) X2=HIGH-0.618*(HIGH-LOW) 10 IF(HIGH-LOW).GT.1E-4) THEN F1=X1*X1-4.0*X1+5.0 F2=X2*X2-4.0*X2+5.0 WRITE(*,202) X1,F1,X2,F2 IF(F1.GT.F2) THEN HIGH=X1 X1=X2 X2=HIGH-0.618*(HIGH-LOW) ELSE LOW=X2 X2=X1 X1=LOW+0.618*(HIGH-LOW) ENDIF GOTO 10 ENDIF F1=X1*X1-4.0*X1+5.0 F2=X2*X2-4.0*X2+5.0 IF(F1.GT.F2) THEN F=F2 X=X2 ELSE F=F1 X=X1 ENDIF WRITE(*,204) X,F 200 FORMAT(12X,X1,14X,F1,13X,X2,13X,F2/) 202 FORMAT(1X,4F15.7) 204 FORMAT(0,X=,F10.6,5X,F(X)=,F10.7) END,根据X1 X2算出两点的（Y）值,X2 - 4x+ 5=0,先选定High Low,根据方程算出X1 X2,根据Y1 Y2确定最小值的位置,根据最小值的位