吴文虎程序设计基础ppt第五讲.ppt
- 文档编号:18763032
- 上传时间:2023-11-02
- 格式:PPT
- 页数:134
- 大小:935KB
吴文虎程序设计基础ppt第五讲.ppt
《吴文虎程序设计基础ppt第五讲.ppt》由会员分享,可在线阅读,更多相关《吴文虎程序设计基础ppt第五讲.ppt(134页珍藏版)》请在冰点文库上搜索。
1,声明:
本课件版权归清华大学计算机系语音技术中心所有未经许可不得扩散,2,“案情分析”程序讨论,2,3,/*/*程序:
6_aqfx2002_1.cpp(逻辑表达式)*/*作者:
wuwh*/*编制时间:
2002年10月10日*/*主要功能:
枚举法找出谁是罪犯*/*#includevoidmain(void)/案情分析/A和B至少有一人作案;cc1=(A|B)/A和D不可能是同案犯;cc2=!
(A/定义变量,3,4,intcc1,cc2,cc3,cc4,cc5,cc6;/定义6个变量,分别表示6句话intA,B,C,D,E,F;/定义6个变量,分别表示6个人charinfo29=不是罪犯,是罪犯;/定义二维数组,给出是否罪犯信息inti,j,w6;/定义变量,4,5,/A和B至少有一人作案;cc1=(A|B)/A和D不可能是同案犯;cc2=!
(A/cc6=D|(!
E)/编程找出犯罪嫌疑人,5,6,/枚举64种可能:
为0不是罪犯,为1是罪犯for(i=0;ij)/输出结束/循环结束/程序结束,6,7,for(i=0;ij),7,8,wj=(ij)&1wi000ABCDEFF0i1000ABCDEE1i20000ABCDD2i300000ABCC3i4000000ABB4i50000000AA5,8,9,cc1=A|B;/第1句话cc2=!
(A/第6句话if(cc1+cc2+cc3+cc4+cc5+cc6=6)/测试6句话都为真时,才输出谁是罪犯,9,10,/输出判断结果coutA:
infoAendl;coutB:
infoBendl;coutC:
infoCendl;coutD:
infoDendl;coutE:
infoEendl;coutF:
infoFendl;/输出结束/循环结束/程序结束,10,11,位运算按位“与”操作&向右位移1位操作1向右位移4位操作4,11,12,/*/*程序:
6_aqfx2002_2.cpp(逻辑表达式)*/*作者:
wuwh*/*编制时间:
2002年10月12日*/*主要功能:
枚举法找出谁是罪犯*/*#includevoidmain(void)/案情分析/A和B至少有一人作案;cc1=(A|B)/A和D不可能是同案犯;cc2=!
(D/定义变量,12,13,/枚举64种可能:
为0不是罪犯,为1是罪犯for(i=0;i5;/从i中经位操作分离出AB=(i,13,14,for(i=0;i5;/从i中分离出AB=(i/从i中分离出F,14,15,按位与运算n=63;s=32;ABCDEFA5=nn:
00111110&)s:
00100000A5:
00100000A=A5/32,15,16,按位与运算n=63;s=16;ABCDEFB4=nn:
00111110&)s:
00010000B4:
00010000B=B4/16,16,17,按位与运算n=63;s=8;ABCDEFC3=nn:
00111110&)s:
00001000C3:
00001000C=C3/8,17,18,按位与操作常用来分离出某一位或某几位,18,19,A=(n,19,20,假定n=3200100000n/2相当右移1位00010000n/4相当右移2位00001000n/8相当右移3位00000100n/16相当右移4位00000010n/32相当右移5位00000001,20,21,A=(n,21,22,二进制位运算位运算符操作&按位与|按位或按位异或按位取反右移左移,22,23,冒泡排序法,23,24,a183249下标123456希望排成a984321下标123456,24,25,冒泡排序法问题:
将几个数从大到小排序并输出,25,26,26,27,27,28,从表中可以看出最小的一个数第一遍扫描就交换到a6中。
如果将a1视为水底,a6视为水面:
最轻的(最小的)一个数1最先浮到水面,交换到a6;次轻的2第二遍扫描交换到a5;再轻的3第三遍扫描交换到a4;依此类推,有6个数,前5个数到位需5遍扫描,第6个最重的数自然落在a1中。
因此,6个数只需5遍扫描,即j=n-1,n=6。
冒泡排序算法分析:
28,29,再看在每遍扫描中,相邻两数组元素的比较次数。
当j=1时,i=1,2,n-j。
n=6时,比较5次之后a6中有一个最小数到达,这时a6不必再参与比较了。
因此在第二遍搜索时,j=2,i=1,2,n-j,即i=1,2,3,4。
比较4次之后次小的一个数到达了a5。
这时a5不必再参与比较了。
因此,j=3时,i=1,2,3;j=4时,i=1,2;j=5时,i=1。
理出上述规律后,程序就不难编了,29,30,为了表述方便,定义以下3个变量:
n待排序的数的个数,这里n=6j扫描遍数,j=1,2,n-1i第j遍扫描待比较元素的下标,i=1,2,n-j,冒泡排序算法设计:
30,31,采用两重计数型循环:
步骤1:
将待排序的数据放入数组中;步骤2:
置j为1;步骤3:
让i从1到n-j,比较ai与ai+1,如果ai=ai+1,位置不动;如果aiai+1,位置交换,步骤4:
让j=j+1;只要j!
=n返回步骤3,当j=n时执行步骤5步骤5:
输出排序结果,31,32,/*/*程序名:
5_4.cpp*/*作者:
wuwh*/*编制时间:
2002年9月22日*/*主要功能:
冒泡排序*/*#include/预编译命令#include/预编译命令voidmain()/主函数inti=0,j=0,p=0,a7;/整型变量memset(a,0,sizeof(a);/整型数组初始化for(i=1;iai;/用键盘输入整数赋给aifor(j=1;j=5;j+)/冒泡排序,外层循环for(i=1;i=6-j;i+)/内层循环if(aiai+1)/如果aiai+1p=ai;/让ai与ai+1交换ai=ai+1;ai+1=p;for(i=1;i=6;i+)/输出排序结果coutaiendl;/输出ai,32,33,/*/*程序名:
5_4.cpp*/*作者:
wuwh*/*编制时间:
2002年9月22日*/*主要功能:
冒泡排序*/*#include/预编译命令#include/预编译命令,33,34,intmain()inti=0,j=0,p=0,a7;memset(a,0,sizeof(a);for(i=1;iai;,34,35,for(j=1;j=5;j+)/外层循环for(i=1;i=6-j;i+)/内层循环Tif(aiai+1)Fp=ai;ai=ai+1;ai+1=p;,35,36,for(i=1;i=6;i+)/输出排序结果coutaiendl;,36,37,结构与结构数组,structstudent/名为student的结构类型charname20;/姓名charsex;/性别unsignedlongbirthday;/生日floatheight;/身高floatweight;/体重;,37,38,定义结构体类型格式struct结构体名类型名1成员名1;类型名2成员名2;.类型名n成员名n;;,38,39,/*/*程序名:
55.CPP*/*作者:
wuwh*/*编制时间:
2002年11月20日*/*主要功能:
学生个人信息*/*,39,40,#includestructstudent/名为student的结构类型charname20;/姓名charsex;/性别unsignedlongbirthday;/生日floatheight;/身高floatweight;/体重;,40,41,intmain()studentmy;/定义my为student类的结构cout“输入自己的数据”endl;/提示cout“姓名(汉语拼音)n”“性别:
M/Fn”“生日(年月日)n”“身高(m)n”“体重(kg)n”endl;,41,42,/依次输入个人信息cinmy.namemy.sexmy.birthdaymy.heightmy.weightendl;,42,43,/依次输出个人信息coutmy.nameendl;coutmy.sexendl;coutmy.birthdayendl;coutmy.heightendl;coutmy.weightendl;,43,44,定义类型不会分配内存空间Structstudent/此处为结构类型定义charname20;/姓名charsex;/性别unsignedlongbirthday;/生日floatheight;/身高floatweight;/体重;studentmy/结构变量my的定义系统会为my分配内存空间,44,45,变量my(my为变量的符号地址)my.namemy.sexmy.birthdaymy.heightmy.weight&my(变量的内存地址),45,46,点操作符用于对结构体变量的成员的引用如coutmy.name;读作“输出结构体my的name成员”这里“.”读作“的”,46,47,结构体变量的初始化定义和初始化同时完成
(1)structpersoncharname10;unsignedlongbirthday;charpiaceofbirth20;per=“Liming”,19821209,”Beijing”;,47,48,person是结构体类型per是结构体变量per.name=“Liming“;per.birthday=19821209;per.placeofbirth=“Beijing”;,48,49,分开完成
(2)structpersoncharname10;unsignedlongbirthday;charpiaceofbirth20;personper=“Liming”,19821209,”Beijing”,49,50,结构数组元素为结构的数组,50,51,studentRoom4=“Lili”,M,19840318,1.82f,65.0f,“Mimi”,M,19830918,1.75f,58.0f,“Helei”,M,19841209,1.83f,67.1f,“Geli”,M,19840101,1.70f,59.0f;,51,52,namenamenamenamesexsexsexsexbirthdaybirthdaybirthdaybirthdayheightheightheightheightweightweightweightweigh下标0下标1下标2下标3Room,52,53,Room0“Lili”,M,19840318,1.82f,65.0f,Room1“Mimi”,M,19830918,1.75f,58.0f,Room2“Helei”,M,19841209,1.83f,67.1f,Room3“Geli”,M,19840101,1.70f,59.0f,53,54,/*/*程序名:
56.CPP*/*作者:
wuwh*/*编制时间:
2002年11月21日*/*主要功能:
结构数组*/*,54,55,#includestructstudent/名为student的结构类型charname20;/姓名charsex;/性别unsignedlongbirthday;/生日floatheight;/身高floatweight;/体重;,55,56,studentRoom4=“Lixin”,M,19840318,1.82f,65.0f,“zhangmen”,M,19830918,1.75f,58.0f,“Helei”,M,19841209,1.83f,67.1f,“Geyujian”,M,19840101,1.70f,59.0f;,56,57,intmain()studentq;inti=0;intj=0;for(j=0;jTRoomi+1.birthday)Fq=Roomi;Roomi=Roomi+1;Roomi+1=q;,57,58,intmain()studentq;inti=0;intj=0;for(j=0;jTRoomi+1.birthday)Fq=Roomi;Roomi=Roomi+1;Roomi+1=q;,58,59,for(i=0;i4;i=i+1)coutRoomi.name“n”Roomi.sex“n”Roomi.birthday“n”Roomi.height“n”Roomi.weight“n”;,59,60,二维数组测量湖泊水深012345678x00012230001023553200201434221030011001104000000000y,60,61,Lake0001223000012345678第0行的数据构成一维数组Lake0共有5行数据构成5个一维数组Lake0,Lake1,Lake2,Lake3,Lake4,61,62,Lake0Lake00Lake01.Lake08Lake1Lake10Lake11.Lake18Lake2Lake20Lake21.Lake28Lake3Lake30Lake31.Lake38Lake4Lake40Lake41.Lake48下标018,62,63,把5个一维数组作为5个元素放到一个名为Lake的二维数组中,63,64,Lake0Lake00Lake01.Lake08Lake1Lake10Lake11.Lake18Lake2Lake20Lake21.Lake28Lake3Lake30Lake31.Lake38Lake4Lake40Lake41.Lake48下标018,64,65,Lake下标0Lake0Lake0下标1Lake1Lake1下标2Lake2Lake2下标3Lake3Lake3下标4Lake4Lake4,65,66,Lake0Lake00Lake01.Lake08Lake1Lake10Lake11.Lake18Lake2Lake20Lake21.Lake28Lake3Lake30Lake31.Lake38Lake4Lake40Lake41.Lake48018,66,67,012345678Lake0001223000Lake1023553200Lake2014342210Lake3001100110Lake4000000000,67,68,012345678Lake0001223000Lake1023553200Lake2014342210Lake3001100110Lake4000000000,68,69,二维数组的存储顺序Lake00Lake01Lake02.Lake10Lake11Lake12.Lake20Lake20Lake22.,69,70,Lake0001223000Lake1023553200Lake2014342210Lake3001100110Lake4000000000,70,71,二维数组的定义和初始化类型标示符数组名一维数组个数一维数组中的元素个数例:
intLake59,71,72,intLake59=0,0,1,2,2,3,0,0,0,0,2,3,5,5,3,2,0,0,0,1,4,3,4,2,2,1,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0;,72,73,自学内容读懂程序5_7.cpp和5_8.cpp(书中第5859页),73,74,小结,74,75,75,76,第六章函数递推递归,76,77,教学目标函数的概念,定义,调用,返回带自定义函数的程序设计递推算法递归思想及算法实现,77,78,递推是计算机数值计算中的一个重要算法,可以将复杂的运算化为若干重复的简单运算,充分发挥计算机长于重复处理的特点,现举一例,递推,78,79,【例6.1】A、B、C、D、E五人合伙夜间捕鱼,凌晨时都疲惫不堪,各自在河边的树丛中找地方睡着了,日上三竿,A第一个醒来,他将鱼平分作五份,把多余的一条扔回湖中,拿自己的一份回家去了,B第二个醒来,也将鱼平分为五份,扔掉多余的一条,只拿走自己的一份,接着C、D、E依次醒来,也都按同样的办法分鱼。
问五人至少合伙捕到多少条鱼?
每个人醒来后看到的鱼数是多少条?
79,80,解题思路:
假定A、B、C、D、E五人的编号分别为1、2、3、4、5,整数数组fishk表示第k个人所看到的鱼数。
fish1表示A所看到的鱼数,fish2表示B所看到的鱼数fish1为五人合伙捕鱼的总鱼数fish2=(fish1-1)*4/5fish3=(fish2-1)*4/5fish4=(fish3-1)*4/5fish5=(fish4-1)*4/5,80,81,写成一般式fishi=(fishi-11)*4/5i=2,3,5,这个公式可用于知A看到的鱼数去推算B看到的,再推算C看到的,.。
现在要求的是A看到的,能否倒过来,先知E看到的再反推D看到的,直到A看到的。
为此将上式改写为:
fishi-1=fishi*5/4+1i=5,4,2,81,82,分析上式.当i=5时,fish5表示E醒来所看到的鱼数,该数应满足被整除后余,即fish5%5=12.当i=5时,fishi-1表示D醒来所看到的鱼数,这个数既要满足fish4=fish5*5/4+1又要满足fish4%5=1显然,fish4不能不是整数,这个结论同样可以用至fish3,fish2和fish1,82,83,3.按题意要求5人合伙捕到的最少鱼数,可以从小往大枚举,可以先让E所看到的鱼数最少为6条,即fish5初始化为6来试,之后每次增加5再试,直至递推到fish1得整数且除以5之后的余数为1。
根据上述思路,我们可以构思如下的程序框图:
83,图6.1五人合伙捕鱼程序NS图,图6.1的说明:
该图可分为三部分
(1)是说明部分:
包含定义数组fish6,并初始化为1和定义循环控制变量i,并初始化为0。
(2)是do.while直到型循环,其循环体又含两块:
(2).1是枚举过程中的fish5的初值设置,一开始fish5=1+5;以后每次增5。
(2).2是一个for循环,i的初值为4,终值为1,步长为-1,该循环的循环体是一个分支语句,如果fishi+1不能被4整除,则跳出for循环(使用break语句;)否则,从fishi+1算出fishi。
86,当由break语句让程序退出循环时,意味着某人看到的鱼数不是整数,当然不是所求,必须令fish5加5后再试,即重新进入直到型循环dowhile的循环体。
当着正常退出for循环时,一定是控制变量i从初值4,一步一步执行到终值1,每一步的鱼数均为整数,最后i=0,表示计算完毕,且也达到了退出直到型循环的条件。
(3)输出计算结果,86,87,/*/*程序名:
6_1.cpp(五人合伙捕鱼)*/*作者:
wuwh*/*编制时间:
2002年10月2日*/*主要功能:
递推算法的实现*/*#include/预编译命令voidmain()/主函数intfish6=1,1,1,1,1,1;/整型数组,记录每人醒来后看到的鱼数inti=0;dofish5=fish5+5;/让E看到的鱼数增5。
for(i=4;i=1;i-)if(fishi+1%4!
=0)break;/跳出for循环elsefishi=fishi+1*5/4+1;/计算第i人看到的鱼数while(i=1);/当i=1继续做do循环/输出计算结果for(i=1;i=5;i+)coutfishiendl;,87,88,dofish5=fish5+5;for(i=4;i=1;i=i-1)if(fishi+1%4!
=0)break;/跳出for循环elsefishi=fishi+1*5/4+1;while(i=1);,88,89,fish5=fish5+5;for(i=4;i=1;i-)fishi+1%4!
=0tfbreak;fishi=1+fishi+1*5/4;dowhile(i=1),89,90,31212496199615961276,输出结果为:
90,91,为了讲递归,我们必须先将有关函数的基本概念介绍给大家。
递归,91,92,问题:
编程求解,现假定n=6,k=4思路:
1、该式可分解为2、定义一个函数让这个函数可以表示,函数,92,93,3、再定义一个函数让m=n,i=k,即可得解参考程序如下:
93,94,/*/*程序:
6_2.cpp*/*作者:
wuwh*/*编制时间:
2002年10月12日*/*主要功能:
求幂函数的和(介绍函数)*/*#include/预编译命令constintn=6;/定义常量n为6constintk=4;/定义常量k为4intSOP(intm,intl);/声明函数SOPintpower(intp,intq);/声明函数powervoidmain()/主函数/主函数开始coutSumofk/提示信息thpowersofintegersfrom1tonisSOP(n,k)/输出结果,其中SOP(n,k)为被调用函数endl;,94,95,/以下函数是被主程序调用的函数/功能:
计算1,2,.,m的l次幂的和intSOP(intm,intl)/整型自定义函数,m,l为形参/自定义函数体开始inti,sum;/定义整型变量i,sumsum=0;/初始化累加器for(i=1;i=m;i+)/计数循环isum=sum+power(i,l);/累加returnsum;/返回值sum给函数SOP(n,k)/自定义函数体结束/以下函数是被函数sop(n,k)调用的函数/功能:
计算p的q次幂intpower(intp,intq)/整型自定义函数/自定义函数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 吴文虎 程序设计 基础 ppt 第五