C语言程序设计第5章(姜恒远著.ppt

第5章 常用数值计算算法及 其程序设计 1 主要内容 l5.1 素数判断 l5.2 最大公约数求解 l5.3 穷举法求满足条件的一组解 l5.4 级数近似计算 l5.5 一元非线性方程求根 l*5.6 定积分近似计算 2 5.1 素数判断 l素数 如果一个正整数n只能被1和n自身整除，则称n 为素数（prime）。1不是素数，2是素数。 例如：7是素数，8不是素数 3 5.1 素数判断 l5.1.1 最简单素数判断算法 l5.1.2 改进后的素数判断算法 4 5.1.1 最简单素数判断算法 l算法描述 若n2且n不能被2n-1范围内的任一个整数整 除，n就是素数；否则n不是素数；若发现n不 是素数，立即停止后续判断。 l程序实现 for (t=1,i=2;t for(t=1,i=2; t z=x; while(!(x%z=0 printf(“%d”,z); return 0; 程序实现 10 5.2.2 欧几里德算法 l算法描述 (1) 判断x除以y的余数r是否为0。若r为0则y是 x、y的最大公约数，继续做下步操作；否则 yx，ry重复做第(1)步。 (2) 输出（或返回）y 11 5.2.2 欧几里德算法 #include int main(void) long x=100000,y=100005, r; while(r=x%y)!=0) x=y; y=r; printf(“%ld”,y); return 0; 程序实现 12 5.3 穷举法求满足条件的一组解 例1：某人在纸上写了一个四位整数3a45（a代 表一个数字）。已知这个四位整数被3除后的 值是1115，请问这个四位整数是什么？ l算法描述 用a的所有可能取值（09）分别形成10个四 位整数3045、3145、3945 依次判断这10个四位整数中的每一个被3除后 的值是否1115，若是则输出。 13 5.3 穷举法求满足条件的一组解 #include int main(void) int a,b; for(a=0;a int main(void) int x,y,z; for(x=0;x #include int main(void) double s=1,a=1,x,eps,f; int n,m; printf(“input x and eps:”); scanf (“%lf%lf”, for(n=1;fabs(a)eps; n+) for(f=1,m=1;m #include int main(void) double s=1,a=1,x,eps; int n; printf(“input x and eps:”); scanf (“%lf%lf”, for(n=2;fabs(a)eps; n+) a=a*x/(n-1) ; s+=a; printf(“%f”,s); 程序实现 22 5.5 一元非线性方程求根 l5.5.1 牛顿迭代法 l5.5.2 二分法和弦截法 23 5.5.1 牛顿迭代法 l牛顿迭代公式 xn+1= xnf(xn)/f (xn) 求方程f(x)=0在x0附 近的一个近似实根。 24 5.5.1 牛顿迭代法 l(1) 用方程f(x)=0根的初始近似值x0带入牛顿迭 代公式求得x1，用x1带入牛顿迭代公式求得x2 如此重复可得到根的近似值序列x0,x1,x2,xn 。 l (2) 每求出一个新的近似值xn+1后均判断 |f(xn+1)| #include int main(void) double x,x1,eps=1e-6,f,f1; x=1.0; do x1=x; f=6-x1*(5-x1*(4-3*x1); f1=-5+x1*(8-9*x1); x=x1-f/f1; f=6-x*(5-x*(4-3*x); while(fabs(f)=eps printf(“x=%f”,x); 程序实现 26 5.5.2 二分法和弦截法 27 5.5.2 二分法和弦截法 l 找到x轴上的两个端点a和b使得方程f(x)=0 在a,b中只有一个根；判断a和b是否为方程 的近似根，若是立即结束计算； l 若a、b均不是近似根则计算a,b的中心点 c=(a+b)/2，判断c是否为方程的近似根，若是 则立即结束计算； l 若c不是近似根且ab则将a,b 区间调整到 a,c或c,b（即将a,b 的长度缩小一半）并 确保方程在调整后的a,b 中仍有一个实根 ； 重复第(3)步直到找到根为止。 二分法算法描述 28 5.5.2 二分法和弦截法 l计算方程-3x3+4x2-5x+6=0的一个近似实根 ，允许所求得的近似根在小数点后第6位上 有误差。 #include #include double f(double x) return 6-x*(5-x*(4-3*x); int main(void) double a,b,c,x,eps=1e-6; do printf(“No one root ”); scanf(“%lf%lf”, while(f(a)*f(b)0); 二分法程序实现 29 5.5.2 二分法和弦截法 if(fabs(f(a)eps double a=-3.14159/2,b=3.14159/2, h,s,x; scanf(“%ld”, h=(b-a)/n; s=(cos(a)+cos(b)/2; x=a; for(i=1;i #include int main(void) long n,i; double a=-