计算机算法复习题及答案(前三章)

计算机算法复习题及答案（前三章）第一章1、什么是绝对误差？什么是相对误差？答：绝对误差等于准确值与近似值差的绝对值。相对误差是近似数的误差与准确值的比值。2、什么是绝对误差限？什么是相对误差限？答：绝对误差限为绝对误差的“上界”相对误差限为相对误差绝对值的“上界”3、有效数字与绝对误差限有何关系？有效数字与相对误差限有何关系？答：（绝对）若近似值的绝对误差限是某一位上的半个单位，且该位直到的第一位非零数字一共有几位。则称近似值有n位有效数字。（相对）设近似值=±0.···×有n位有效数字，≠0,则真相对误差限为×设近似值=±0.···×的相对误差限为×，≠0,则它有n位有效数字。4、例1.11、例1.12、例1.15、例1.16.例1.11.设x=4.26972，那么取2位，=4.3,有效数字为2位取3位，=4.27,有效数字为3位取4位，=4.270,有效数字为4位取5位，=4.2697,有效数字为5位例1.12，若=3587.64是x的具有6位有效数字的近似值，则误差限是|-x|≤×=×若=0.0023156是x的具有5位有效数字的近似值，则误差限是|-x|≤×≤×例1.15，若=2.72来表示e的具有3位有效数字的近似值，则相对误差限是=×=×例1.16要使的近似值的相对误差限小于0.1%，要取几位有效数字？由定理1.1，≤×.由于=4.4···，已知=4,故只要取n=4，就有≤0.125×=0.1%只要对的近似值取4位有效数字，其相对误差限就小于0.1%。此时由开方表得≈4.4725、课本13~14页习题1、2、3、4.习题1：下列各数都是经过四舍五入得到的近似数，试指出它们是具有几位有效数字的近似数，并确定＋＋和的误差限答：=1.1021，5位，=0.031，2位，=385.6，4位|＋＋|-|＋＋|≤|-|＋|-|＋|-|＝×＋×＋×＝0.5055η()≈||η（）＋|η（）|＝1.1021××＋0.031××＝0.00055105＋0.00000155＝0.0005526η（）≈||η（）＋||η()＝0.001708255＋0.21308256＝0.2148习题2.已测得某场地长L的值为=110m，宽d的值为=80m,已知|L-|≤0.2m，|d-|≤0.1m，试求面积S=Ld的绝对误差限和相对误差限。解：绝对误差限：S=η(Ld)≈||η(d)＋||η(L)=110×0.1＋80×0.2=相对误差限：S=(Ld)≈d㏑L＋d㏑d＝＋＝0.001818＋0.00125＝0.31%习题3.若a=1.1062，b=0.947是经四舍五入后得到的近似值，问a+b,a×b有几位有效数字。解：a+b≈1.1062+0.947≈2.053有4位a×b≈1.1062×0.947≈1.05有3位习题4、设x=4.26972,求x的具有i位有效数字的近似值，其中i=2、3、4、5、。解：i=2,=4.3i=3,=4.27i=4,=4.270i=5,*4X=4.26926、判断下列哪个数精度高：x=1000±0.01、y=100±0.01解：*X=1000*y=100，x=0.01，y=0.01∵x=y∴*y与*X的误差限相等但是*yy=0.01%，*xx=0.001%∴X的精度高7、已知x1=3.141,(x1是的近似值〕且│-x1│≤1/2*10-5哪么x1有几位有效数字？解：∵|π-1x|≤21×510，m=||-6=-5∴1x有6位有效数字*1X*2X*3X第二章1.数据拟合与差值多项式有什么不同？答：数据拟合只要所构造的近似函数g（X)与被逼近函数f（X)在区间[a，b]上的偏差满足某种要求就行了。插值多项式所构造的函数y=f（x）的近似函数g（x）必须精确地通过由已知离散数据所确定的离散点。2.构造差值多项式应注意事项有几点？答：①已给出函数是否肯定②查找函数是否唯一③如何表达查找函数④误差估计3.曲线拟合的最小二乘法的基本思想答：基于准则（3）使残差的平方和为最小，即=min来选取拟合曲线的方法为曲线拟合的最小二乘法4、例2.1、例2.3、例2.8例2.1已知y=f（x）的函数求其近似值插值表达式解：将0x=1，0y=1，1x=3，1y=2代入式1P（x）=101xxxx0y+010xxxx1y,得1P（x）=313x×1+131x×2=21（x+1）∴f（x）≈21(x+1)例2.3已知lg2.71=0.4330，lg2.72=0.4346，lg=2.73=0.4362，求lg2.718；解：这里x0=2.71,x1=2.72,x2=2.73y0=0.4330,y1=0.4346,y2=0.4362代入式P2（x）=y0l0（x）+y1l1（x）+y2l2（x）(x-2.72)(x-2.73)P2(X)＝×0.4330(2.71-2.72)(2.71-2.73)(x-2.71)(x-2.73)＋×0.4346(2.72-2.71)(2.72-2.73)(x-2.71)(x-2.72)＋×0.4362(2.73-2.71)(2.73-2.72)＝13038x2－70926.08x＋96459.032P2（2.718）=0.48x13y12例2.8有一滑轮组，要举起W公斤的重物需要用F公斤的力，实验所得的数据如下表。W/kg20406080100F/kg4.357.5510.4013.8016.80求合适上述关系的近似公式。解：首先，将这些数据画在直角坐标系中，从图形上看，数据点的分布大致呈一条直线，所以所求的拟合直线为y=a+bx，则由公式NiiiNiNiiNiiNiiyxxbxayxbNai112111得关于a和b的线性方程组37972200030090.523005baba解得a=247200，b=6234000∴近似公式为y=247200+6234000x5、课本50页习题：1、2、3、13习题1.已知函数表如下，求X=3.8的函数值X34Y0.50.64解：将x0=3,x1=4,y0=0.5,y1=0.64代入公式得P1（x）==0.14x+0.08∴P1（3.8）=0.162习题2.已知函数表如下，求二次lagrange插值多项式P2（x）X314Y425解：(x-1)(x-4)(x-3)(x-4)(x-3)(x-1)P2(X)＝×4＋×2＋×5=(3-1)(3-4)(1-3)(1-4)(4-3)(4-1)＝X＋1习题3、已知函数表如下，试不用开方的办法而用抛物插值法计算的值X100121144Y101112解：(x-121)(x-144)(x-100)(x-144)(x-100)(x-121)P2(X)＝×10＋×11＋×12(100-121)(100-144)(121-100)(121-144)(144-100)(144-121)10x2-2650x+17424011x2-2684x+15840012x2-2652x+145200＝＋＋9244831012P2(115)≈10.7210100111yxxxxyxxxxXP0.643435.0434xx115习题13．已知函数表如下，求Newton插值多项式X01436Y0-78514解：X1Y1一阶二阶三阶四阶00-73−4323901-75-1154830353614Nn(x)=f(Xo)+f[Xo,X1](X-Xo)+f[Xo,X1,X2](X-Xo)(X-X1)+f[Xo,X1,X2,X3](X-Xo)(X-X1)(X-X2)+f[Xo,X1,X2,X3,X4](X-Xo)(X-X1)(X-X2)(X-X3)=2815X4−25915X3+40215X2−34615X6、已知列表函数值如下，构造牛顿二次插值公式。X314Y425解:XY一阶二阶Nn(X)=4+(X−3)=X+13410121457、由课本24页：公式2.11、2.12写出二阶、三阶Newton插值公式。二阶：Nn(X)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)三阶：Nn(X)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)+f[x0,x1,x2,x3](x−x0)(x−x1)(x−x2)第三章：1、复化求积法的基本思想是什么？答：为了改善求积公式的精度，把积分区间分成若干个小区间，在每个小区间上采用次数不高的插值多项式，构造出相应的低阶求积公式，然后再把他们加起来作为整个积分区间上的求积公式。2、求积公式的代数精度有什么作用？梯形公式的代数是多少？答:作用：衡量一个求积公式的精确程度梯形公式具有一次代数精度3、复化求积法与变步长求积的区别？答：复化求积法计算积分时，要事先给出一个合适的步长。而变步长求积是在步长逐次二分的过程中，反复利用复化求积公式进行计算，直到所求的积分值满足精度要求为止。4、用复化的辛浦生公式和复化的梯形公式计算下列列表函数的积分值。X-4-2024Y1/171/511/51/17解：复化辛浦生：h=4+44=2I=Sn=23×[117+117+4×(15+15)+2×1]=23×31685=632255≈2.4784复化梯形公式：I=Tn=22×[117+117+2×(15+1+15)]=217+145=24885≈2.91765、课本66页例3.3，88页习题6、8题例3.3用复化梯形公式,复化simpson公式和n=6的Newton-Cotes公式计算积分下表中给出了sinX在7个点上的值.-----------------------------------------------------------------------------------X0sinX0.000000.258820.500000.707110.866030.965931.00000-----------------------------------------------------------------------------------解:用复化梯形公式I≈Tn=[f(a)+2f()(k)+f(b)]取a=0,b=π/2,n=π/12,n=6,则I≈Tn=1/2×1/12×π[sin(0)+sin()+sin]≈099429用复化Simpson公式I≈Sn=[f(a)+f(b)+4f()+2f()]≈1.00003用n=6的Newton-Cotes公式I≈Xsin+Xsin+Xsin+Xsin+Xsin+Xsin+Xsin≈1.000003与精确值比较,复化梯形公式的误差为-0.0057,复化Simpson公式的误差为+0.00003,用牛的Newton-Cotes公式的误差为+0.000003习题6.用梯形公式,Simpson公式计算定积分dX解:梯形公式:dX≈(1-0)[+]=+=Simpson公式:dX≈×(1-0)×[+4×+]=习题8.用复化梯形公式和复化Simpson公式计算积分.(1)dX(取n=8)复化梯形公式=n==dX≈×[+2×[++++++]+]=0.8347复化Simpson公式:dX≈×[++4×(+++)+2×(++)]=0.8357(2)dX(取n=6)复化梯形公式:n==dX≈×[+2×(++++)+]=1.6355复化Sinpson公式:dX≈×[++4×(++)×2×(+)]=1.6360第一章：1、什么是绝对误差？什么是相对误差？准确值x与其近似值x*之差称为近似数x*的绝对误差相对误差：近似数的误差与准确值的比值2、什么是绝对误差限？什么是相对误差限？在数值计算中，记为e(x*)=x*-x，简记为。但一般来说，不能准确知道的大小，可以通过测量或计算|e(x*)|=|x*-x|≤估计其绝对值的上界，那么叫做近似数x*的绝对误差限，简称误差限相对误差限：绝对误差跟近似值的比值3、有效数字与绝对误错限有何关