常用算法的程序设计举例.ppt

第八章第八章 常用算法的程序设计举例常用算法的程序设计举例 第一章第一章 算法算法 第二章第二章 计算机和计算机程序计算机和计算机程序 第四章第四章 逻辑运算和选择结构逻辑运算和选择结构 第五章第五章 循环结构的实现循环结构的实现 第六章第六章 FortranFortran的数据结构的数据结构 第七章第七章 数据的输入、输出数据的输入、输出 第三章第三章 FortranFortran语言程序设计初步语言程序设计初步 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 1 一、数值积分 几何意义： Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 2 近似求小曲边梯形面积的方法： （1）用小矩形代替小曲边梯形； （2）用小梯形代替小曲边梯形； （3）在小区间范围内，用一条抛物线代替该区间内的f(x)。Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 3 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) 10continue write(*,100) a,b,n write(*,200) s 100format(1x,a=,f10.3,3x,b=, $ f10.3,3x,n=,i4) 200format(1x,s=,f15.8) end 1. 矩形法 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 4 read(*,*) a,b,n x=a h=(b-a)/n s=0.0 do 10 i=1,n si=(sin(x+(i-1)*h)+ $ sin(x+i*h)*h/2.0 s=s+si 10continue write(*,100) a,b,n write(*,200) s 100format(1x,a=,f10.3,3x, $ b=,f10.3,3x,n=,i4) 200format(1x,s=,f15.8) end 2. 梯形法 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 5 其他几种 程序变形 . . . f1=sin(a) . . . do 10 i=1,n f2=sin(a+i*h) si=(f1+f2)*h/2.0 s=s+si f1=f2 10continue . . . . . . x2=a . . . do 10 i=1,n x1=x2 x2=x2+h si=(sin(x1)+ $ sin(x2)*h/2.0 s=s+si 10continue . . . . . . f0=sin(a) h=(b-a)/n s=f0 do 10 i=1,n f=sin(a+i*h) s=s+2.0*f 10continue s=(s-sin(b)*h/2.0 . . . Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 6 3. Sinpson法 取a，b中点c(a+b)/2，0)，通过 f(a)，f(b)，f(c)三点可作唯一一条抛物 线f1(x)。 根据抛物线定积分求值公式，有： 如果将(a，b)分成两个小区间(a，c) 和(c，b): Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 7 如果将(a，b)分成四个小区间: 如果将(a，b)分成n个小区间: Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 8 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) 10continue s=h/3.0*(fa+fb+4.0*f4+2.0*f2) write(*,100) a,b,n write(*,150) s 100format(1x,a=,f8.2,2x,b=,f8.2, $ 2x,n=,i4) 150format(1x,s=,f16.7) end 三种求定积分的方法中，矩形法的误差较大 ，梯形法次之，辛普生法最好。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 9 二、解一元方程（解非线性函数） 1. 直接迭代法 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 end if 10continue write(*,200) m 100format(1x,i=,i3,5x,x1=,f15.7) 200format(1x,computation has not, $ converged after,i4,iteration) end 因有收敛问题，要 设最大循环次数。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 10 有的g(x)是收敛的，而有的g(x)是不收敛的。 同一个g(x)，对某些x0是收敛的，对有的x0则是不 收敛的。 如果g(x)具有一阶导数连续，且对于所有的x ，若|g(x)|q1（q为一个定数），那么x=g(x)对于 任意的x0均收敛，且q愈小，收敛速度愈快。如果 不满足对所有的x存在|g(x)|q1 ，则可能对有的 x0收敛，对有的x0不收敛。 因此要恰当的选择g(x)形式和初值x0。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 11 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 100format(1x,n=,i3,3x,x1=,f15.7, $ 3x,x=,f15.7) end Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 12 3. 二分法 5read(*,*) x1,x2 f1=x1*3-6.0*x1-1.0 f2=x2*3-6.0*x2-1.0 if(sign(f1,f2).eq.f1) goto 5 10x=(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 end if 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 100format(1x,x=,f15.7) end Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 13 4. 弦截法（割线法） 5read(*,*) 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 5 f=1.0 20if(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 end if goto 20 end if if(abs(f).gt.1e-6) x=(x1+x2)/2.0 write(*,100) x 100format(1x,x=,f15.7) end Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 14 以上方法都是近似求根，得到不是准确值而是近 似值。但只要给定的误差足够小，就可以认为它们之 间足够近似。 事实上，只有少数的方程才能用解析的方法求出 准确的根值。 计算机可以解任何有实根的一元方程，它采用的 基本方法就是迭代，经过多次迭代，使近似根逐渐趋 近于真实根。迭代可以用循环实现，正好充分发挥计 算机快速运算的特点。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 15 三、求函数极值 Fibonacci搜索算法，或0.618法，或黄金值搜索法。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 16 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 end if write(*,204) x,f 200format(12x,x1,14x,f1, $ 13x,x2,13x,f2/) 202format(1x,4f15.7) 204format(0,x=,f10.6,5x, $ f(x)=,f10.7) end real low,high,x1,x2 read(*,*) low,high write(*,200) x1=low+0.618*(high-low) x2=high-0.618*(high-low) 10if(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) end if goto 10 end if Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 17 五、计算机模拟 计算机模拟（Computer Simulation）,又称“ 仿真”：用计算机模仿实物系统进行测试，从测试 的结果获得期望的资料。 根据模拟对象的不同特点，可分为： 确定性模拟（Deterministic Mode）； 随机性模拟（Stochastic Mode） 。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 18 小球以10m/s沿 45斜抛，落地反 弹方向同前，速度 减小10%，求前三 次周期轨迹。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile .Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd. 19 if(abs(y).gt.0.001) then t=t-dt dt=0.1*dt t=t+dt x=v*t+x0 y=v*t-0.5*g*t*2 else write(*,100) t,x,y flag=.false. end if end if got