第3章基本程序设计2.ppt

《第3章基本程序设计2.ppt》由会员分享，可在线阅读，更多相关《第3章基本程序设计2.ppt（41页珍藏版）》请在优知文库上搜索。

1、第三章第三章#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,退出外循环退出外循环到此，程序的输出结果是到此，程序的输出结果是“2 2 2 3”，读者可以进一，读者可以进一步取步取x的不同值进行手工操作，例如，的不同值进行手工操作，例如，x=50时，输时，输出是出是“2 5 5”。因式分解因式分解【例【例3-11】从键盘上输入的一个大于等于】从键盘上输入

2、的一个大于等于3的整数的整数,将将其其分解为质因子的乘积分解为质因子的乘积。例如：。例如：输入：输入：28，输出：，输出：2 2 7输入：输入：37，输出：，输出：37【例【例3-16】编程完成因式分解，对键盘输入的任意整】编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如：数，输出因式分解的形式，例如：输入：输入：56，输出：输出：56=(23)(7)输入：输入：-450，输出：，输出：-450=-(2)(32)(52)。学会读程序自己看懂程序【例【例3-163-16】#include#includevoid num_decomp(int n);main()int n;prin

3、tf(“请输入请输入n=”);scanf(“%d”,&n);num_decomp(n);printf(n);编程完成因式分解，对键盘输入的任意整数，输出因编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如：式分解的形式，例如：输入：输入：56，输出：输出：56=(23)(7)void num_decomp(int n)int i,p;printf(%d=,n);if(n0)printf(-);n=abs(n);for(i=2;i1)printf(%d%d),i,p);if(n!=1)printf(%d),n);【例【例3-163-16】素数判定素数判定定理：定理：如果如果a是合数

4、是合数,则则a必有小于等于必有小于等于 的的真因子。真因子。证：证：如果如果a是合数，则是合数，则a可表示成可表示成 a=bc,其中其中1ba,1c()2=a,矛盾。矛盾。aaa素数素数:整数整数p1,只有和只有和p自身能整除自身能整除p,p为素数为素数 如如:2,3,5,7合数合数:大于大于1且不是素数的数且不是素数的数 如如:4,6,8,9/*功能：判定功能：判定x是否是素数，是否是素数，x2 返回值：返回返回值：返回1表示是素数，返回表示是素数，返回0则不是素数则不是素数*/int is_prime(int x)int m;if(x=2)return 1;if(x%2=0)return

5、0;/*偶数不是素数偶数不是素数*/m=sqrt(x);for(i=3;i=m;i+)if(x%i=0)/*x能被能被i整除，整除，x不是素数不是素数*/return 0;return 1;/*循环结束还没有返回，说明循环结束还没有返回，说明x是素数是素数*/素数判定算法素数判定算法【例【例3-173-17】编一程序打印出】编一程序打印出2 2至至9999之间的所有素数。之间的所有素数。分析：本例是上面素数判定算法的一个简单应用分析：本例是上面素数判定算法的一个简单应用#includeint is_prime(int x);void main()for(i=2;i100;i=i+1)if(is

6、_prime(i)printf(%3d,i);/*上机调试时，将上机调试时，将is_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 求求100100至至200200之间的所有素数之间的所有素数#include stdio.h#include#include#include void main()void main()int int m,k,i,m,k,i,n=0n=0;for(m for(m=101;m=200;=101;m=200;m=

7、m+2m=m+2)k=sqrt(m k=sqrt(m););for(i for(i=2;i=k;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););素数家族素数家族1.梅森数梅森数:(2p-1),p为素数为素数,如如:22-1=3,27-1=1272.孪生素数孪生素数:两个素数的差值是两个素数的差值是2,如如2-99之间的孪生素之间的孪生素数数 3.可逆素数可逆素数:一个素数将其各位数字的顺序倒过来构成的反序

8、一个素数将其各位数字的顺序倒过来构成的反序数也是素数数也是素数,如如:1009,10214.回文素数回文素数:一个素数从左到右和从右向读的结果相同且是素一个素数从左到右和从右向读的结果相同且是素数数,如如:101,131,151,181,1915.歌德巴赫猜想歌德巴赫猜想:任何大于任何大于4的偶数都可以表示成两个奇素数的的偶数都可以表示成两个奇素数的和和,如如:1978=5+1973C语言程序设计语言程序设计求最大公约数的算法求最大公约数的算法-辗转相除法辗转相除法 递推公式：递推公式：gcd(a,b)=gcd(b,a%b)这个公式的含义是这个公式的含义是a与与b的最大公约数等于的最大公约数等

9、于b与与a%b的最大公约数。一直递推下去，直到的最大公约数。一直递推下去，直到gcd(rn，0)，此时此时rn即为所要求的最大公约数即为所要求的最大公约数。一个非常著名的古老算法是用于求两个整数的最大公约数一个非常著名的古老算法是用于求两个整数的最大公约数的欧几里德算法。欧几里德算法也称为的欧几里德算法。欧几里德算法也称为辗转相除法辗转相除法。C语言程序设计语言程序设计计算计算91和和52的最大公约数，求解过程如下：的最大公约数，求解过程如下：（1）mod(91,52)=39（2）mod(52,39)=13（3）mod(39,13)=0所以，所以，13就是就是91和和52的最大公约数。的最大公

10、约数。自然语言表示的欧几里德算法如下：自然语言表示的欧几里德算法如下：输入：输入：两个正整数两个正整数m和和n输出：输出：m与与n的最大公约数的最大公约数(公因子公因子)。步骤步骤1:求余数，以求余数，以n除除m并令并令r为所得余数为所得余数(0rn)步骤步骤2:余数余数r为为0吗？若吗？若r=0，算法结束；，算法结束；n即为答案即为答案步骤步骤3:互换互换,置置mn，nr，转步骤，转步骤1。C语言程序设计语言程序设计/*算法：求两个整数算法：求两个整数a和和b的最大公约数的最大公约数返回值：返回返回值：返回a和和b的最大公约数的最大公约数*/int gcd(int a,int b)int r

11、,t;if(ab)k0=a;elsek0=b;k=k0;while(k%a!=0|k%b!=0)k=k+k0;return k;C语言程序设计语言程序设计/*下面主程序用于算法测试下面主程序用于算法测试*/#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)=1288C语言程序设计语言程序设计【实例】古典问题：有一对兔子，从出生后第【实例】古典问题：有一对兔子

12、，从出生后第3 3个月起每个个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？对兔子，假如兔子都不死，问每个月的兔子总数为多少？C语言程序设计语言程序设计)3()2(1)1(12121nfffnfnfnnn第一个月第一个月第二个月第二个月第三个月第三个月第四个月第四个月第五个月第五个月递推公式递推公式:求求Fibonacci数列的前数列的前40个数：个数：1，1，2，3，5，8，13，21，34)3()2(12)1(1121nFFFnFnFnnnFibonacci螺旋螺旋21例例 求求Fi

13、bonacci数列：数列：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-2(n=3)例：求例：求F

14、ibonacciFibonacci数列前数列前4040个数。个数。#includestdio.h#include main()main()long int long int f1=1,f2=1;f1=1,f2=1;int int i;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);分析下面的程序分析下面的程序(VCVC环境环境)#include void main()

15、int i,k,fn,fn_1=1,fn_2=1;k=2;printf(%12d%12d,fn_1,fn_2);for(i=3;i=3）,将各数字分开，并按其反序输出。将各数字分开，并按其反序输出。分析分析:问题的关键是如何将一个数字的各位分开？如问题的关键是如何将一个数字的各位分开？如1234，将其分解成，将其分解成1,2,3,4。初值：初值：x0=1234step1:r1=x0%10=4 x1=x0/10=123step2:r2=x1%10=3 x2=x1/10=12step3:r3=x2%10=2 x3=x2/10=1step4:r4=x3%10=1 x4=x3/10=0 程序程序:#i

16、ncludevoid main()int x,r;scanf(%d,&x);while(x!=0)r=x%10;x=x/10;printf(%d,r);printf(n);递推公式递推公式:运行结果运行结果输入一个整数：输入一个整数：5353443535例：打印出所有的例：打印出所有的“水仙花数水仙花数”（一个（一个3 3位数，其各位数，其各位数字的立方和等于该数本身。位数字的立方和等于该数本身。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【例【例3-123-12】编一程序求出满足不等式编一程序求出满足不等式的最小的最小n n值。值。分析：分析：（1 1）此题不等式左边和式中的数据项（求和项）个）此题不等式左边和式中的数据项（