C语言程序设计姜恒远著.pptx

1主要内容主要内容l5.1 素数判断素数判断l5.2 最大公约数求解最大公约数求解l5.3 穷举法求满足条件的一组解穷举法求满足条件的一组解l5.4 级数近似计算级数近似计算 l5.5 一元非线性方程求根一元非线性方程求根l*5.6 定积分近似计算定积分近似计算 25.1 素数判断素数判断 l素数素数 如果一个正整数如果一个正整数n只能被只能被1和和n自身整除，则称自身整除，则称n为素数（为素数（prime）。）。1不是素数，不是素数，2是素数。是素数。例如：例如：7是素数，是素数，8不是素数不是素数35.1 素数判断素数判断l5.1.1 最简单素数判断算法最简单素数判断算法l5.1.2 改进后的素数判断算法改进后的素数判断算法45.1.1 最简单素数判断算法最简单素数判断算法 l算法描述算法描述 若若n2且且n不能被不能被2n-1范围内的任一个整数整范围内的任一个整数整除，除，n就是素数；否则就是素数；否则n不是素数；若发现不是素数；若发现n不不是素数，立即停止后续判断。是素数，立即停止后续判断。l程序实现程序实现 for(t=1,i=2;t&i2且且n不能被不能被2sqrt(n)之间的所有整数之间的所有整数整除，整除，n就是素数。就是素数。l程序实现程序实现 r=sqrt(n);for(t=1,i=2;t&i=r;i+)if(n%i=0)t=0;if(t)printf(“%d is prime”,n);65.2 最大公约数求解最大公约数求解 l最大公约数最大公约数 能同时被能同时被x和和y整除的最大整数是整数整除的最大整数是整数x和和y的最的最大公约数（大公约数（GCD）。例如：例如：30和和45的公约数有的公约数有3、5、15，其中，其中15是是30和和45的最大公约数。的最大公约数。75.2 最大公约数求解最大公约数求解l5.2.1 brute-force算法算法l5.2.2 欧几里德算法欧几里德算法85.2.1 brute-force算法算法 l算法描述算法描述(1)设设x（或或y）是是x、y的最大公约数的最大公约数z；(2)判判断断x和和y是是否否均均能能被被z整整除除。若若z不不能能同同时时整整除除x和和y则则z-1z，重重复复S2步步。否否则则，做做下下一一步步操作；操作；(3)输出（或返回）输出（或返回）z。95.2.1 brute-force算法算法#include int main(void)int x=30,y=45,z;z=x;while(!(x%z=0&y%z=0)z-;printf(“%d”,z);return 0;程序实现程序实现105.2.2 欧几里德算法欧几里德算法 l算法描述算法描述(1)判判断断x除除以以y的的余余数数r是是否否为为0。若若r为为0则则y是是x、y的的最最大大公公约约数数，继继续续做做下下步步操操作作；否否则则yx，ry重复做第重复做第(1)步。步。(2)输出（或返回）输出（或返回）y 115.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;程序实现程序实现125.3 穷举法求满足条件的一组解穷举法求满足条件的一组解 例例1：某人在纸上写了一个四位整数：某人在纸上写了一个四位整数3a45（a代表代表一个数字）。已知这个四位整数被一个数字）。已知这个四位整数被3除后的值除后的值是是1115，请问这个四位整数是什么？，请问这个四位整数是什么？l算法描述算法描述 用用a的所有可能取值（的所有可能取值（0 9）分别形成）分别形成10个四位个四位整数整数3045、3145、3945 依次判断这依次判断这10个四位整数中的每一个被个四位整数中的每一个被3除后的除后的值是否值是否1115，若是则输出。，若是则输出。135.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);程序实现程序实现145.3 穷举法求满足条件的一组解穷举法求满足条件的一组解例例2 中国古代数学著作算经中提出一个问题：中国古代数学著作算经中提出一个问题：公鸡每只公鸡每只5钱，母鸡每只钱，母鸡每只3钱，小鸡钱，小鸡1钱钱3只。若只。若用用100钱买钱买100只鸡，可以有多少种买法？只鸡，可以有多少种买法？用用x表示可以买到的公鸡数量、表示可以买到的公鸡数量、y表示可以买表示可以买到的母鸡数量、到的母鸡数量、z表示可以买到的小鸡数量。表示可以买到的小鸡数量。则：则：x+y+z=100，5x+3y+z/3=100 155.3 穷举法求满足条件的一组解穷举法求满足条件的一组解l算法描述算法描述 不不重重复复不不遗遗漏漏地地取取x、y和和z的的所所有有可可能能值值，分分别别将每组取值代入方程组将每组取值代入方程组 x+y+z=100，5x+3y+z/3=100 判判断断是是不不是是方方程程组组的的解解，若若是是解则输出解则输出x、y和和z的这一组取值。的这一组取值。165.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&5*x+3*y+z/3=100&z%3=0)printf(“x=%d,y=%d,z=%dn”,x,y,z);return 0;程序实现程序实现175.4 级数近似计算级数近似计算 一个函数可以近似地表示为一个收敛的幂级数。一个函数可以近似地表示为一个收敛的幂级数。因此函数求值问题可以归结为级数项求和问题。因此函数求值问题可以归结为级数项求和问题。例如例如：用计算机计算无穷级数的值时只能计算有限个用计算机计算无穷级数的值时只能计算有限个级数项的和。因此，用程序求得的级数值只能级数项的和。因此，用程序求得的级数值只能是在给定误差范围内的近似值。即：计算级数是在给定误差范围内的近似值。即：计算级数前前n个项之和，当通项（第个项之和，当通项（第n项）的绝对值小于项）的绝对值小于所给误差时停止级数项累加计算。所给误差时停止级数项累加计算。185.4 级数近似计算级数近似计算l5.4.1 简单方法简单方法l5.4.2 递推法递推法 195.4.1 简单方法简单方法 l程序实现程序实现 计算计算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”,&x,&eps);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);205.4.2 递推法递推法 l算法描述算法描述在计算级数的各项值时从前项结果推出后项结果在计算级数的各项值时从前项结果推出后项结果例如：例如：将级数：将级数：表示为：表示为：则：则：a1=1，an=an-1 x/(n-1）（n=2，3，4）215.4.2 递推法递推法l采用递推法计算采用递推法计算ex的级数展开式近似值，允许误的级数展开式近似值，允许误差在差在eps范围内。范围内。#include#include int main(void)double s=1,a=1,x,eps;int n;printf(“input x and eps:”);scanf(“%lf%lf”,&x,&eps);for(n=2;fabs(a)eps;n+)a=a*x/(n-1);s+=a;printf(“%f”,s);程序实现程序实现225.5 一元非线性方程求根一元非线性方程求根 l5.5.1 牛顿迭代法牛顿迭代法 l5.5.2 二分法和弦截法二分法和弦截法 235.5.1 牛顿迭代法牛顿迭代法 l牛顿迭代公式牛顿迭代公式 xn+1=xnf(xn)/f(xn)求方程求方程f(x)=0在在x0附近附近的一个近似实根的一个近似实根。245.5.1 牛顿迭代法牛顿迭代法l(1)用方程用方程f(x)=0根的初始近似值根的初始近似值x0带入牛顿迭带入牛顿迭代公式求得代公式求得x1，用，用x1带入牛顿迭代公式求得带入牛顿迭代公式求得x2 如此重复可得到根的如此重复可得到根的近似值序列近似值序列x0,x1,x2,xn。l(2)每求出一个新的每求出一个新的近似值近似值xn+1后均判断后均判断|f(xn+1)|或或|xn+1-xn|是否成立，若成立则是否成立，若成立则xn+1是所要求解的方程是所要求解的方程f(x)=0在在x0附近、满足允许误附近、满足允许误差差 的一个近似实根。的一个近似实根。算法描述算法描述255.5.1 牛顿迭代法牛顿迭代法l采用牛顿迭代法采用牛顿迭代法求方程求方程-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);f1=-5+x1*(8-9*x1);x=x1-f/f1;f=6-x*(5-x*(4-3*x);while(fabs(f)=eps&fabs(x-x1)=eps);printf(“x=%f”,x);程序实现程序实现265.5.2 二分法和弦截法二分法和弦截法 275.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不是近似根且不是近似根且a b则将则将a,b 区间调整到区间调整到a,c或或c,b（即将即将a,b 的长度缩小一半）的长度缩小一半）并确保方程并确保方程在在调整后的调整后的a,b 中仍有一个实根中仍有一个实根；重复第；重复第(3)步直到找到根为止。步直到找到根为止。二分法算法描述二分法算法描述285.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”,&a,&b);while(f(a)*f(b)0);二分法程序实现二分法程序实现295.5.2 二分法和弦截法二分法和弦截法 if(fabs(f(a)1e-6)x=a;else if(fabs(f(b)eps&fabs(b-a)eps)if(f(a)*f(c)0)b=c;else a=c;c=(b+a)/2;x=c;printf(“x=%f”,x);305.5.2 二分法和弦截法二分法和弦截法 找到找到x轴上的两个端点轴上的两个端点a和和b使得方程使得方程f(x)=0在在a,b中只中只有一个根；判断有一个根；判断a和和b是否为方程的近似根，若是立即结是否为方程的近似根，若是立即结束计算；束计算；若若a、b均不是近似根则用以下公式计算均不是近似根则用以下公式计算a,b中的一点中的一点c的值的值，判断，判断c是否为方程的近似根，若是则立即结束计是否为方程的近似根，若是则立即结束计算；算；若若c不是近似根且不是近似根且a b则将则将a,b 区间调整到区间调整到a,c或或c,b（即将即将a,b 区间的长度缩小一半）并确保方程区间的长度缩小一半）并确保方程在在调整后的调整后的a,b 中仍有一个实根中仍有一个实根；重复第；重复第(3)步直到步直到找到根为止。找到根为止。弦截法算法描述弦截法算法描述315.6*定积分近似计算定积分近似计算l5.6.1 梯形法梯形法 l5.6.2 矩形法矩形法325.6.1 梯形法梯形法 335.6.1 梯形法梯形法l将将 对应的曲边梯形等分为对应的曲边梯形等分为n个小曲边梯形，个小曲边梯形，每个小曲边梯形的高度每个小曲边梯形的高度h=(b-a)/n；采用梯形面采用梯形面积计算公式计算每个小曲边梯形面积近似值，积计算公式计算每个小曲边梯形面积近似值，所有小曲边梯形面积之和是所要求解的定积分所有小曲边梯形面积之和是所要求解的定积分近似值。近似值。算法描述算法描述345.6.1 梯形法梯形法l采用梯形法计算采用梯形法计算 近似值。近似值。#include#include int main(void)long n,i;double a=-3.14159/2,b=3.14159/2,h,s,x;scanf(“%ld”,&n);h=(b-a)/n;s=(cos(a)+cos(b)/2;x=a;for(i=1;in;i+)x+=h;s+=cos(x);printf(“s=%f”,s*h);程序实现程序实现355.6.2 矩形法矩形法l算法描述算法描述 将将 对应的曲边梯形等分为对应的曲边梯形等分为n个小曲边梯形，个小曲边梯形，每个小曲边梯形的高度每个小曲边梯形的高度h=(b-a)/n；将每个小曲将每个小曲边梯形看作矩形，采用矩形面积计算公式计算边梯形看作矩形，采用矩形面积计算公式计算每个小矩形的面积每个小矩形的面积，所有小矩形面积之和是所所有小矩形面积之和是所要求解的定积分近似值。要求解的定积分近似值。365.6.2 矩形法矩形法l 采用矩形法计算采用矩形法计算 近似值。近似值。#include#include int main(void)long n,i;double a=-3.14159/2,b=3.14159/2,h,s=0,x;scanf(“%ld”,&n);h=(b-a)/n;x=a;for(i=0;in;i+)x+=h;s+=cos(x);printf(“s=%f”,s*h);程序实现程序实现