2014-1算法(2.5h)

1.1 误差的来源例1.1.1 用差商ha f h a f a f )()()(-+≈'求x x f ln )(=在3=x 处导数的近似值.取1.0=h ，1000.0=h ，h =0.000 000 000 000 001和h =0.000 000 000 000 000 1分别用MATLAB 软件计算，取十五位数字计算.解 在MATLAB 工作窗口输入下面程序>>a=3;h=0.1;y=log(a+h)-log(a);yx=y/h运行后得yx = 0.32789822822991 将此程序中h 改为0.000 1，运行后得yx = 0.33332777790385后者比前者好.再取h = 0.000 000 000 000 001，运行后得yx = 0.44408920985006不如前者好.取h = 0.000 000 000 000 000 1，运行后得yx = 0算出的结果反而毫无价值.例1.1.2 分别求方程组b AX =在下列情况时的解，其中A ⎪⎪⎭⎫⎝⎛=011111.. （1）⎪⎪⎭⎫ ⎝⎛=22b ;（2）⎪⎪⎭⎫⎝⎛=0122.b . 解 （1） 首先将方程组b AX =化为同解方程b A X 1-=，然后在MATLAB 工作窗口输入程序>> b=[2,2]';A=[1,1;1,1.01]; X=A\b运行后输出当⎪⎪⎭⎫ ⎝⎛=22b 时，b AX =的解为⎪⎪⎭⎫⎝⎛=02X ；（2）同理可得，当⎪⎪⎭⎫ ⎝⎛=0122.b 时，b AX =的解为⎪⎪⎭⎫⎝⎛=11X .例1.1.3 计算e 的近似值. 解 泰勒级数e +++++++=!!4!3!21432 n x x x x x n x)(∞<<-∞x , 取1=x ，得e +++++++=!1!41!31!2111　　n . （1.2）这是一个无限过程，计算机无法求到精确值.只能在（1.2）取有限项时计算，再估计误差.如果取有限项!!!!)(　　n s n 1413121111++++++=作为e 的值必然会有误差，根据泰勒余项定理可知其截断误差为e !)1()1(　+=-n e s n θ)10(<<θ.如果取（1.2）的前九项，输入程序>> n =8;s=1;S =1; for k=1:ns=s*k;S=S+1/s, ends,S,R=3/(s*(n+1)) 或>>S1=1+1+1/2+1/(1*2*3)+1/(1*2*3*4)+1/(1*2*3*4*5)+1/(1*2*3*4*5*6)+1/(1*2*3*4*5*6*7)+1/(1*2*3*4*5*6*7*8),R1=3/(1*2*3*4*5*6*7*8*9)运行后结果S = R =2.71827876984127 8.267195767195768e-006 因为截断误差为e ),10(101968.267!93!)18()1(6-8<<⨯≈<+=-θθ　　e s 所以e 的近似值e ≈≈++++++++=!81!71!61!51!41!31!2111)1(8 s 2.718 28.1.2 误差和有效数字例1.2.1 取282.718作为e 的四舍五入近似值时，求其绝对误差和相对误差. 解 在MATLAB 工作窗口输入程序>>juewu=exp(1)-2.71828运行后输出结果为juewu = 1.828 459 045 505 326e-006例1.2.2 计算⎰π20sin x xd x 的近似值，并确定其绝对误差和相对误差.解 因为被积函数xxsin 的原函数不是初等函数，故用泰勒级数求之.++-+-=!!!!sin ９　７５　３８６x x x x x x 421 )(∞<<-∞x , （1.5） 这是一个无限过程，计算机无法求到精确值.可用（1.5）的前四项!!!７５　３６x x x -+-421代替被积函数xxsin ，得 ⎰π=20sin x x y d ⎰π≈20(x !!!142７５　３６x x x -+-)d x =!7)2(!5)2(!3)2(2753７５　３⋅π-⋅π+⋅π-π=y ˆ. 根据泰勒余项定理和交错级数收敛性的判别定理，得到绝对误差!99)2(ˆ9⋅<-=πyy R = WU ， 在MA TLAB 命令窗口输入计算程序如下：>>syms xf=1-x^2/(1*2*3)+x^4/(1*2*3*4*5)-x^6/(1*2*3*4*5*6*7)y=int(f,x,0,pi/2),y1=double(y)y11=pi/2-(pi/2)^3/(3*3*2)+(pi/2)^5/(5*5*4*3*2)-(pi/2)^7/(7*7*6*5*4*3*2)inf=int(sin(x)/x,x,0,pi/2) ,infd=double(inf) WU =(pi/2)^9/(9*9*8*7*6*5*4*3*2), R =infd-y11因为运行后输出结果为： =y 1.370 762 168 154 49，yˆ=1.370 744 664 189 38，=R 1.750 396 510 491 47e-005， WU = 1.782 679 830 970 664e-005410-<.所以，yˆ的绝对误差为=ε410-，故⎰π=20sin x xy d 7 1.370≈x .yˆ的相对误差为 =r ε71.37010ˆ4-=y ε<0.007 3%.1.3 误差估计的基本方法例1.3.4 设计三种算法求方程01522=-+x x 在)3,2(的一个正根*x 的近似值，并研究每种算法的误差传播情况.解 为解已知方程，我们可以设计如下三种算法，然后将计算结果与此方程的精确解5.2*=x 比较，观察误差的传播.算法1 将已知方程化为同解方程=x 2215x -.取初值20=x ，按迭代公式21215k k x x -=+依次计算 ,,,,21n x x x ，结果列入表1–3中.算法2 将已知方程化为同解方程1215+=x x .取初值20=x ，按迭代公式 12151+=+k k x x依次计算 ,,,,21n x x x ，结果列入表1–3中.算法3 将已知方程化为同解方程141522+-+-=x x x x x .取初值20=x ，按迭代公式为1415221+-+-=+k k kk k x x x x x 依次计算 ,,,,21n x x x ，结果列入表1–3中.我们为这三种算法的计算编写两套MATLAB 程序如下： （1）MATLAB 主程序function [k,juecha,xiangcha,xk]= liti112(x0,x1,limax) % 输入的量--x0是初值, limax 是迭代次数和精确值x; % 输出的量--每次迭代次数k 和迭代值xk,% --每次迭代的绝对误差juecha 和相对误差xiangcha ， x(1)=x0;for i=1:limaxx(i+1)=fl(x(i));%程序中调用的fl.m juecha = abs(x(i)-x1);xiangcha = juecha /( abs(x(i))+eps);xk=x(i);k=i-1;[(i-1),juecha,xiangcha,xk] end（2）MATLAB 调用函数程序及其计算结果①算法2的MATLAB 调用函数程序function y1=fl(x)y1=15/(2*x+1);② 将MATLAB 主程序和调用函数程序分别命名liti112.m 和fl.m ，分别保存为M 文件，然后在MATLAB 工作窗口输入命令>> [k,juecha,xiangcha,xk]= liti112(2,2.5,100) ③运行后输出计算结果列入表1–3和表 1-4中.④将算法2的MATLAB 调用函数程序的函数分别用y1=15-2*x^2和y1=x-(2*x^2+x-15)/(4*x+1)代替，得到算法1和算法3的调用函数程序，将其保存，运行后将三种算法的前8个迭代值821,,,x x x 列在一起（见表 1-3），进行比较.将三种算法的821,,,x x x 对应的绝对误差和相对误差的值列在一起（见表 1-4），进行比较.1.4 数值计算中应注意的问题例1.4.1 求数）181(71915-+⨯=-x 的近似值. 解 （1）直接用MATLAB 命令>> x=(7^15)*(sqrt(1+8^(-19))-1)运行后输出结果x = 0问题出现在两个相近的数1981-+与1相减时，计算机运行程序>>sqrt(1+8^(-19))-1运行后输出结果ans = 0由于计算机硬件只支持有限位机器数的运算，因此在计算中可能引入和传播舍入误差.因为有效数字的严重损失，导致输出18119-+-的结果为0，计算机不能再与数157继续进行真实的计算，所以，最后输出的结果与x 的精确值不符.（2）如果化为18187)181(71919151915++⨯=-+⨯=---x ，再用MATLAB 命令>> x=(7^15)*( (8^(-19))/(sqrt(1+8^(-19))+1))运行后输出结果x = 1.6471e-005 这是因为18119-+-化为18181919++--后，计算机运行程序>> x= (8^(-19))/(sqrt(1+8^(-19))+1)运行后的结果为x =3.4694e-018 由于有效数字的损失甚少，所以运算的结果-18103.4694⨯再与157继续计算，最后输出的结果与x 的精确值相差无几.例1.4.2 求数)13030ln(2--=y 的近似值. 解 （1）直接用MATLAB 程序>> x=30;x1= sqrt(x^2-1)运行后输出结果x1 = 29.9833 输入MATLAB 程序>> x=30; x1=29.9833;y=log(x-x1)运行后输出结果y = -4.0923（2）因为)13030ln(2--中的30=x 很大，如果采用倒数变换法111221-+=--=x x x x z ，即130301ln)13030ln(22-+=--)190030ln(-+-=.输入MATLAB 程序>> x=30;y=-log(x+sqrt(x^2-1))运行后输出结果y = -4.0941（3）输入MA TLAB 程序>> x=30; y=log(x-sqrt(x^2-1))运行后输出结果y = -4.0941 可见，（2）计算的近似值比（1）的误差小.参加计算的数，有时数量级相差很大.如果不注意采取相应的措施，在它们的加减法运算中，绝对值很小的那个数经常会被绝对值较大的那个数“吃掉”，不能发挥其作用，造成计算结果失真.例1.4.4 请在16位十进制数值精度计算机上利用软件MATLAB 计算下面的两个数0.30.1111111111111111*++=x 和0.30.11111111111111111*++=y将计算结果与准确值比较，解释计算结果.解 在MATLAB 工作窗口输入下面程序>> x=111111*********+0.1+0.3, y=1111111111111111+0.1+0.3运行后输出结果x = 1.111111*********e+014，y =1.111111*********e+015 从输出的结果可以看出，x *x =，而y *y ≠.为什么*y 仅仅比*x 多一位1，而y *y ≠呢？这是因为计算机进行运算时，首先要把参加运算的数写成绝对值小于1而“阶码”相同的数，这一过程称为数的“对阶”.在16位十进制数值精度计算机上利用软件MATLAB 计算这两个数，把运算的数*x 写成浮点规格化形式为，151515*103000**********.0001010000000000000.000100111111111111111.0⨯+⨯+⨯=x在16位十进制数值精度计算机上，三项的数都表示为小数点后面16位数字的数与1510之积，所以，计算机没有对数进行截断，而是按原来的三个数进行计算.因此，计算的结果x *x =.而161616*10030000000000000.00010010000000000000.000101111111111111111.0⨯+⨯+⨯=y三项的数都表示写成绝对值小于1而“阶码”都为1610的数以后，第一项的纯小数的小数点后面有16位数字.但是，后两项数的纯小数的小数点后面有17位数字，超过了16位十进制数值精度计算机的存储量，计算机对后两项的数都进行截断最后一位，即后两项的数都是16位机上的零，再进行计算，所以计算结果与实际不符.五、向量和矩阵的范数例1．5.1: 用matlab 求下列向量的2,1,5，,-∞∞范数。

C语言考前辅导1、求输入的整数中正数的个数及其平均值#include <stdio.h>main(){ int num=0;float sum=0,a;while ( scanf( "%f", &a) != EOF ){if(a<=0.0) continue;num++;sum+=a;}printf("%d plus integer's sum :%6.0f\n",num,sum);printf("Meanvalue:%6.2f\n",sum/num);}2、求1/a+1/aa+1/aaa+…的前5项之和。

(若a=3, 则是1/3+1/33+1/333+1/3333+1/33333之和)# define N 5main(){int a , k ; float t ,s ;scanf(“%d”, &a) ; s=1.0/a ; t=a ; for (k=2 ; k<=N ; k++){t=t*10 ; t=t+a ; s=s+1.0/t ; }printf(“1/a+1/aa+1/aaa+…=%f”,s); }如果改成求a+aa+aaa+aaaa+aaaaa如何编程三s=a;t=a;{t=10*t+aS=s+t} 3、打印100～200之间的所有素数#include "math.h"main(){int m,k,i,n=0;for(m=101;m<=200;m=m+2){if(n%10==0) printf("\n");k=sqrt(m);for(i=2;i<=k;i++)if(m%i==0)break;if(i>=k+1){printf("%d ",m);n++;}}}if(i>k)比较好理解4、求n的阶乘，1)递归#include <stdio.h>int fac(int n){ int f;if(n<0) printf("n<0,dataerror!");else if (n==0||n==1) f=1;else f=fac(n-1)*n;return(f);}main(){ int n, y;printf("Input a integer number:");scanf("%d",&n);y=fac(n);printf("%d! =%15d",n,y);}2)非递归main(){ float y;Int n;printf("Input a integer number:");scanf("%d",&n);y=fac(n);printf("%d! =%15f",n,y);}float fact(int n){ int i;double res = 1;for(i=1; i<=n; i++)res = res*i;return res;}5、读10个整数存入数组，找出其中最大值和最小值#include <stdio.h>#define SIZE 10main(){ int x[SIZE],i,max,min;printf("Enter 10 integers:\n");for(i=0;i<SIZE;i++){ printf("%d:",i+1);scanf("%d",&x[i]);}max=min=x[0];for(i=1;i<SIZE;i++){ if(max<x[i]) max=x[i];if(min>x[i]) min=x[i];}printf("Maximum valueis %d\n",max);printf("Minimum valueis %d\n",min);}6、冒泡排序算法分析#include <stdio.h>main(){ int a[11],i,j,t;printf("Input 10 numbers:\n");for(i=1;i<11;i++)scanf("%d",&a[i]);printf("\n");for(j=1;j<=9;j++)for(i=1;i<=10-j;i++)if(a[i]>a[i+1]){t=a[i]; a[i]=a[i+1]; a[i+1]=t;}printf("The sorted numbers:\n"); for(i=1;i<11;i++)printf("%d ",a[i]);}8.11写一函数用起泡法对输入的个字符按由小到大的顺序排列。

第3章处理机调度与死锁(处理机调度)-选择题1.时间片轮转调度算法是为了()A.多个用户能及时干预系统B.使系统变得高效C.优先级较高的进程得到及时响应D.需要CPU时间最少的进程最先做2.在单处理器多进程系统中,进程什么时候占用处理器及决定占用时间的长短是由()决定的A.进程相应的代码长度B.进程总共需要运行的时间C.进程特点和进程调度策略D.进程完成什么功能3.()有利于CPU繁忙型的作业,而不利于I/O繁忙型的作业。

A.时间片轮转调度算法B.先来先服务调度算法C.短作业(进程)优先算法D.优先权调度算法4.下面有关选择进程调度算法的准则中,不正确的是()A.尽快响应交互式用户的请求B.尽量提高处理器利用率C.尽可能提高系统吞吐量D.适当增长进程就绪队列的等待时间5.设有4个作业同时到达,每个作业的执行时间均为2h,它们在一台处理器上按单道式运行,则平均周转时间为()A.1hB.5hC.2.5hD.8h6.若每个作业只能建立一个进程,为了照顾短作业用户,应采用()；为了照顾紧急作业用户,应采用()；为了能实现人机交互,应采用()；而能使短作业、长作业和交互作业用户都满意,应采用()A.FCFS调度算法B.短作业优先调度算法C.时间片轮转调度算法D.多级反馈队列调度算法E.剥夺式优先级调度算法7.()优先级是在创建进程时确定的,确定之后在整个运行期间不再改变A.先来先服务B.动态C.短作业D.静态8.现在有三个同时到达的作业J1、J2和J3,它们的执行时间分别是T1、T2、T3且T1<T2<T3。

系统按单道方式运行且采用短作业优先调度算法,则平均周转时间是()A.T1+T2+T3B.(3T1+2T2+T3)/3C.(T1+T2+T3)/3D.(T1+2T2+3T3)/39.设有三个作业,其运行时间分别是2h、5h、3h,假定它们同时到达,并在同一台处理器上以单道方式运行,则平均周转时间最小的执行顺序是()A.J1,J2,J3B.J3,J2,J1C.J2,J1,J3D.J1,J3,J210. 【2013统考真题】某系统正在执行三个进程P1、P2和P3,各进程的计算(CPU时间和I/O 时间比例如下表所示进程计算时间I/O时间P1 90% 10%P2 50% 50%P3 15% 85%提高系统资源利用率,合理的进程优先级设置应为()A.P1>P2>P3B. P3>P2>P1C. P2>P1=P3D. P1>P2=P311.采用时间片轮转调度算法分配CPU时,当处于运行态的进程完一个时间片后,它的状态是()状态A.阻塞B.运行C.就绪D.消亡12.一个作业8:00到达系统,估计运行时间为1h。

习题 11. 执行下列指令，观察其运算结果, 理解其意义： (1) [1 2;3 4]+10-2i(2) [1 2; 3 4].*[0.1 0.2; 0.3 0.4] (3) [1 2; 3 4].\[20 10;9 2] (4) [1 2; 3 4].^2 (5) exp([1 2; 3 4]) (6)log([1 10 100]) (7)prod([1 2;3 4])(8)[a,b]=min([10 20;30 40]) (9)abs([1 2;3 4]-pi)(10) [1 2;3 4]>=[4,3;2 1](11)find([10 20;30 40]>=[40,30;20 10])(12) [a,b]=find([10 20;30 40]>=[40,30;20 10]) (提示：a 为行号，b 为列号) (13) all([1 2;3 4]>1) (14) any([1 2;3 4]>1) (15) linspace(3,4,5) (16) A=[1 2;3 4];A(:,2)2. 执行下列指令，观察其运算结果、变量类型和字节数，理解其意义： (1) clear; a=1,b=num2str(a),c=a>0, a= =b, a= =c, b= =c (2) clear; fun='abs(x)',x=-2,eval(fun),double(fun)3. 本金K 以每年n 次，每次p %的增值率(n 与p 的乘积为每年增值额的百分比)增加，当增加到rK 时所花费的时间为)01.01ln(ln p n rT +=(单位：年)用MA TLAB 表达式写出该公式并用下列数据计算：r =2, p =0.5, n =12.4．已知函数f (x )=x 4-2x 在(-2, 2)内有两个根。

取步长h =0.05, 通过计算函数值求得函数的最小值点和两个根的近似解。

价值工程0引言随着中国经济的迅速发展，建筑工程的规范标准体系日趋完善，国内建筑市场日趋饱和化，不少建筑企业将目光投向海外市场，并且紧跟国家一带一路的发展战略潮流，大量中资企业开拓并深耕于东南亚市场。

孟加拉国作为东南亚国家的典型代表，人口密度非常高，国家整体经济水平十分落后，人民生活水平较低，城市化与商业化发展缓慢。

因此孟加拉建筑市场具有起步性、活跃性、包容性与国际性等特征，这为大量的国际建筑设计企业带来机遇和挑战，因此，系统的研究孟加拉规范BNBC 成为国际建筑设计人才的重要任务。

BNBC （Bangladesh National Building Code ）规范是为孟加拉国境内所有建筑物的设计、建造、材料质量、使用和占用、选址和维护制定最低标准，以便在可实现的范围内保障生命、肢体、健康、财产和公共福利。

《建筑设计防火规范》（GB50016-2014，2018版）是国内为了预防和减少火灾，保护人身及财产安全而单独制定的一套规范。

1建筑分类1.1BNBC 建筑分类BNBC 根据每栋建筑或建筑的一部分的功能用途或用房特征，将建筑用房分为十大类型：A 住宅：A1（单户住宅）；A2（双户住宅）；A3（公寓）；A4（食宿公寓、宿舍或旅馆）；A5（酒店和住宿房屋）；B 教育：B1（高中及以下教育设施）；B2（高中以上教育及培训设施）；B3（学前设施）；C 机构：C1（儿童看护机构）；C2（健全成人监护机构）；C3（非健全或残疾成人监护机构）；C4（儿童精神机构）；C5（成人精神机构）；D 医疗：D1（普通医疗设施）；D2（紧急医疗设施）；E 办公：E1（办公室）；E2（研究和测试实验室）；E3（基本服务）；F 商贸：F1（小型商店和超市）；F2（大型商店和超市）；F3（加油站）；G 工业：G1（低危工业）；G2（中危工业）；H 储存：H1（低火险储藏室）；H2（中火险储藏室）；I 集会：I1（设有固定座椅的大型会场）；I2（设有固定座椅的小型会场）；I3（无固定座椅的大型会场）；I4（无固定座椅的小型会场）；I5（体育设施）；J 危险：J1（爆炸危险建筑）；J2（化学危险建筑）J3（生物危险建筑）J4（辐射危险建筑）；K 其他：K1（停车场）；K2（私人车库）；K3（修理厂）。

基于双二次插值的2.5维FCSEM有限元正演模拟柳建新;汤文武;童孝忠【摘要】首先给出2.5维频率域可控源电磁的有限元方程,并详细推导基于矩形剖分及双二次插值的有限元方程的刚度矩阵的求解过程;接着重点研究波数的选取并得到一组精度较高的波数选取方案;然后利用本文基于双二次插值的有限元算法对一个均匀半空间模型进行模拟计算,并将计算结果与解析解对比,验证本文算法的正确性;最后对2个二维地电模型进行有限元模拟,分别得到TE及TM模式下的视电阻率及相位等值线断面图,通过对比分析可知模拟结果均能在不同程度上反映出异常体,从而进一步说明本文算法能够对2.5维频率域可控源电磁进行有效地模拟.【期刊名称】《中南大学学报（自然科学版）》【年(卷),期】2014(045)002【总页数】9页(P474-482)【关键词】2.5维;频率域可控源电磁;有限元;双二次插值【作者】柳建新;汤文武;童孝忠【作者单位】中南大学地球科学与信息物理学院,湖南长沙,410083;有色资源与地质灾害探查湖南省重点实验室,湖南长沙,410083;中南大学地球科学与信息物理学院,湖南长沙,410083;有色资源与地质灾害探查湖南省重点实验室,湖南长沙,410083;中南大学地球科学与信息物理学院,湖南长沙,410083;有色资源与地质灾害探查湖南省重点实验室,湖南长沙,410083【正文语种】中文【中图分类】P6312.5 维数值模拟指的是源为三维的、正演模型为二维的地球物理数值模拟问题[1−3]。

众所周知，2.5维数值模拟问题有着重要的实用价值，这是因为将三维问题简化为2.5维模型后只需要对剖面而不是整个体积空间进行离散处理，这样就大大减小了矩阵的尺寸[4]。

2.5维频率域可控源电磁法(frequency domain controlled-source electromagnetic, FCSEM)的有限元正演模拟，国内外都进行了研究。

常用算法设计方法第1节计算机算法概述 (1)1.1算法的五个特性 (1)1.2算法设计的要求 (1)1.3算法效率的度量 (1)第2节各种常规算法 (2)2.1迭代法 (2)2.2穷举搜索法 (3)2.3递推法 (3)2.4递归法 (3)2.5分治法 (4)2.5.1 分治法思想 (4)2.5.2 分治法时间复杂度计算 (5)2.6动态规划法 (7)2.7回溯法 (8)2.8贪心法 (9)2.9分支限界法 (10)2.10概率算法 (10)2.11字符串的模式匹配 (11)第3节附录部分 (12)3.1使用递推法求N的阶乘程序代码 (12)第1节 计算机算法概述计算机算法是对特定问题求解步骤的描述，它是指令的有限序列。

为解决某问题的算法与为该问题编写的程序含义是相同的。

常用的表示算法的语言有：自然语言、流程图、盒图、程序设计语言和伪代码。

1.1 算法的五个特性1. 有限性：算法必须在执行有限条指令之后结束，每条指令执行的时间也必须是有限的。

2. 确定性：算法中每一条指令必须有确切的含义，读者和计算机在理解时不会产生二义性，并且在相同条件下，相同的输入只能得到相同的输出。

3. 可行性：算法能把问题真正的解决。

即不能是理论正确但无法在计算机上实现的算法。

4. 输入：一个算法有零个或多个输入。

1.2 算法设计的要求1. 正确性：算法应当满足具体问题的需求。

2. 可读性：算法应该能让人读懂，能被计算机运行。

3. 健壮性：算法应该具有容错处理能力，不容易被击垮。

4. 高效率与低存储量要求：效率指程序的执行时间（越短越好），算法要占用计算机一定的存储量（越小越好）。

1.3 算法效率的度量1. 时间复杂度根据不同的输入，将算法的时间复杂度分为三种情况：(1) 最佳情况：使算法执行时间最少的输入。

一般不进行算法在最佳情况下的时间复杂度分析。

(2) 最坏情况：使算法执行时间最多的输入。

一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，而且对于某些算法来说，最坏情况是相当频繁的。