《三章结构化程序设计ppt课件.ppt》由会员分享,可在线阅读,更多相关《三章结构化程序设计ppt课件.ppt(55页珍藏版)》请在三一文库上搜索。
1、uangXi University,1,C/C+程序设计,胡立坤,uangXi University,2,第三章结构化程序设计与基本算法,3.1 算法及其表示 3.2 结构化程序设计 3.3 顺序结构 3.4 选择结构 3.5 循环结构 3.6 流程转移控制语句 3.7 应用举例,uangXi University,3,3.1 算法及其表示,N. Wirth提出:数据结构+算法=程序 算法:为解决一个具体问题而采取的确定的有限的操作步骤,这里仅指计算机能执行的算法 算法特性: 有穷性 确定性 有效性 没有输入或有多个输入 有一个或多个输出 算法分类: 数值算法:解决的是求数值解的问题,例如用辗
2、转相除法求两个数的最大公约数等。 非数值算法:主要用于解决需要用分析推理、逻辑推理才能解决的问题,例如人工智能中的许多问题,查找、分类等问题。,uangXi University,4,3.1 算法及其表示,算法的表示方式 自然语言 传统的流程图 N-S结构化流程图 伪代码,开始/准备,过程/处理,选择/决策,手动输入,文档,显示/输出,终止,离页连接,uangXi University,5,3.2 结构化程序设计,已经证明,任何程序均可只用顺序结构、选择结构、循环结构这三种结构综合描述。只用这三种结构编制的程序,叫结构化程序。程序应符合结构化规则。 采用顺序、选择和循环三种基本结构作为程序设计
3、的基本单元 只有一个入口; 只有一个出口; 无死语句,即不存在永远都执行不到的语句; 无死循环,即不存在永远都执行不完的循环,但也有例外。 采用“自顶向下、逐步求精”和模块化的方法进行结构化程序设计,E. W. Dijkstra,生于1930年,卒于2002年8月6日,uangXi University,6,3.2 结构化程序设计流程表示,B,A,B,A,条 件P,顺序结构,选择结构,uangXi University,7,3.2 结构化程序设计流程表示,条 件P,A,真,假,假,条 件P,A,假,真,当型循环,直到型循环,uangXi University,8,3.3 顺序结构,顺序结构:按
4、照语句出现的先后顺序依次执行。 一般: 表达式; 例如: i+; sum=a+b; coutabendl; 特例: ;(空语句) 作用: 当程序中某个位置在语法上需要一条语句,而在语义上又不 要求执行任何动作时,可放上一条空语句。一般适用于在循环语句中做空循环体: for (m = 0; m1000; m+) ;,uangXi University,9,3.3 顺序结构,复合语句: 变量定义 语句组 作用:当程序中某个位置在语法上只允许一条语句,而在语义上要执行多条语句才能完成某个操作时,需要使用复合语句。 变量仅在定义它的复合语句内有效 一般适用于选择、循环语句中的内嵌语句。也有时为了清晰,
5、特意将某段程序中括起来。,uangXi University,10,3.4 选择结构,选择结构:根据条件的值来判断程序的流向。C/C+中,提供两类选择控制语句: if语句,实现n分支,要求n个表达式; switch语句,实现多分支;只用1个表达式。,uangXi University,11,3.4 选择结构,3.2.1 if 语句 if语句的三种形式: 形式1: if (表达式) 语句 作用:当表达式为真(非0)时,执行表达式后面的语句, 否则绕过该语句,而执行其后面的语句。 例3.1已知两个数x和y,比较它们的大小,使得x大于y。 思考:如何将一瓶油与一瓶酒互相换瓶? 需借助于一个空瓶子内存
6、中的两个单元也可以看成放着一瓶油与一瓶酒,要交换其中放的内容,同样需借助于一个空的内存单元。这是由内存”取之不尽,一冲就走”的物点决定的。,uangXi University,12,3.4 选择结构,于是,有,if(xy) t=x; x=y; y=t; coutxy;,#include “iostream.h“ void main() int x,y,t; coutxy; if (x“yendl; ,完整的程序如右:,uangXi University,13,3.4 选择结构,形式2: if (表达式) 语句1 else 语句2 作用:当表达式为真时,执行语句1,否则执行语句2。 例3.2计算
7、分段函数:,uangXi University,14,3.4 选择结构,实现此题可采用双分支结构,也可采用单分支结构。,if (x) y=sin(x)+sqrt(x*x+1); else y=cos(x)x*x+3*x;,y=cos(x)x*x+3*x; if (x) y=sin(x)+sqrt(x*x+1);,思考:若将右边的两个语句上下交换一下,还能实现上例的要求吗? 不能,uangXi University,15,3.4 选择结构,形式3: if (表达式1) 语句1 else if (表达式2) 语句2 else if (表达式n) 语句n else 语句n+1 作用:当表达式1的值为
8、true时,执行语句1;否则判断当表达式2的值为true时执行语句2;依此类推,若表达式的值都为false,则执行语句n+1。,uangXi University,16,3.4 选择结构,例3.3已知成绩mark,要求显示对应五级制的评定,评定条件:,if (mark = 90) cout “优“; else if (80 = mark ,if (mark = 60) cout= 70) cout= 80) cout=90) cout “优“; else cout “不及格“;,注意: 不管有几个分支,程序执行一个分支后,其余分支不再执行。 else if不能写成elseif。 当多分支中有多
9、个表达式同时满足,则只执行第一个与之匹配的语句。,uangXi University,17,3.4 选择结构,if语句的嵌套形式 if语句的嵌套是指if或else后面的语句本身又是一个if语句。 如: if(表达式1) if(表达式11) 语句11 else 语句12 else 语句2,if (表达式1) if (表达式2) 语句1 else 语句2,如何使之与第一个if配对?,注意: 为了增强程序的可读性,建议采用锯齿型的书写形式。 else始终与它上面的最近的if语句配对,而这个if语句又没有 其它的else与之匹配 。,uangXi University,18,3.4 选择结构,例3.4
10、已知x,y,z三个数,使得xyz。可用一个IF语句和一个嵌套的IF语句实现。,if (xy) t=x ; x=y ; y=t; if (yz) t=y ; y=z ; z=t ; if (xy) t=x ; x=y ; y=t ; ,uangXi University,19,3.4 选择结构,现场编程:体型判断。按“体指数”对肥胖程度进行划分,体指数t = 体重w / (身高h)2 (w 单位为公斤,h单位为米) 当t = 27时,为肥胖。 编程从键盘输入你的身高h和体重w,根据给定公式计算体指数t,然后判断你的体重属于何种类型。 提示:可用3种方法编程中的一种 算法1:用不带else子句的i
11、f语句编程 算法2:用在if子句中嵌入if 语句的形式编程 算法3:用在else子句中嵌入if 语句的形式编程 (10分钟,请自告奋勇),uangXi University,20,3.4 选择结构,3.2.2 switch语句 形式: switch(表达式) case 常量表达式1:语句组1; break; case 常量表达式2:语句组2; break; case 常量表达式n:语句组n; break; default: 语句组n+1 ,执行顺序:当表达式的值与某个常量表达式的值相等时,则执行该常量表达式后面相应的语句,若使用了break, 则执行完该语句后便退出switch语句;否则,还要
12、依次执行其后面的各条语句。若找不到相匹配的常量表达式,则执行default后面的语句。,必须为整型或字符型,uangXi University,21,3.4 选择结构,现场编程:设计一个简单的计算器程序,要求根据用户从键盘输入的表达式: 操作数1 运算符op 操作数2 然后,计算表达式的值,指定的运算符为加(+)、减(-)、乘(*)、除(/) 提示:用switch语句。,uangXi University,22,3.4 选择结构,2a+1 (1=a2) 【例3.5】用switch结构求分段函数b= a2-3 (2=a4) a 其它,正确: switch(int)a) case 1: b=2*a
13、+1;break; case 2: case 3: b=a*a-3;break; default: b=a; ,错误: switch(int)a) case a=1 ,共用同一个语句组,思考:若省去break语句,情况会怎样?,uangXi University,23,3.5 循环结构,C语言提供了三种循环语句,流程图如下: while do-while for,while (表达式) 语句,do 语句 while (表达式);,for(表达式1;表达式2;表达式3) 语句,uangXi University,24,3.5 循环结构,例3.6/3.8用上述三种循环语句求,while语句:,n
14、= 1;s = 0; while (n=100) s=s+n; n=n+1; ,n = 1; s = 0; do s = s+n; n = n+1; while(n=100);,do-while语句:,for (n = 1,s = 0;n=100;n+) s=s+n;,for语句:,uangXi University,25,3.5 循环结构,例3.7求下列级数的前m项和,要求其误差小于0.00001,分析: 级数的通项为 xm/m!, 第i项ti与第i-1项 ti-1之间存在如下关系: ti=t i-1*x/i,int i(1);float t(1),e(0); while(t1e-5) e+
15、=t; t/=i; i+;,int i(1);float t(1),e(0); for( ;t1e-5; ) e+=t; t/=i; i+;,for(i=1,t=1,e=0;t1e-5; e+=t, t/=i,i+);,分号不能省略,空语句,uangXi University,26,3.5 循环结构,例3.9将可打印的ASCII码制成表格输出,使每个字符与它的编码对应起来,每行打印7个字符。 看程序,思考:你认为完成该例,关键在什么地方?,for通常有一个循环变量控制循环的次数,不要在循环体内改变这个变量,uangXi University,27,3.5 循环结构,现场编程-猜数游戏:先由计算
16、机“想”一个数请人猜,如果人猜对了,则计算机给出提示:“Right!”, 否则提示:“Wrong!”,并告诉人所猜的数是大还是小。 现场编程-先由计算机“想”一个1到100之间的数请人猜,如果人猜对了,则结束游戏,否则计算机给出提示,告诉人所猜的数是太大还是太小,直到人猜对为止。计算机记录人猜的次数,以此来反映猜数者“猜”的水平。,uangXi University,28,3.5 循环结构,猜数游戏用到的库函数 随机函数rand() #include 产生0,32767 之间随机数 .,随机函数srand 为函数rand()设置随机数种子实现对函数rand所产生的伪随机数的 “随机化” ,使用
17、计算机读取其时钟值并把该值自动设置为随机数种子,产生0,100之间的随机数 C中函数time()返回以秒计算的当前时间值,该值被转换为无符号整数并用作随机数发生器的种子 #include srand(time(NULL); magic = rand() % 101 + 0;,uangXi University,29,3.5 循环结构,#include “iostream.h“ #include “stdlib.h“ void main() int i,a; for(i=0;i10;i+) a=rand()%101; couta ; ,问题:每一次运行程序,所得到的随机数序列都一样吗?,一样,这
18、是因为初始种子是默认的,要改变必须使每次运行的初始种子不一样,这就要用到srand函数了,想一想如何修改程序?,uangXi University,30,3.5 循环结构,循环的嵌套:循环体内包含另一个完整的循环结构。三种循环语句皆可以相互嵌套 。,例3.10打印九九乘法表,uangXi University,31,3.5 循环结构,#include “iostream.h“ void main() cout“t 九九乘法表“endl; cout“t -“endl; for(int i=1;i=9;i+) for(int j=1;j=9;j+) couti“j“=“i*jt; coutendl
19、; ,程序:,思考:打印上三角或下三角程序如何改动?,uangXi University,32,3.5 循环结构,#include “iostream.h“ void main() cout“t 九九乘法表“endl; cout“t -“endl; for(int i=1;i=9;i+) for (int k=1;k=i-1;k+) coutt; for(int j=i;j=9;j+) couti“j“=“i*jt; coutendl; ,#include “iostream.h“ void main() cout“t 九九乘法表“endl; cout“t -“endl; for(int i=
20、1;i=9;i+) for(int j=1;j=i;j+) couti“j“=“i*jt; coutendl; ,打印下三角的程序,打印上三角的程序,uangXi University,33,3.5 循环结构,使用嵌套的循环体时,应注意以下问题: 在嵌套的各层循环体中,使用复合语句(即用一对大花括号将循环体语句括起来)保证逻辑上的正确性 内层和外层循环控制变量不应同名,以免造成混乱 嵌套的循环最好采用右缩进格式书写,以保证层次的清晰性 循环嵌套不能交叉,即在一个循环体内必须完整的包含着另一个循环,合法的嵌套循环,uangXi University,34,3.5 循环结构,现场编程:国王的许诺。
21、 相传国际象棋是古印度舍罕王的宰相达依尔发明的。舍罕王十分喜欢象棋,决定让宰相自己选择何种赏赐。这位聪明的宰相指着88共64格的象棋盘说:陛下,请您赏给我一些麦子吧,就在棋盘的第一个格子中放1粒,第2格中放2粒,第3格放4粒,以后每一格都比前一格增加一倍,依此放完棋盘上的64个格子,我就感恩不尽了。舍罕王让人扛来一袋麦子,他要兑现他的许诺。 国王能兑现他的许诺吗?试编程计算舍罕王共要多少麦子赏赐他的宰相,这些麦子合多少立方米? (已知1立方米麦子约1.42e8粒) 总粒数为:sum=1+2+22+23+263,uangXi University,35,3.5 循环结构,死循环 永远不会退出的循
22、环为死循环 for (;) while (1) do while (1) 一般情况下,要极力避免死循环 绝大多数程序不需要死循环。如果出现,往往都是bug 时间过长的循环会造成“假死”效果,也要考虑解决,uangXi University,36,3.5 循环结构,选择三种循环的一般原则: 如果循环次数已知,用for 如果循环次数未知,用while 如果循环体至少要执行一次,用do-while 这只是“一般”原则,不是“原则”,uangXi University,37,3.6 流程转移控制语句break&continue,Break在switch语句中出现过,保证多分支情况的正确执行; brea
23、k和continue还对for、while、do-while循环进行内部手术: break,退出循环 continue,中断此次循环体的执行,开始下一次 少用为妙,uangXi University,38,3.6 流程转移控制语句break&continue,分析下面两段代码如何执行的。,for(m=20;m0;m-) if(m % 6=0) break; coutm“ “; ,for(m=20;m0;m-) if(m % 6=0) continue; coutm“ “; ,uangXi University,39,3.6 流程转移控制语句goto,goto与标号 标号举例 error: go
24、to举例 goto error; 一般形式 goto 语句标号; 语句标号: 或 语句标号: goto 语句标号;,糟糕的goto: START_LOOP: if (fStatusOk) if (fDataAvaiable) i = 10; goto MID_LOOP; else goto END_LOOP; else for (i = 0; i 100; i+) MID_LOOP: / lots of code here goto START_LOOP; END_LOOP:,Dijkstra早在1968年就指出: “Goto considered harmful” , “I became c
25、onvinced that the go to statement should be abolished from all “higher level“ programming languages.” “The go to statement is too much an invitation to make a mess of ones program. ” 现代观点认为:混乱根源不在goto,而在标号;任何程序都可以不用goto就实现其功能;但在某些情况下,使用goto可以让程序更清晰 使用原则: 使用之后,程序仍然是单入口,单出口 不要使用一个以上的标号 不要用goto往回跳,要向下跳
26、 不要让goto制造出永远不会被执行的代码,uangXi University,40,3.6 流程转移控制语句,exit(0)作用是终止整个程序的执行,强制返回操作系统 ,调用该函数需要嵌入头文件stdlib.h。 此函数为出现异常,结束整个程序的运行提供了支持。 例3.11分别用if 和goto、for语句实现求和。 记住要写上标号。,uangXi University,41,3.7 应用举例,1. 求最大值(或最小值) 例3.12从键盘输入一组数,求这组数中的最大值。,cinm; max=m; /第一个数假设为最大数 while (cinm,m!=0) if (mmax) max=m;,m
27、ax=0; /设一个较小的数为最大值的初值 for(int i=0;im; if (mmax) max=m; ,以输入0作为结束,输入数的个数未知,输入数的个数已知,uangXi University,42,3.7 应用举例,2求最大公约数 例3.13输入两自然数m、n,求最大公约数。 方法1:欧几里德的辗转相除法 (1)对于已知两数m、n,使mn; (2)m除以n得余数r; (3)若r=0,则n为最大公约数,算法结束;否则继续进行下一步; (4)则令nm, rn,转第2步继续相除得新的r。 方法2:辗转相减法 先用两个数相减,判别差是否为0,用小数和差组成新的数对再相减,直到差为0时为止。最
28、后那一组相同的数对即为最大公约数。,uangXi University,43,#include “iostream.h“ void main( ) int m, n, t, r; coutmn; if(mn) t=m; m=n; n=t; while (r=m % n)!=0) m=n; n=r; cout“最大公约数为 “mendl; /退出循环时m为最大公约数 ,3.7 应用举例,#include “iostream.h“ void main( ) int m, n; coutmn; while (m - n!=0) if(mn) m - = n; else n - = m; cout“最
29、大公约数为 “mendl; /退出循环时m为最大公约数 ,方法1,方法2,不要这句行吗?,uangXi University,44,3.7 应用举例,3求素数 例3.14求2100之间的素数。 素数(质数)-就是除1和它本身以外设有其他的约数的整数。 判别某数为质数的最简单方法就是用j=2,3,m-1逐个判别m能否被j整除,若都不能被整除,m是素数。 另一种判别方法是用j=2,3,sqrt(m)逐个判别m能否被j整除,若都不能被整除,m是素数。 显然,第一种方法比第二种循环要多一些。,uangXi University,45,3.7 应用举例,#include “iostream.h“ voi
30、d main() int m,i,countm(0); bool tag; for(m = 2;m=100;m+) tag=false; /tag初值为false for(i = 2;i=m-1;i+) if (m % i = 0) tag=true; /m被整除,设置为true / 出了内循环,tag的值若为false,说明m没有被i整除过m是素数 if (tag=false) /等价于 if (!tag) coutmt; countm+; if (countm % 8 =0) coutendl; ,第一种方法,uangXi University,46,3.7 应用举例,#include #
31、include void main() int m, i, k; printf(“Please enter a number:“); scanf(“%d“, ,进一步,输入一个数,判断其是否是素数。,uangXi University,47,3.7 应用举例,4穷举法-测试所有的情况 例3.15a马克思手稿中有一道趣味数学题:有30个人,其中有男人、女人和小孩,在一家饭馆里吃饭共花了50先令,每个男人各花3先令,每个女人各花2先令,每个小孩各花1先令,问男人、女人和小孩各有几人?,对这种不定方程组,可采用穷举法。,提示,本题就是解方程组,uangXi University,48,3.7 应用举
32、例,#include main() int x,y,z; printf(“Man t Women t Childernn“); for (x=0; x=30; x+) for (y=0; y=30; y+) for (z=0; z=30; z+) if (x+y+z=30 ,三重循环穷举,uangXi University,49,3.7 应用举例,#include main() int x,y,z; printf(“Man t Women t Childernn“); for (x=0; x=16; x+) for (y=0; y=25; y+) z = 30 x - y; if (3 * x
33、 + 2 * y + z = 50) printf(“%3d t %5d t %8dn“,x,y,z); ,二重循环穷举,uangXi University,50,3.7 应用举例,5.递推法 “递推法”也称为 “迭代法”,其基本思想是把一个复杂的计算过程转化为简单过程的多次重复,每次重复都从旧值的基础上递推出新值,并由新值代替旧值。,例3.16利用牛顿迭代法求方程 在x0附近的根的近似值。,牛顿迭代公式为: 输入x0值,由公式求出x1,再由x1从公式求出x2,直到 时可视x n+1为方程f(x)=0在X0附近的一个近似根 ,设为10-5 。,uangXi University,51,3.7
34、应用举例,#include “iostream.h“ #include “math.h“ void main( ) double x0,x1; x1=1; do x0=x1; x1=x0 - (3*x0*x0*x0-4*x0*x0-5*x0+13)/(9*x0*x0-8*x0-5); while(fabs(x1-x0)1e-5); cout“方程的根是 “x1endl; ,思考: 若迭代最高次数M后,即使达不到精度也要输出结果, 程序该如何修改?,i+; if (i=M) break;,int M,i=0;,(见上),uangXi University,52,3.7 应用举例,6分类统计 例3
35、.17从键盘输入一串字符,以ctrl+z(z)表示输入结束。统计其中包含的单词的个数、字母个数、数字个数。规定单词用一个空白符分开(空白符包括空格符、水平制表符、换行符)。 空白符隔开单词,所以统计空白符就可以统计单词个数。 想想:读入这串字符,能用标准输入流吗?为何?,uangXi University,53,3.7 应用举例,#include “iostream.h“ #include “stdio.h“ void main( ) char c; int alpha(0), num(0),ch(0),word(0); while(c=getchar( )!=EOF) / EOF代表文本结束符,键盘上对应输入CTRL+Z if(c= |c=t|c=n) word+; if(c=a ,uangXi University,54,Dijkstra说过的话,编程的艺术就是处理复杂性的艺术 优秀的程序员很清楚自己的能力是有限的,所以他对待编程任务的态度是完全谦卑的,特别是,他们会象逃避瘟疫那样逃避 “聪明的技巧”。1972年图灵奖演讲 简单是可靠的先决条件 我们所使用的工具深刻地影响我们的思考习惯,从而也影响了我们的思考能力,uangXi University,55,小结,回忆一下,本章你学习了些什么? 回忆一下,本章你学习了些什么? 回忆一下,本章你学习了些什么?,
链接地址:https://www.31doc.com/p-2626673.html