第3章_基本程序设计-2(周)

第三章#includestdio.hvoidmain(){intx,i;printf(请输入一个整数，若小于3则重输:);doscanf(%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(%d\n,x);}读程序因式分解【例3-11】从键盘上输入的一个大于等于3的整数,将其分解为质因子的乘积。例如：输入：28，输出：227输入：37，输出：37【例3-16】编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如：输入：56，输出：56=(2^3)(7)输入：-450，输出：-450=-(2)(3^2)(5^2)。学会读程序自己看懂程序素数判定定理：如果a是合数,则a必有小于等于的真因子。证：如果a是合数，则a可表示成a=bc,其中1ba,1ca.显然,b和c中必有一个小于等于，否则,bc()2=a,矛盾。aaa§素数:整数p1,只有和p自身能整除p,p为素数如:2,3,5,7…§合数:大于1且不是素数的数如:4,6,8,9…/**********************************************功能：判定x是否是素数，x≥2返回值：返回1表示是素数，返回0则不是素数***********************************************/intis_prime(intx){intm;if(x==2)return1;if(x%2==0)return0;/*偶数不是素数*/m=sqrt(x);for(i=3;i=m;i++)if(x%i==0)/*x能被i整除，x不是素数*/return0;return1;/*循环结束还没有返回，说明x是素数*/}素数判定算法【例3-17】编一程序打印出2至99之间的所有素数。分析：本例是上面素数判定算法的一个简单应用#includestdio.hintis_prime(intx);voidmain(){for(i=2;i100;i=i+1)if(is_prime(i))printf(%3d,i);}/*上机调试时，将is_prime函数定义放在这儿*/运行结果2357111317192329313741434753596167717379838997求100至200之间的所有素数#includestdio.h#includemath.hvoidmain(){intm,k,i,n=0;for(m=101;m=200;m=m+2){k=sqrt(m);for(i=2;i=k;i++)if(m%i==0)break;if(i=k+1){printf(%d,m);n=n+1;}if(n%10==0)printf(\n);}printf(\n);}素数家族1.梅森数:(2p-1),p为素数,如:22-1=3,27-1=1272.孪生素数:两个素数的差值是2,如2-99之间的孪生素数3.可逆素数:一个素数将其各位数字的顺序倒过来构成的反序数也是素数,如:1009,10214.回文素数:一个素数从左到右和从右向读的结果相同且是素数,如:101,131,151,181,1915.歌德巴赫猜想:任何大于4的偶数都可以表示成两个奇素数的和,如:1978=5+1973C语言程序设计求最大公约数的算法--辗转相除法递推公式：gcd(a,b)=gcd(b,a%b)这个公式的含义是a与b的最大公约数等于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的最大公约数。自然语言表示的欧几里德算法如下：输入：两个正整数m和n输出：m与n的最大公约数(公因子)。步骤1:求余数，以n除m并令r为所得余数(0≤r＜n)步骤2:余数r为0吗？若r=0，算法结束；n即为答案步骤3:互换,置m←n，n←r，转步骤1。C语言程序设计/********************************************算法：求两个整数a和b的最大公约数返回值：返回a和b的最大公约数*********************************************/intgcd(inta,intb){intr,t;if(ab)/*确保第一个参数大于第二个参数*/{t=a;a=b;b=t;}r=a%b;while(r!=0){a=b;b=r;r=a%b;}returnb;}求最大公约数的算法C语言程序设计求最小公倍数的算法算法1：利用最小公倍数与最大公约数之间的关系。/*****************************************算法：求两个整数a与b的最小公倍数返回值：返回a与b的最小公倍数********************************************/intlcm(inta,intb){returna*b/gcd(a,b);}C语言程序设计算法2：利用最小公倍数的定义/******************************************算法：求两个整数a与b的最小公倍数返回值：返回a与b的最小公倍数********************************************/intlcm(inta,intb){intk0,k;if(ab)k0=a;elsek0=b;k=k0;while(k%a!=0||k%b!=0)k=k+k0;returnk;}C语言程序设计/*下面主程序用于算法测试*/#includestdio.hmain(){inta,b;printf(输入两个正整数a和b：);scanf(%d%d,&a,&b);printf(Lcm(%d,%d)=%d\n,a,b,lcm(a,b));}运行结果输入两个正整数a和b：2356Lcm(23,56)=1288C语言程序设计【实例】古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？C语言程序设计)3()2(1)1(12121nfffnfnfnnnFibonacci数列11235…第一个月第二个月第三个月第四个月第五个月递推公式:求Fibonacci数列的前40个数：1，1，2，3，5，8，13，21，34……Fibonacci螺旋21例求Fibonacci数列：1，1，2，3，5，8，……的前40个数f1=1,f2=1fori=1to20输出f1,f2f1=f1+f2f2=f2+f11534233159710946750255142293524578241578171855377258417711121393832040570288739088169213896104181286571964181346269922746563245986321144987676546368317811217830914930352102334155f1=1(n=1)f2=1(n=2)fn=fn-1+fn-2(n=3)例：求Fibonacci数列前40个数。#includestdio.hmain(){longintf1=1,f2=1;inti;for(i=1;i=20;i++){printf(%12ld%12ld,f1,f2);f1=f1+f2;f2=f2+f1;if(i%2==0)printf(\n);}}分析下面的程序(VC环境)#includestdio.hvoidmain(){inti,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(%12d\n,fn);elseprintf(%12d,fn);fn_2=fn_1;fn_1=fn;}printf(\n);}•K的作用是什么?•程序的功能是什么?例：打印出所有的“水仙花数”（一个3位数，其各位数字的立方和等于该数本身。153=13+53+33）#includestdio.hvoidmain(){inti,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(%d\n,n);}}运行结果：153370371407【例3-12】编一程序求出满足不等式的最小n值。分析：（1）此题不等式左边和式中的数据项（求和项）个数是未知的，也正是需要求出的的n。因此用while循环比较方便。（2）对于和式中的每个数据项（求和项），i=1,2,...n，可采用循环累加的方法来计算出不等式的和。（3）设循环变量为i，它应从1开始取值，每次增加1，直到不等式的值不小于5为止，此时的i值就是所求的n。设累加和用变量s表示，在循环体内应把1/i的值累加到s上。5131211n采用while循环编写出程序如下：#includestdio.hvoidmain(){inti=0;doubles=0;while(s5)s=s+1.0/++i;printf(n=%d\n,i);}采用for循环编写程序，则如下所示：#includestdio.hvoidmain(){inti;doubles=0;for(i=1;s5;i++)s+=1.0/i;printf(n=%d\n,i-1);/*注意：此i-1的值为所求的n值*/}该程序的输出结果应为：n=83【例3-23】(非线性方程求根)编一程序求解方程ex+3x-2=0的根，要求两相邻近似根之差的绝对值不大于0.001。分析：（1）令f(x)=ex+3x-2，根据函数的泰勒展开原理，将函数f(x)在任意x0处展开式为：)()(!21)(')()()(020000xfxxxfxxxfxf线性逼近,代入方程)(')(000xfxfxx0)(')()()(000xfxxxfxf)(')(111iiiixfxfxx迭代公式:#includestdio.h#includemath.hdoublefun(doublex);/*函数f(x)*/doubledfun(doublex);/*f(x)的导数f'(x)*/doubleNewton(doublex0){doublex1,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);returnx2;}本例函数f(x)及其导数定义如下：doublefun(doublex){returnexp(x)+3*x-2;}doubledfun(doublex){returnexp(x)+3;}下面写一个主函数，以测试上面的算法。voidmain(){floatx;printf(请输入任一实数作为自变量x的初值:);scanf(%f,&x);x=Newton(x);/*调用求根算法*/printf(root=%8.3f\n,x);}程序运行结果：请输入任一实数作为自变量x的初值:2root=0.242典型习题–1*2*3+3*4*5+…+99*100*101term=i*(i+1)*