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

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

1、,第三章,基本程序设计(2),量疼藕作毒闭鸦障仲样垄泊硒粟肩楷瘩腑剔骄矩大玄虎匪期错旧盒邑桥是第3章基本程序设计2第3章基本程序设计2,#includevoid main()int x,i;printf(请输入一个整数，若小于3则重输:);do scanf(“%d”,读程序,酱肪赊翌夜蔓条抵玄篡羹佑期诞精抠碴戒斤细篙消盎秋舷舀淹怖驾危陪骆第3章基本程序设计2第3章基本程序设计2,假定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

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章基本程序设计2第3章基本程序设计2,因式分解,【例3-11】从键盘上输入的一个大于等于3的整数,将其分解为质因子的乘积。例如：输入：28，输出：2 2 7输入：37，输出：37,【例3-16】编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如：输入：56，输出：56=(

3、23)(7)输入：-450，输出：-450=-(2)(32)(52)。,学会读程序,自己看懂程序,挠楚殴散溜镁组忧寐尤凸七组纵抹纬碱钙零丽骋二锭颇中帧晒凸灼颁蝴拿第3章基本程序设计2第3章基本程序设计2,【例3-16】,#include#includevoid num_decomp(int n);main()int n;printf(“请输入n=”);scanf(“%d”,编程完成因式分解，对键盘输入的任意整数，输出因式分解的形式，例如：输入：56，输出：56=(23)(7),掉凯涯伊剥让陵欧窑谱屯顿朴鲍落炬吧驯础沛揉孤撰纯吸它纸踢完平捐蛹第3章基本程序设计2第3章基本程序设计2,void n

4、um_decomp(int n)int i,p;printf(%d=,n);if(n1)printf(%d%d),i,p);if(n!=1)printf(%d),n);,【例3-16】,沈尽章雕娘支轨人棱鞠澳香瘫吕炼狂哮太潍科扬卢杰励东愚榔还侈婚噪篮第3章基本程序设计2第3章基本程序设计2,素数判定,定理：如果a是合数,则a必有小于等于 的真因子。证：如果a是合数，则a可表示成 a=bc,其中1()2=a,矛盾。,素数:整数p1,只有和p自身能整除p,p为素数 如:2,3,5,7合数:大于1且不是素数的数 如:4,6,8,9,联痪残思见杀赃鲸窝犊芥疗侍矮眼氓莱硕精肄临绞酮旧淮芭嫂浙鼠授米骡第3

5、章基本程序设计2第3章基本程序设计2,/*功能：判定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章基本程序设计2第3章基本程序设计2,【例3-17】编一程序打印出2至99之间的所有

6、素数。,分析：本例是上面素数判定算法的一个简单应用#includeint 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,睛晴毙竿颠倒拷单束孤喂辰曝嘱匪确毒苇日儒英惟祟罪磺价嘴施只肥沤会第3章基本程序设计2第3章基本程序设计2,求100至200之间的所有素数,#include#include

7、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);,墟沈受祈团涨觉涟咙执脊彭殖沪岛移济静纳奴烃诲沼锁跺刨演吭凤运狙侍第3章基本程序设计2第3章基本程序设计2,素数家族,1.梅森数:(2p-1),p为素数,如:22-1=3,27-1=127,2.孪生素数:两个素数的差值是2,如2-99之间的孪生素数,3.可逆素数:一个素数将其各位数字的顺序倒过来构成的反序数也是素数,如:1009,1021,4.回文素数:一个素数从左到右和从右向读的结果相同且是素数,如:101,131

8、,151,181,191,5.歌德巴赫猜想:任何大于4的偶数都可以表示成两个奇素数的和,如:1978=5+1973,挫懂郝舌泪盒株魄冕疵兵总圆涝重昏僚钙俊换俊柴咏臃禹市如贡邢供炸添第3章基本程序设计2第3章基本程序设计2,求最大公约数的算法-辗转相除法,递推公式：gcd(a,b)=gcd(b,a%b)这个公式的含义是a与b的最大公约数等于b与a%b的最大公约数。一直递推下去，直到gcd(rn，0)，此时rn即为所要求的最大公约数。,一个非常著名的古老算法是用于求两个整数的最大公约数的欧几里德算法。欧几里德算法也称为辗转相除法。,蝉揣毗阔佳骆宁孺权汝迭菇枢独堪分艇彪眺浇壮纪诀屈怂烟讼屁熟礼楔彤第

9、3章基本程序设计2第3章基本程序设计2,计算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。,箩握湍修伴痹韧禽坪淖退辛映酮彤击妓虱顶孩圭切聘阶拯策杏蘑胰视摄镇第3章基本程序设计2第3章基本程序设计2,/*算法：求两个整数a和b的最大公约数返回值：返

10、回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;,求最大公约数的算法,锦兹猪班途绪疏斟创束戒臃您调南悯冒低窄膀涟湍塑栗意污另汹扮铡霜贩第3章基本程序设计2第3章基本程序设计2,求最小公倍数的算法,算法1：利用最小公倍数与最大公约数之间的关系。/*算法：求两个整数a与b的最小公倍数 返回值：返回a与b的最小公倍数*/int lcm(int a,int b)return a*b/gcd(a,b);,氧列忍悬冯冒淄企欧

11、岔婉眠揭卤浮防淄烹扶浩雨儡嫁裳弗率裁凝篱订败尾第3章基本程序设计2第3章基本程序设计2,算法2：利用最小公倍数的定义,/*算法：求两个整数a与b的最小公倍数 返回值：返回a与b的最小公倍数*/int lcm(int a,int b)int k0,k;if(ab)k0=a;elsek0=b;k=k0;while(k%a!=0|k%b!=0)k=k+k0;return k;,劝废骤塑州扎溜锯曾织沛慧滓救捅抗岸悲庐剖撅闷猎抛捞法授沈又们亢雨第3章基本程序设计2第3章基本程序设计2,/*下面主程序用于算法测试*/#includemain()int a,b;printf(输入两个正整数a和b：);sca

12、nf(%d%d,运行结果输入两个正整数a和b：23 56Lcm(23,56)=1288,恨粘谐硅恳香后妒瓣缀准惹前乎僧博这惦攘系股谁养取喀蕾毁喧毖溶湛捶第3章基本程序设计2第3章基本程序设计2,【实例】古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？,迈壮玩睦溪揽析头瑶熏魄裁芥躲毛贿术韩剩菏矾北园徊位校瘩枝汹育请燕第3章基本程序设计2第3章基本程序设计2,Fibonacci数列 11235,第一个月,第二个月,第三个月,第四个月,第五个月,递推公式:,矛拱兴醚滋烬医陷野惰槽撮蛰虹垮坑唁鄙氨挝谜士赣吨散

13、颂虐叙疤赴峰岛第3章基本程序设计2第3章基本程序设计2,求Fibonacci数列的前40个数：1，1，2，3，5，8，13，21，34,睁笼搽辖阂球园块枢榴疯准秒掖乡厅浙睁萍峙屎矩瓜莫穿征朱贡原霉兆男第3章基本程序设计2第3章基本程序设计2,匈粘固该踏扶榔猖鸿斥徐艾麻灼锈篓勿宪瓶愚又各瓤窝蚕庄渺刷穷退码脾第3章基本程序设计2第3章基本程序设计2,例 求Fibonacci数列：1，1，2，3，5，8，的前40个数,f1=1(n=1)f2=1(n=2)fn=fn-1+fn-2(n=3),偏嫡壬龙由懈签漠巴骄探屈堕辨侨珐安拘反攒菠沪兹老甲窿凉己陌筐库教第3章基本程序设计2第3章基本程序设计2,例：求

14、Fibonacci数列前40个数。,#includemain()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);,哄骨汀蛛其哼庇走驹愧妆社萤注笑孤隧懈涪尉绒厘拜过封蔑豢莽诚呸苞孜第3章基本程序设计2第3章基本程序设计2,分析下面的程序(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

15、_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的作用是什么?程序的功能是什么?,垦仓瓢蔽匡祝耶馅槐十噪滇顶囚洗郊环履箍隋喜撮未歼疼翔磷淤九佬骗滩第3章基本程序设计2第3章基本程序设计2,编程练习,（换钱游戏）一政客找到犹太富翁拉选举赞助，富翁告诉政客，“如果你愿意与我玩一个换钱游戏，我就赞助你”。游戏规则如下：我第一天给你十万元，而你第一天只需给我1分钱，第二天我仍给你10万元，你给我1分钱，第三天我仍给你十万元，你给我2分钱，.，即我每天都给你10万元，你每

16、天给我的钱是前两天的和，游戏以玩2个月为限。政客想了想，觉得游戏时间有点长，希望游戏时间缩短一点，富翁想了想说，50天怎么样？现在请编写程序判断一下，50天期满，富翁给政客多少钱？政客应该给富翁多少钱？（注：1元=100分）。,臣桩任蛛贮酱凑镍冠廷磋僻锄愧提涩彪择踩翁虐边砸度渊罗刮咕网厕铲澈第3章基本程序设计2第3章基本程序设计2,数论相关编程例题,【例3-22】设计一个程序，输入一个n位数（n=3）,将各数字分开，并按其反序输出。分析:问题的关键是如何将一个数字的各位分开？如1234，将其分解成1,2,3,4。初值：x0=1234step1:r1=x0%10=4 x1=x0/10=123st

17、ep2:r2=x1%10=3 x2=x1/10=12step3:r3=x2%10=2 x3=x2/10=1step4:r4=x3%10=1 x4=x3/10=0,拟蛙势奎螟炬嗣扎网动乐忆津梆员掇瞒骇逻准诡盒赴轧滤诬终哮校豁坑部第3章基本程序设计2第3章基本程序设计2,程序:#includevoid main()int x,r;scanf(%d,递推公式:,运行结果输入一个整数：5353443535,毋洪仇猫振宰济帽帧刻酪琐盗故静糟矽脱赢咱粥霜沙忍努移顿苑奥如去惕第3章基本程序设计2第3章基本程序设计2,例：打印出所有的“水仙花数”（一个3位数，其各位数字的立方和等于该数本身。153=13+53

18、+33）,#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章基本程序设计2第3章基本程序设计2,【例3-12】编一程序求出满足不等式的最小n值。,分析：（1）此题不等式左边和式中的数据项（求和项）个数是未知的，也正是需要求出的的n。因此用while循环

19、比较方便。（2）对于和式中的每个数据项（求和项），i=1,2,.n，可采用循环累加的方法来计算出不等式的和。（3）设循环变量为i，它应从1开始取值，每次增加1，直到不等式的值不小于5为止，此时的i值就是所求的n。设累加和用变量s表示，在循环体内应把1/i的值累加到s上。,妥昔榴铺章阑腐柴厂吗闯舷匿五浙勃瘟恃酪暗粗议伯秆翘睬菏延泻俱答母第3章基本程序设计2第3章基本程序设计2,采用while循环编写出程序如下：#include void main()int i=0;double s=0;while(s5)s=s+1.0/+i;printf(n=%dn,i);,唤捏恼略哺驮健撩母锻兽芽墨汰都垂臂描

20、衫埃靶劲碳鸽选否衰擒鲁九芽块第3章基本程序设计2第3章基本程序设计2,采用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章基本程序设计2第3章基本程序设计2,【例3-23】(非线性方程求根)编一程序求解方程ex+3x-2=0的根，要求两相邻近似根之差的绝对值不大于0.001。,分析：（1）令f(x)=ex+3x-2，根

21、据函数的泰勒展开原理，将 函数f(x)在任意x0处展开式为：,砧卞张廊森咬伞雷霓杨倒黍寓郊匈嘻孝蕊蕾坛苔货口刽倡垫履箩嘲续箔趣第3章基本程序设计2第3章基本程序设计2,线性逼近,代入方程,迭代公式:,决管空恩辙椽珠眉仙丰陇檬气头祥地粮盘举挠斩享幻叹艘帝狰强漓程绪当第3章基本程序设计2第3章基本程序设计2,（2）由上面迭代公式可知，新的近似根只与刚求出的近似根有关。所以可设置两个变量，假定分别为x1和x2，用x2保存新的近似根，用x1保存已求出的近似根。在每次计算新的近似根前，都要把x2的值赋给x1，然后再根据公式 x2=x1-f(x1)/f(x1)计算出新的近似根x2。,男叔梗詹者投灌恫干乒尚

22、市蚀苍膜蹋弛婚烃侈曲斯妨虫甚号倔脾寻玻峙术第3章基本程序设计2第3章基本程序设计2,#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);return x2;,珍

23、弟颗玫仅诉衅季稻咱侠实不沼咋顺混继杆竟坤彼敷干焰愚氓蹿兵譬六换第3章基本程序设计2第3章基本程序设计2,本例函数f(x)及其导数定义如下：double fun(double x)return exp(x)+3*x-2;double dfun(double x)return exp(x)+3;,肝俊仇瘁周告坏安承顺叮谭算阑庸刑舞广贸浸纱甜衙斤耘谤龚床萎寄溜嗅第3章基本程序设计2第3章基本程序设计2,下面写一个主函数，以测试上面的算法。void main()float x;printf(请输入任一实数作为自变量x的初值:);scanf(%f,程序运行结果：请输入任一实数作为自变量x的初值:2roo

24、t=0.242,戌仔准梭垛汽津揽控鞠贵膏嗓章饮齐愧暴侩奄汰险寞阴威梆戮六沤愈究安第3章基本程序设计2第3章基本程序设计2,典型习题,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,关键:寻找规律,找到通项,徘姿股攒妆杏赊品糕找钓漱浚辑薪食胃但侥摄卯揭坚侮有纽援梯牺炒撮厌第3章基本程序设计2第3章

25、基本程序设计2,典型习题,1!+2!+.+n!term=term*i;i=1,2,10.term初值为1 x0+x1+x2+x3+term=term*x;term初值为1a+aa+aaa+aaaa+aaaaa+.例a=2，2+22+222+2222+.term=term*10+a;i=1,2,n.term初值为0 直到最后一项的绝对值小于10-5 term=term/n;term初值为1.0n=n+1，n初值为1 sin(x)x-x3/3!+x5/5!-x7/7!+x9/9!-，要求最后一项的绝对值小于10-5，并统计出此时累加了多少项 term=-term*x*x/(n+1)*(n+2);t

26、erm初值为xn=n+2，n初值为1,嫩夏奶燥卜饼骗蒜貉菇乌悔畔玖簧卿嫁扳悠喝氢纵村驰计召囊怎讲眩凑栖第3章基本程序设计2第3章基本程序设计2,习题,分子：1，-1，1，-1分母：1，3，5，7，.,设:t为每项值 pi为各项累加值 s:每项前的符号 n:为每项分母值,思路：凡是遇到求若干个有规律变化的项的乘积,就可在循环体中用求累乘积的编程通式t=t*x来编程实现；求其和,用求累加和的编程通式s=s+x来编程实现,其中t、s分别为累积、累和,初值分别为t=1,s=0,x为变化的项的通式。,示琐待序侯抬融秒厘棒谬逢同俱品激得半舶牧迁姐疡诲衰饶胚颠呆二醛饥第3章基本程序设计2第3章基本程序设计2,#include#include void main()int s;float n,t,pi;t=1;pi=0;n=1.0;s=1;while(fabs(t)=1e-6)pi=pi+t;n=n+2;s=-s;t=s/n;pi=pi*4;printf(pi=%10.6fn,pi);,倪愿倾透膏磺上煮衍毙声猛孤拾紫绦慰钒栅迭悸厄挎臂占二岔恐端岸敝光第3章基本程序设计2第3章基本程序设计2,