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

《C语言程序设计第5章(姜恒远著.ppt》由会员分享，可在线阅读，更多相关《C语言程序设计第5章(姜恒远著.ppt（37页珍藏版）》请在三一办公上搜索。

1、第5章 常用数值计算算法及其程序设计,主要内容,5.1 素数判断5.2 最大公约数求解5.3 穷举法求满足条件的一组解5.4 级数近似计算 5.5 一元非线性方程求根*5.6 定积分近似计算,5.1 素数判断,素数 如果一个正整数n只能被1和n自身整除，则称n为素数（prime）。1不是素数，2是素数。例如：7是素数，8不是素数,5.1 素数判断,5.1.1 最简单素数判断算法5.1.2 改进后的素数判断算法,5.1.1 最简单素数判断算法,算法描述 若n2且n不能被2n-1范围内的任一个整数整除，n就是素数；否则n不是素数；若发现n不是素数，立即停止后续判断。程序实现 for(t=1,i=2

2、;t,5.1.2 改进后的素数判断算法,算法描述 如果n2且n不能被2sqrt(n)之间的所有整数整除，n就是素数。程序实现 r=sqrt(n);for(t=1,i=2;t,5.2 最大公约数求解,最大公约数 能同时被x和y整除的最大整数是整数x和y的最大公约数（GCD）。例如：30和45的公约数有3、5、15，其中15是30和45的最大公约数。,5.2 最大公约数求解,5.2.1 brute-force算法5.2.2 欧几里德算法,5.2.1 brute-force算法,算法描述(1)设x（或y）是x、y的最大公约数z；(2)判断x和y是否均能被z整除。若z不能同时整除x和y则z-1z，重复

3、S2步。否则，做下一步操作；(3)输出（或返回）z。,5.2.1 brute-force算法,#include int main(void)int x=30,y=45,z;z=x;while(!(x%z=0,程序实现,5.2.2 欧几里德算法,算法描述(1)判断x除以y的余数r是否为0。若r为0则y是x、y的最大公约数，继续做下步操作；否则yx，ry重复做第(1)步。(2)输出（或返回）y,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);re

4、turn 0;,程序实现,5.3 穷举法求满足条件的一组解,例1：某人在纸上写了一个四位整数3a45（a代表一个数字）。已知这个四位整数被3除后的值是1115，请问这个四位整数是什么？算法描述 用a的所有可能取值（09）分别形成10个四位整数3045、3145、3945 依次判断这10个四位整数中的每一个被3除后的值是否1115，若是则输出。,5.3 穷举法求满足条件的一组解,#include int main(void)int a,b;for(a=0;a=9;a+)b=3*1000+a*100+45;if(b/3=1115)printf(“%d”,b);,程序实现,5.3 穷举法求满足条件的

5、一组解,例2 中国古代数学著作算经中提出一个问题：公鸡每只5钱，母鸡每只3钱，小鸡1钱3只。若用100钱买100只鸡，可以有多少种买法？用x表示可以买到的公鸡数量、y表示可以买到的母鸡数量、z表示可以买到的小鸡数量。则：x+y+z=100，5x+3y+z/3=100,16,5.3 穷举法求满足条件的一组解,算法描述 不重复不遗漏地取x、y和z的所有可能值，分别将每组取值代入方程组 x+y+z=100，5x+3y+z/3=100 判断是不是方程组的解，若是解则输出x、y和z的这一组取值。,5.3 穷举法求满足条件的一组解,#include int main(void)int x,y,z;for(

6、x=0;x=20;x+)for(y=0;y=33;y+)for(z=0;z=100;z+)if(x+y+z=100,程序实现,5.4 级数近似计算,一个函数可以近似地表示为一个收敛的幂级数。因此函数求值问题可以归结为级数项求和问题。例如：用计算机计算无穷级数的值时只能计算有限个级数项的和。因此，用程序求得的级数值只能是在给定误差范围内的近似值。即：计算级数前n个项之和，当通项（第n项）的绝对值小于所给误差时停止级数项累加计算。,5.4 级数近似计算,5.4.1 简单方法5.4.2 递推法,5.4.1 简单方法,程序实现 计算ex级数展开式的近似值，误差为键盘输入的eps。,#include#i

7、nclude 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=n;m+)f*=m;a=pow(x,n)/f;s+=a;printf(“%f”,s);,5.4.2 递推法,算法描述在计算级数的各项值时从前项结果推出后项结果例如：将级数：表示为：则：a1=1，an=an-1 x/(n-1）（n=2，3，4）,5.4.2 递推法,采用递推法计算ex的级数展开式近似值，允许误差在eps范围内。,#inclu

8、de#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);,程序实现,5.5 一元非线性方程求根,5.5.1 牛顿迭代法 5.5.2 二分法和弦截法,5.5.1 牛顿迭代法,牛顿迭代公式 xn+1=xnf(xn)/f(xn)求方程f(x)=0在x0附近的一个近似实根。,5.5.1 牛顿迭代法,(1)用方程f(x)=0根的初始近似值x0带入牛顿迭代公式求得x1，

9、用x1带入牛顿迭代公式求得x2 如此重复可得到根的近似值序列x0,x1,x2,xn。(2)每求出一个新的近似值xn+1后均判断|f(xn+1)|或|xn+1-xn|是否成立，若成立则xn+1是所要求解的方程f(x)=0在x0附近、满足允许误差的一个近似实根。,算法描述,5.5.1 牛顿迭代法,采用牛顿迭代法求方程-3x3+4x2-5x+6=0在1.0附近的一个近似实根，允许求得的近似根在小数点后第6位存在误差。,#include#include int main(void)double x,x1,eps=1e-6,f,f1;x=1.0;dox1=x;,f=6-x1*(5-x1*(4-3*x1)

10、;f1=-5+x1*(8-9*x1);x=x1-f/f1;f=6-x*(5-x*(4-3*x);while(fabs(f)=eps,程序实现,5.5.2 二分法和弦截法,5.5.2 二分法和弦截法,找到x轴上的两个端点a和b使得方程f(x)=0在a,b中只有一个根；判断a和b是否为方程的近似根，若是立即结束计算；若a、b均不是近似根则计算a,b的中心点c=(a+b)/2，判断c是否为方程的近似根，若是则立即结束计算；若c不是近似根且ab则将a,b 区间调整到a,c或c,b（即将a,b 的长度缩小一半）并确保方程在调整后的a,b 中仍有一个实根；重复第(3)步直到找到根为止。,二分法算法描述,5

11、.5.2 二分法和弦截法,计算方程-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”,二分法程序实现,5.5.2 二分法和弦截法,if(fabs(f(a)eps,5.5.2 二分法和弦截法,找到x轴上的两个端点a和b使得方程f(x)=0在a,b中只有一个根；判断a和b是否为方程的近似根，

12、若是立即结束计算；若a、b均不是近似根则用以下公式计算a,b中的一点c的值，判断c是否为方程的近似根，若是则立即结束计算；若c不是近似根且ab则将a,b 区间调整到a,c或c,b（即将a,b 区间的长度缩小一半）并确保方程在调整后的a,b 中仍有一个实根；重复第(3)步直到找到根为止。,弦截法算法描述,5.6*定积分近似计算,5.6.1 梯形法 5.6.2 矩形法,5.6.1 梯形法,5.6.1 梯形法,将 对应的曲边梯形等分为n个小曲边梯形，每个小曲边梯形的高度h=(b-a)/n；采用梯形面积计算公式计算每个小曲边梯形面积近似值，所有小曲边梯形面积之和是所要求解的定积分近似值。,算法描述,5

13、.6.1 梯形法,采用梯形法计算 近似值。#include#include int main(void)long n,i;double a=-3.14159/2,b=3.14159/2,h,s,x;scanf(“%ld”,程序实现,5.6.2 矩形法,算法描述 将 对应的曲边梯形等分为n个小曲边梯形，每个小曲边梯形的高度h=(b-a)/n；将每个小曲边梯形看作矩形，采用矩形面积计算公式计算每个小矩形的面积，所有小矩形面积之和是所要求解的定积分近似值。,5.6.2 矩形法,采用矩形法计算 近似值。#include#include int main(void)long n,i;double a=-3.14159/2,b=3.14159/2,h,s=0,x;scanf(“%ld”,程序实现,