《第3章基本程序设计2周优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第3章基本程序设计2周优秀PPT.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3 3章基本程序设计章基本程序设计2 2周周现在学习的是第1页，共41页#includevoid main()int x,i;printf(请输入一个整数，若小于请输入一个整数，若小于3则重输则重输:);do scanf(“%d”,&x);while(x=2);i=2;do while(x%i=0)printf(“%d”,i);x=x/i;i+;while(ix);if(x!=1)printf(“%dn”,x);读程序读程序现在学习的是第2页，共41页因式分解因式分解【例【例3-11】从键盘上输入的一个大于等于】从键盘上输入的一个大于等于3的整数的整数,将其将其分解分解为质因子的乘积为质因
2、子的乘积。例如：。例如：输入：输入：28，输出：，输出：2 2 7输入：输入：37，输出：，输出：37【例【例3-16】编程完成因式分解，对键盘输入的任意整数，输】编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如：出因式分解的形式，例如：输入：输入：56，输出：输出：56=(23)(7)输入：输入：-450，输出：，输出：-450=-(2)(32)(52)。学会读程序自己看懂程序现在学习的是第4页，共41页素数判定素数判定定理：定理：如果如果a是合数是合数,则则a必有小于等于必有小于等于 的的真因子。真因子。证：证：如果如果a是合数，则是合数，则a可表示成可表示成 a=bc,其
3、中其中1ba,1c()2=a,矛盾。矛盾。素数素数:整数整数p1,只有和只有和p自身能整除自身能整除p,p为素数为素数 如如:2,3,5,7合数合数:大于大于1且不是素数的数且不是素数的数 如如:4,6,8,9现在学习的是第7页，共41页/*功能：判定功能：判定x是否是素数，是否是素数，x2 返回值：返回返回值：返回1表示是素数，返回表示是素数，返回0则不是素数则不是素数*/int is_prime(int x)int m;if(x=2)return 1;if(x%2=0)return 0;/*偶数不是素数偶数不是素数*/m=sqrt(x);for(i=3;i=m;i+)if(x%i=0)/*
4、x能被能被i整除，整除，x不是素数不是素数*/return 0;return 1;/*循环结束还没有返回，说明循环结束还没有返回，说明x是素数是素数*/素数判定算法素数判定算法现在学习的是第8页，共41页【例【例3-173-17】编一程序打印出】编一程序打印出2 2至至9999之间的所有素数。之间的所有素数。分析：本例是上面素数判定算法的一个简单应用分析：本例是上面素数判定算法的一个简单应用#includeint is_prime(int x);void main()for(i=2;i100;i=i+1)if(is_prime(i)printf(%3d,i);/*上机调试时，将上机调试时，将i
5、s_prime函数定义放在这儿函数定义放在这儿*/运行结果运行结果 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 现在学习的是第9页，共41页求求100100至至200200之间的所有素数之间的所有素数#include#include#include#include void main()void main()int m,k,i,int m,k,i,n=0n=0;for(m=101;m=200;for(m=101;m=200;m=m+2m=m+2)k=sqrt(m);k=sqrt(m);for(i=
6、2;i=k;i+)for(i=2;i=k+1)printf(if(i=k+1)printf(%d%d ,m);,m);n=n+1;n=n+1;if(n%10=0)printf(if(n%10=0)printf(nn););printf(printf(nn););现在学习的是第10页，共41页素数家族素数家族1.梅森数梅森数:(2p-1),p为素数为素数,如如:22-1=3,27-1=1272.孪生素数孪生素数:两个素数的差值是两个素数的差值是2,如如2-99之间的孪生素数之间的孪生素数 3.可逆素数可逆素数:一个素数将其各位数字的顺序倒过来构成的反序数也是一个素数将其各位数字的顺序倒过来构成的
7、反序数也是素数素数,如如:1009,10214.回文素数回文素数:一个素数从左到右和从右向读的结果相同且是素数一个素数从左到右和从右向读的结果相同且是素数,如如:101,131,151,181,1915.歌德巴赫猜想歌德巴赫猜想:任何大于任何大于4的偶数都可以表示成两个奇素数的和的偶数都可以表示成两个奇素数的和,如如:1978=5+1973现在学习的是第11页，共41页求最大公约数的算法求最大公约数的算法-辗转相除法辗转相除法 递推公式：递推公式：gcd(a,b)=gcd(b,a%b)这个公式的含义是这个公式的含义是a与与b的最大公约数等于的最大公约数等于b与与a%b的最大的最大公约数。一直递
8、推下去，直到公约数。一直递推下去，直到gcd(rn，0)，此时，此时rn即为所即为所要求的最大公约数要求的最大公约数。一个非常著名的古老算法是用于求两个整数的最大公约数的欧几里德一个非常著名的古老算法是用于求两个整数的最大公约数的欧几里德算法。欧几里德算法也称为算法。欧几里德算法也称为辗转相除法辗转相除法。现在学习的是第12页，共41页计算计算91和和52的最大公约数，求解过程如下：的最大公约数，求解过程如下：（1）mod(91,52)=39（2）mod(52,39)=13（3）mod(39,13)=0所以，所以，13就是就是91和和52的最大公约数。的最大公约数。自然语言表示的欧几里德算法如
9、下：自然语言表示的欧几里德算法如下：输入：输入：两个正整数两个正整数m和和n输出：输出：m与与n的最大公约数的最大公约数(公因子公因子)。步骤步骤1:求余数，以求余数，以n除除m并令并令r为所得余数为所得余数(0rn)步骤步骤2:余数余数r为为0吗？若吗？若r=0，算法结束；，算法结束；n即为答案即为答案步骤步骤3:互换互换,置置mn，nr，转步骤，转步骤1。现在学习的是第13页，共41页/*算法：求两个整数算法：求两个整数a和和b的最大公约数的最大公约数返回值：返回返回值：返回a和和b的最大公约数的最大公约数*/int gcd(int a,int b)int r,t;if(ab)k0=a;e
10、lsek0=b;k=k0;while(k%a!=0|k%b!=0)k=k+k0;return k;现在学习的是第16页，共41页/*下面主程序用于算法测试下面主程序用于算法测试*/#includemain()int a,b;printf(输入两个正整数输入两个正整数a和和b：);scanf(%d%d,&a,&b);printf(Lcm(%d,%d)=%dn,a,b,lcm(a,b);运行结果运行结果输入两个正整数输入两个正整数a和和b：23 56Lcm(23,56)=1288现在学习的是第17页，共41页【实例】古典问题：有一对兔子，从出生后第【实例】古典问题：有一对兔子，从出生后第3 3个月
11、起每个月个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？子，假如兔子都不死，问每个月的兔子总数为多少？现在学习的是第18页，共41页Fibonacci数列数列 1 11 12 23 35 5第一个月第一个月第二个月第二个月第三个月第三个月第四个月第四个月第五个月第五个月递推公式递推公式:现在学习的是第19页，共41页求求Fibonacci数列的前数列的前40个数：个数：1，1，2，3，5，8，13，21，34Fibonacci螺旋螺旋21现在学习的是第20页，共41页现在学习的是第21
12、页，共41页例例 求求Fibonacci数列：数列：1，1，2，3，5，8，的前的前40个数个数f1=1,f2=1for i=1 to 20输出f1,f2f1=f1+f2f2=f2+f11534233159710946750255142293524578241578171855377258417711121393832040570288739088169213896104181286571964181346269922746563245986321144987676546368317811217830914930352102334155f1=1(n=1)f2=1(n=2)fn=fn-1+fn-
13、2(n=3)现在学习的是第22页，共41页例：求例：求FibonacciFibonacci数列前数列前4040个数。个数。#include#includemain()main()long int f1=1,f2=1;long int f1=1,f2=1;int i;int i;for(i=1;i=20;i+)for(i=1;i=20;i+)printf(printf(%12ld%12ld%12ld%12ld,f1,f2);,f1,f2);f1=f1+f2;f1=f1+f2;f2=f2+f1;f2=f2+f1;if(i%2=0)printf(n);现在学习的是第23页，共41页分析下面的程序分析
14、下面的程序(VCVC环境环境)#include void main()int i,k,fn,fn_1=1,fn_2=1;k=2;printf(%12d%12d,fn_1,fn_2);for(i=3;i=24;i+)fn=fn_1+fn_2;k=k+1;if(k%6=0)printf(%12dn,fn);else printf(%12d,fn);fn_2=fn_1;fn_1=fn;printf(n);K的作用是的作用是什么什么?程序的功能程序的功能是什么是什么?现在学习的是第24页，共41页例：打印出所有的例：打印出所有的“水仙花数水仙花数”（一个（一个3 3位数，其各位数字位数，其各位数字的立
15、方和等于该数本身。的立方和等于该数本身。153=1153=13 3+5+53 3+3+33 3）#include stdio.hvoid main()int i,j,k,n;for(n=100;n1000;n+)i=n/100;/*百位数百位数*/j=n/10-i*10;/*十位数十位数*/k=n%10;/*个位数个位数*/if(n=i*i*i+j*j*j+k*k*k)printf(%dn,n);运行结果：运行结果：153 370 371 407现在学习的是第28页，共41页【例【例3-123-12】编一程序求出满足不等式编一程序求出满足不等式的最小的最小n n值。值。分析：分析：（1 1）此
16、题不等式左边和式中的数据项（求和项）个数是未）此题不等式左边和式中的数据项（求和项）个数是未知的，也正是知的，也正是需要求出的的需要求出的的n n。因此。因此用用whilewhile循环比较方循环比较方便便。（2 2）对于和式中的每个数据项（求和项），）对于和式中的每个数据项（求和项），i=1,2,.ni=1,2,.n，可采用，可采用循环累加循环累加的方法来计算出不等式的方法来计算出不等式的和。的和。（3 3）设）设循环变量为循环变量为i i，它应从，它应从1 1开始取值，每次增加开始取值，每次增加1 1，直到不等式的值不小于直到不等式的值不小于5 5为止，此时的为止，此时的i i值就是所求的
17、值就是所求的n n。设累加和用变量。设累加和用变量s s表示，在循环体内应把表示，在循环体内应把1/i1/i的值的值累加到累加到s s上上。现在学习的是第29页，共41页采用采用while循环编写循环编写出程序如下：出程序如下：#include void main()int i=0;double s=0;while(s5)s=s+1.0/+i;printf(n=%dn,i);现在学习的是第30页，共41页采用采用for循环编写循环编写程序，则如下所示：程序，则如下所示：#include void main()int i;double s=0;for(i=1;s5;i+)s+=1.0/i;pri
18、ntf(n=%dn,i-1);/*注意：此注意：此i-1的值为所求的的值为所求的n值值*/该程序的输出结果应为：该程序的输出结果应为：n=83现在学习的是第31页，共41页【例【例3-233-23】(非线性方程求根非线性方程求根)编一程序编一程序求解方程求解方程e ex x+3x-2=0+3x-2=0的根，要求两相邻近的根，要求两相邻近似根之差的绝对值不大于似根之差的绝对值不大于0.0010.001。分析：分析：（1）令）令f(x)=ex+3x-2，根据函数的泰勒展开原理，将，根据函数的泰勒展开原理，将 函数函数f(x)在任意在任意x0处展开式为：处展开式为：现在学习的是第32页，共41页线性
19、逼近线性逼近,代入方程代入方程迭代公式迭代公式:现在学习的是第33页，共41页#include#includedouble fun(double x);/*函数函数f(x)*/double dfun(double x);/*f(x)的导数的导数f(x)*/double Newton(double x0)double x1,x2,y1,y2,eps=0.001;x2=x0;/*给给x2赋初值为赋初值为x0*/do x1=x2;y1=fun(x1);/*y1=f(x1)*/y2=dfun(x1);/*y2=f(x1)*/x2=x1-y1/y2;while(fabs(x2-x1)eps);retur
20、n x2;现在学习的是第35页，共41页本例函数本例函数f(x)及其导数定义如下：及其导数定义如下：double fun(double x)return exp(x)+3*x-2;double dfun(double x)return exp(x)+3;现在学习的是第36页，共41页下面写一个主函数，以测试上面的算法。下面写一个主函数，以测试上面的算法。void main()float x;printf(请输入任一实数作为自变量请输入任一实数作为自变量x的初值的初值:);scanf(%f,&x);x=Newton(x);/*调用求根算法调用求根算法*/printf(root=%8.3fn,x)
21、;程序运行结果：程序运行结果：请输入任一实数作为自变量请输入任一实数作为自变量x的初值的初值:2root=0.242现在学习的是第37页，共41页典型习题典型习题1*2*3+3*4*5+99*100*1011*2*3+3*4*5+99*100*101 term=i*(i+1)*(i+2);i=1,3,99 term=i*(i+1)*(i+2);i=1,3,99 前前前前100100项项之之之之积积 term=n*n/(n-1)*(n+1);n=2,4term=n*n/(n-1)*(n+1);n=2,4，100 100 1-1/2+1/3-1/4+1/99-1/100+1-1/2+1/3-1/4
22、+1/99-1/100+直到最后一直到最后一直到最后一直到最后一项项的的的的绝对值绝对值小于小于小于小于1010-4-4为为止止止止 term=sign/n;term=sign/n;分子分子分子分子sign=-sign;sign=-sign;初初初初值为值为1 1分母分母分母分母n=n+1;n=n+1;初初初初值为值为1 1 关键关键:寻找规律寻找规律,找到通项找到通项现在学习的是第38页，共41页典型习题典型习题 1!+2!+.+n!1!+2!+.+n!term=term*i;i=1,2,10.term=term*i;i=1,2,10.termterm初初初初值为值为1 1 x x0 0+x
23、+x1 1+x+x2 2+x+x3 3+term=term*x;term=term*x;termterm初初初初值为值为1 1 a+aa+aaa+aaaa+aaaaa+.a+aa+aaa+aaaa+aaaaa+.例例例例a=2a=2，2+22+222+2222+.2+22+222+2222+.term=term*10+a;i=1,2,n.term=term*10+a;i=1,2,n.termterm初初初初值为值为0 0 直到直到直到直到最后一最后一最后一最后一项项的的的的绝对值绝对值小于小于小于小于1010-5-5 term=term/n;term=term/n;termterm初初初初值为
24、值为1.01.0n=n+1n=n+1，n n初初初初值为值为1 1 sin(x)x-xsin(x)x-x3 3/3!+x/3!+x5 5/5!-x/5!-x7 7/7!+x/7!+x9 9/9!-/9!-，要求最后一，要求最后一，要求最后一，要求最后一项项的的的的绝对值绝对值小于小于小于小于1010-5-5，并并并并统计统计出此出此出此出此时时累加了多少累加了多少累加了多少累加了多少项项 term=-term*x*x/(n+1)*(n+2);term=-term*x*x/(n+1)*(n+2);termterm初初初初值为值为x xn=n+2n=n+2，n n初初初初值为值为1 1现在学习的是
25、第39页，共41页习题t=1,pi=0,n=1.0,s=1当|t|1e-6pi=pi+tn=n+2s=-st=s/npi=pi*4输出pi分子：1，-1，1，-1分母：1，3，5，7，.设设:t为每项值为每项值 pi为各项累加值为各项累加值 s:每项前的符号每项前的符号 n:为每项分母值为每项分母值思路：凡是遇到求若干个有规律变化的项的乘积思路：凡是遇到求若干个有规律变化的项的乘积,就可在循环体就可在循环体中用中用求累乘积求累乘积的的编程通式编程通式t=t*x来编程实现；求其和来编程实现；求其和,用用求累加和求累加和的的编编程通式程通式s=s+x来编程实现来编程实现,其中其中t、s分别为累积、
26、累和分别为累积、累和,初值分别为初值分别为t=1,s=0,x为变化的项的通式。为变化的项的通式。现在学习的是第40页，共41页#include#include#include#include void main()void main()int s;int s;float n,t,pi;float n,t,pi;t=1;pi=0;n=1.0;s=1;t=1;pi=0;n=1.0;s=1;while(fabs(t)=1e-6)while(fabs(t)=1e-6)pi=pi+t;pi=pi+t;n=n+2;n=n+2;s=-s;s=-s;t=s/n;t=s/n;pi=pi*4;pi=pi*4;printf(pi=%10.6fn,pi);printf(pi=%10.6fn,pi);t=1,pi=0,n=1.0,s=1当当|t|1e-6pi=pi+tn=n+2s=-st=s/npi=pi*4输出输出pi现在学习的是第41页，共41页