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

1,第5章 常用数值计算算法及其程序设计,2,主要内容,5.1 素数判断 5.2 最大公约数求解 5.3 穷举法求满足条件的一组解 5.4 级数近似计算 5.5 一元非线性方程求根 *5.6 定积分近似计算,3,5.1 素数判断,素数 如果一个正整数n只能被1和n自身整除，则称n为素数（prime）。1不是素数，2是素数。 例如：7是素数，8不是素数,4,5.1 素数判断,5.1.1 最简单素数判断算法 5.1.2 改进后的素数判断算法,5,5.1.1 最简单素数判断算法,算法描述 若n2且n不能被2n-1范围内的任一个整数整除，n就是素数；否则n不是素数；若发现n不是素数，立即停止后续判断。 程序实现 for (t=1,i=2;t,6,5.1.2 改进后的素数判断算法,算法描述 如果n2且n不能被2sqrt(n)之间的所有整数整除，n就是素数。 程序实现 r=sqrt(n); for(t=1,i=2; t,7,5.2 最大公约数求解,最大公约数 能同时被x和y整除的最大整数是整数x和y的最大公约数（GCD） 。 例如：30和45的公约数有3、5、15，其中15是30和45的最大公约数。,8,5.2 最大公约数求解,5.2.1 brute-force算法 5.2.2 欧几里德算法,9,5.2.1 brute-force算法,算法描述 (1) 设x（或y）是x、y的最大公约数z； (2) 判断x和y是否均能被z整除。若z不能同时整除x和y则z-1z，重复S2步。否则，做下一步操作； (3) 输出（或返回）z。,10,5.2.1 brute-force算法,#include int main(void) int x=30,y=45,z; z=x; while(!(x%z=0 ,程序实现,11,5.2.2 欧几里德算法,算法描述 (1) 判断x除以y的余数r是否为0。若r为0则y是x、y的最大公约数，继续做下步操作；否则yx，ry重复做第(1)步。 (2) 输出（或返回）y,12,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; ,程序实现,13,5.3 穷举法求满足条件的一组解,例1：某人在纸上写了一个四位整数3a45（a代表一个数字）。已知这个四位整数被3除后的值是1115，请问这个四位整数是什么？ 算法描述 用a的所有可能取值（09）分别形成10个四位整数3045、3145、3945 依次判断这10个四位整数中的每一个被3除后的值是否1115，若是则输出。,14,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); ,程序实现,15,5.3 穷举法求满足条件的一组解,例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的这一组取值。,17,5.3 穷举法求满足条件的一组解,#include int main(void) int x,y,z; for(x=0;x=20;x+) for(y=0;y=33;y+) for(z=0;z=100;z+) if(x+y+z=100 ,程序实现,18,5.4 级数近似计算,一个函数可以近似地表示为一个收敛的幂级数。因此函数求值问题可以归结为级数项求和问题。例如 ： 用计算机计算无穷级数的值时只能计算有限个级数项的和。因此，用程序求得的级数值只能是在给定误差范围内的近似值。即：计算级数前n个项之和，当通项（第n项）的绝对值小于所给误差时停止级数项累加计算。,19,5.4 级数近似计算,5.4.1 简单方法 5.4.2 递推法,20,5.4.1 简单方法,程序实现 计算ex级数展开式的近似值，误差为键盘输入的eps。,#include #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=n;m+) f*=m; a=pow(x,n)/f; s+=a; printf(“%f”,s); ,21,5.4.2 递推法,算法描述 在计算级数的各项值时从前项结果推出后项结果 例如： 将级数： 表示为： 则： a1=1， an=an-1 x/(n-1） （n=2，3，4）,22,5.4.2 递推法,采用递推法计算ex的级数展开式近似值，允许误差在eps范围内。,#include #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); ,程序实现,23,5.5 一元非线性方程求根,5.5.1 牛顿迭代法 5.5.2 二分法和弦截法,24,5.5.1 牛顿迭代法,牛顿迭代公式 xn+1= xnf(xn)/f (xn) 求方程f(x)=0在x0附近的一个近似实根。,25,5.5.1 牛顿迭代法,(1) 用方程f(x)=0根的初始近似值x0带入牛顿迭代公式求得x1，用x1带入牛顿迭代公式求得x2 如此重复可得到根的近似值序列x0,x1,x2,xn 。 (2) 每求出一个新的近似值xn+1后均判断|f(xn+1)| 或|xn+1-xn|是否成立，若成立则xn+1是所要求解的方程f(x)=0在x0附近、满足允许误差的一个近似实根。,算法描述,26,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; 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 ,程序实现,27,5.5.2 二分法和弦截法,28,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)步直到找到根为止。,二分法算法描述,29,5.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”,二分法程序实现,30,5.5.2 二分法和弦截法,if(fabs(f(a)eps ,31,5.5.2 二分法和弦截法, 找到x轴上的两个端点a和b使得方程f(x)=0在a,b中只有一个根；判断a和b是否为方程的近似根，若是立即结束计算； 若a、b均不是近似根则用以下公式计算a,b中的一点c的值 ，判断c是否为方程的近似根，若是则立即结束计算； 若c不是近似根且ab则将a,b 区间调整到a,c或c,b（即将a,b 区间的长度缩小一半）并确保方程在调整后的a,b 中仍有一个实根 ；重复第(3)步直到找到根为止。,弦截法算法描述,32,5.6* 定积分近似计算,5.6.1 梯形法 5.6.2 矩形法,33,5.6.1 梯形法,34,5.6.1 梯形法,将 对应的曲边梯形等分为n个小曲边梯形，每个小曲边梯形的高度h=(b-a)/n；采用梯形面积计算公式计算每个小曲边梯形面积近似值，所有小曲边梯形面积之和是所要求解的定积分近似值。,算法描述,35,5.6.1 梯形法,采用梯形法计算 近似值。 #include #include int main(void) long n,i; double a=-3.14159/2,b=3.14159/2, h,s,x; scanf(“%ld”, ,程序实现,36,5.6.2 矩形法,算法描述 将 对应的曲边梯形等分为n个小曲边梯