《基本程序设计2周》PPT课件.pptVIP

,第三章,基本程序设计(2),#include void main() int x,i; printf(“请输入一个整数，若小于3则重输:“); do scanf(“%d“, ,读程序,假定x=24，按程序执行过程，手工演算一遍： i x x%i 动作 2 24 0 执行内循环，输出2，x=12 2 12 0 执行内循环，输出2，x=6 (x=x/i) 2 6 0 执行内循环，输出2，x=3 (x=x/i) 2 3 1 退出内循环，i=i+1 3 3 0 执行内循环，输出3，x=1 3 1 1 退出内循环，i=4,ix,退出外循环 到此，程序的输出结果是“2 2 2 3”，读者可以进一步取x的不同值进行手工操作，例如，x=50时，输出是“2 5 5”。,因式分解,【例3-11】从键盘上输入的一个大于等于3的整数,将其分解为质因子的乘积。例如： 输入：28，输出：2 2 7 输入：37，输出：37,【例3-16】编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如： 输入：56， 输出：56=(23)(7) 输入：-450 ，输出：-450=-(2)(32)(52) 。,学会读程序,自己看懂程序,【例3-16】,#include #include void num_decomp(int n); main() int n; printf(“请输入n=“); scanf(“%d“, ,编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如： 输入：56， 输出：56=(23)(7),void num_decomp(int n) int i,p; printf(“%d=“,n); if(n1) printf(“(%d%d)“,i,p); if(n!=1) printf(“(%d)“,n); ,【例3-16】,素数判定,定理：如果a是合数, 则a必有小于等于 的真因子。 证： 如果a是合数，则a可表示成 a=bc, 其中1( )2=a, 矛盾。,素数:整数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 0; /*偶数不是素数*/ m=sqrt(x); for(i=3;i=m;i+) if (x%i=0) /*x能被i整除，x不是素数*/ return 0; return 1; /*循环结束还没有返回，说明x是素数*/ ,素数判定算法,【例3-17】编一程序打印出2至99之间的所有素数。,分析：本例是上面素数判定算法的一个简单应用 #include int is_prime(int x); void main() for(i=2;i100;i=i+1) if(is_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,求100至200之间的所有素数,#include #include void main( ) int m,k,i,n=0; for(m=101;m=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=127,2.孪生素数: 两个素数的差值是2, 如2-99之间的孪生素数,3.可逆素数: 一个素数将其各位数字的顺序倒过来构成的反序数也是素数, 如:1009,1021,4.回文素数: 一个素数从左到右和从右向读的结果相同且是素数, 如:101,131,151,181,191,5.歌德巴赫猜想: 任何大于4的偶数都可以表示成两个奇素数的和, 如:1978=5+1973,求最大公约数的算法-辗转相除法,递推公式： gcd(a,b)=gcd(b,a%b) 这个公式的含义是a与b的最大公约数等于b与a%b的最大公约数。一直递推下去，直到gcd(rn，0)，此时rn即为所要求的最大公约数。,一个非常著名的古老算法是用于求两个整数的最大公约数的欧几里德算法。欧几里德算法也称为辗转相除法。,计算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为所得余数(0rn) 步骤2:余数r为0吗？若r=0，算法结束；n即为答案 步骤3:互换,置mn， nr，转步骤1。,/* 算法：求两个整数a和b的最大公约数 返回值：返回a和b的最大公约数 */ int gcd(int a,int b) int r,t; if(ab) /*确保第一个参数大于第二个参数*/ t=a; a=b; b=t; r=a%b; while(r!=0) a=b; b=r; r=a%b; return b; ,求最大公约数的算法,求最小公倍数的算法,算法1： 利用最小公倍数与最大公约数之间的关系。 /* 算法：求两个整数a与b的最小公倍数 返回值：返回a与b的最小公倍数 */ int lcm(int a,int b) return a*b/gcd(a,b); ,算法2：利用最小公倍数的定义,/* 算法：求两个整数a与b的最小公倍数 返回值：返回a与b的最小公倍数 */ int lcm(int a,int b) int k0,k; if(ab) k0=a; else k0=b; k=k0; while( k%a !=0 | k%b !=0 ) k=k+k0; return k; ,/*下面主程序用于算法测试*/ #include main() int a,b; printf(“输入两个正整数a和b：“); scanf(“%d%d“, 运行结果 输入两个正整数a和b：23 56 Lcm(23,56)=1288,【实例】古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？,Fibonacci数列 1 1 2 3 5 ,第一个月,第二个月,第三个月,第四个月,第五个月,递推公式:,求Fibonacci数列的前40个数： 1，1，2，3，5，8，13，21，34,例 求Fibonacci数列：1，1，2，3，5，8，的前40个数,f1=1 (n=1) f2=1 (n=2) fn=fn-1+fn-2 (n=3),例：求Fibonacci数列前40个数。,#include main() long int f1=1,f2=1; int i; for(i=1;i=20;i+) printf(“%12ld%12ld“,f1,f2); f1=f1+f2; f2=f2+f1; if(i%2=0) printf(“n“); ,分析下面的程序(VC环境),#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的作用是什么? 程序的功能是什么?,编程练习,（换钱游戏）一政客找到犹太富翁拉选举赞助，富翁告诉政客，“如果你愿意与我玩一个换钱游戏，我就赞助你”。游戏规则如下：我第一天给你十万元，而你第一天只需给我1分钱，第二天我仍给你10万元，你给我1分钱，第三天我仍给你十万元，你给我2分钱，即我每天都给你10万元，你每天给我的钱是前两天的和，游戏以玩2个月为限。政客想了想，觉得游戏时间有点长，希望游戏时间缩短一点，富翁想了想说，50天怎么样？现在请编写程序判断一下，50天期满，富翁给政客多少钱？政客应该给富翁多少钱？（注：1元=100分）。,数论相关编程例题,【例3-22】设计一个程序，输入一个n位数（n=3）,将各数字分开，并按其反序输出。 分析: 问题的关键是如何将一个数字的各位分开？如1234，将其分解成1,2,3,4。 初值： x0=1234 step1: r1=x0%10 = 4 x1=x0/10 = 123 step2: r2=x1%10 = 3 x2=x1/10 = 12 step3: r3=x2%10 = 2 x3=x2/10 = 1 step4: r4=x3%10 = 1 x4=x3/10 = 0,程序: #include void main() int x,r; scanf(“%d“, ,递推公式:,运行结果 输入一个整数：53534 43535,例：打印出所有的“水仙花数”（一个3位数，其各位数字的立方和等于该数本身。153=13+53+33）,#include “stdio.h“ void 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-12】 编一程序求出满足不等式 的最小n值。,分析： （1）此题不等式左边和式中的数据项（求和项）个数是未知的，也正是需要求出的的n。因此用while循环比较方便。 （2）对于和式中的每个数据项（求和项），i=1,2,.n，可采用循环累加的方法来计算出不等式的和。 （3）设循环变量为i，它应从1开始取值，每次增加1，直到不等式的值不小于5为止，此时的i值就是所求的n。设累加和用变量s表示，在循环体内应把1/i的值累加到s上。,采用while循环编写出程序如下： #include void main() int i=0; double s=0; while(s5) s=s + 1.0/+i; printf(“n=%dn“,i); ,采用for循环编写程序，则如下所示： #include void main() int i; double s=0; for(i=1; s5; i+) s+=1.0/i; printf(“n=%dn“,i-1); /*注意：此i-1的值为所求的n值*/ 该程序的输出结果应为：n=83,【例3-23】(非线性方程求根)编一程序求解方程ex+3x-2=0的根，要求两相邻近似根之差的绝对值不大于0.001。,分析： （1）令f(x)=ex+3x-2，根据函数的泰勒展开原理，将 函数f(x)在任意x0处展开式为：,线性逼近,代入方程,迭代公式:,（2）由上面迭代公式可知，新的近似根只与刚求出的近似根有关。 所以可设置两个变量，假定分别为x1和x2，用x2保存新的近似根，用x1保存已求出的近似根。 在每次计算新的近似根前，都要把x2的值赋给x1，然后再根据公式 x2=x1-f(x1)/f(x1)计算出新的近似根x2。,#include #include double 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); return x2; ,本例函数f(x)及其导数定义如下： double fun(double x) return exp(x)+3*x-2 ; double dfun(double x) return exp(x)+3 ; ,下面写一个主函数，以测试上面的算法。 void main() float x; printf(“请输入任一实数作为自变量x的初值:“); scanf(“%f“, 程序运行结果： 请输入任一实数作为自变量x的初值:2 root= 0.242,典型习题,1*2*3 + 3*4*5 + + 99*100*101 term = i * (i+1) * (i+2); i = 1,3,99 前100项之积 term = n * n / (n-1) * (n+1); n = 2,4，100 1 - 1/2 + 1/3 - 1/4 + + 1/99 - 1/100 + 直到最后一项的绝对值小于10-4为止 term = sign / n; 分子sign = -sign; 初值为1 分母n = n + 1; 初值为1,关键:寻找规律,找到通项,典型习题,1!+2!+.+n! term = term * i; i = 1,2,10. term初值为1 x0 + x1 + x2 + x3 + term = term * x; term初值为1