Chap3程序的流程控制.ppt

Chap 3 程序的流程控制,主要内容,语句概述 表达式语句 复合语句 选择语句(选择结构) 循环语句(循环结构) 转移语句 空语句 程序设计风格 常用算法设计,语句概述,表达式构成了数据处理的基本单位。 当程序中有多个表达式时，面临的问题： 先计算哪一个表达式? 根据不同的情况,如何选择计算不同的表达式? 一个或几个表达式需要重复计算多次时,如何进行? 解决方法 用不同的语句解决上述问题, 实现对程序执行流程的控制 程序的流程 指程序语句的执行顺序。,C+语句分类,表达式语句,表达式语句 在C+表达式的后面加上一个分号“;”. 格式：; 例如： a + b * c; a b ? a: b; a+; x = a | b C+中,把数据定义也看成语句.,较常使用的表达式语句,赋值 自增/自减 输入/输出 无返回值的函数调用，等 例如 x = a+b; /赋值 x+; /自增 f(a); /函数调用 cin a; /输入 cout 例3.2 等差级数求和，同学自己看,复合语句,定义 由一对花括号括起来的一条或多条语句 又称为分程序（block） 格式为： 中的语句可以是任何的C+语句，包括数据定义语句。 复合语句一般作为函数体和结构语句的成分语句。 语法上，复合语句可看作是一个语句。,复合语句举例, int a,b； cin a b; int max; if (a = b) /选择语句 max = a; else max = b; cout max endl; ,三种基本结构,一般地 任何复杂的程序段可有三种基本结构组成: 顺序结构 选择分支结构 循环结构,顺序结构,语句按照书写的顺序执行 例 二个例 例3.1 P42 例3.2 P43 等差级数求和,（顺序结构）,选择分支结构,程序设计中采用分支选择结构 当一个问题有不同的处理方式或多个解时。 选择的条件是逻辑值 关系表达式 逻辑表达式,（选择结构）,选择结构的不同形式,3. switch 语句 switch(E) case e1: s1 case e2: s2 case en : sn default: s /可缺省 ,1ifelse 结构 if (E1) s1 else S2,2. else if 结构 （多重选择） if (E1) s1 else if (E2) s2 else if (E3) s3 else if (En) Sn else S,ifelse 结构,格式 (两种): if (E1) S if (E1) S1 else S2 例 P45 3-3 说明： 1）当E1的值为真时，执行语句s1；值为假时，执行语句s2。 2）s1、s2可以是复合语句。 3）选择结构可以嵌套，但要注意if 与else的配对关系。最好用括号强制配对。 else 与其前面的离它最近的未配对的if 配对。 例3.4 注意：浮点数不能作等于零的判断 INT_MAX, SHRT_MAX, INT_MIN DBL_EPSILON,FLT_EPSILON,if结构的流程图,第一种格式,第二种格式,例 P45,/从键盘输入三个整数，计算其中的最大值并将其输出 #include using namespace std; int main() int a,b,c,max; cout a b c; if (ab) max=a; else max=b; if (c max) max = c; cout “最大者为：“ max endl; return 0; ,if 语句的歧义问题,下面的if语句的含义是什么？ if () if () else if () if () else if () if () else C+规定： else子句与前面最近的、没有else子句的if配对。 上面的if语句解释为： if () if () else P48 输出结果是什么?,else if 结构（多重选择）,if (E1) s1 else if (E2) s2 else if (E3) s3 else if (En) Sn else Sm 流程图 例 P46 例 3.5 (同学自己看, 作业) 例 3.6 P47 比较二个时间,若要按2解释，则需要加上一对花括号： if () if () else 程序的效率 (P48),switch 语句,对嵌套的if 结构改进，以增强程序的可读性。 switch语句格式 (又称开关语句)（P50） switch(E) case e1: s1 case e2: s2 case en : sn default: s /可缺省 流程图 例 3.7 ,3.8 P49(输出对应星期的英文单词),switch 例子,从键盘输入一个星期的某一天，然后输出其对应的英语单词 （0：星期天；1：星期一；.） / P49,50 #include using namespace std; void main(void) int day; cin day; switch (day) case 0: cout “Sunday“; break; case 1: cout “Monday“; break; case 2: cout “Tuesday“; break; case 3: cout “Wednesday“; break; case 4: cout “Thursday“; break; case 5: cout “Friday“; break; case 6: cout “Saturday“; break; default: cout “Input error“; cout endl; ,注意,1）switch 后的表达式可以为任意类型 一般为 integral types ,如: int, char,枚举类型. 2）case 后跟常量表达式，不可以为赋值后的变量或关系表达式。 （必要时，进行转换，例segmentFunction.cpp） 3）case 仅提供一个入口。 要退出switch结构，需要用break 语句。 4）case的各种情形和default的次序可以任意 5) C+中的switch语句具有灵活性 当若干个分支具有部分重复功能时，C+的switch语句可以节省代码量 ( 例3.9 P50),分段函数x:(0,1:0; x:(1,2:2; x:(2,3:2.5;,coutx; switch(int)ceil(x) case 1: y=0; cout“x=“x“t y=“yendl; break; case 2: y=2; cout“x=“x“t y=“yendl; break; case 3: y=2.5; cout“x=“x“t y=“yendl; break; default: printf(“No definitionn“); ,break语句,break语句用于控制程序流程 一般用在switch语句中跳过余下的情形； 或用于循环结构中提前退出循环。 语句格式： （P43） break;,Cingrade; While（grade!=#） switch(grade) case a: case A: aCount +; break; case b: case B: bCount+; break; case c: case C: cCount+; break; case d: case D: dCount+; break; case f: case F: fCount+; break; casen: case : break; /getchar read n as a character default: coutgrade; ,分支结构的测试,要说明程序的正确性有二种方法： 1）证明 2）以实例测试 测试是在编译、链接没有错误后进行的。 测试的目的: 找出程序中的逻辑错误（语义错误）（非语法错误，）。 测试数据要进行精心设计，以便提高程序测试的有效性。,测试,测试数据要包括：输入数据和程序执行后的预期结果数据，以便观察程序是否出错。 程序测试是程序开发的重要组成部分，所花费的代价并不小于程序设计。 测试方法： 1.结构测试，（白箱法） 基于程序的内部语句的逻辑结构的测试。 尽可能地使程序中的每条语句被执行过。 2.功能测试，（黑箱法） 根据用户提出的功能要求进行测试 测试者不知道程序结构。,几个结构测试方法,语句覆盖法 分支覆盖法， 又称为判定覆盖 条件覆盖 组合条件覆盖 Dijkstra:“程序测试只能证明错误的存在，而不能证明错误不存在” 除很小的程序外，再多的测试也不能保证程序的正确性。 注重测试方法和技术，提高测试的效率，尽可能多地测试出程序中的错误。 例 P45 找出3个数中的最大数（使用4组测试例）,循环结构,重复的例 二种重复的机制: 循环 (迭代) 递归 (第四章) 循环分二类： 1）记数器控制的循环。 2）标记值控制的循环,记数器控制的循环,执行循环前可以确定循环的次数定数循环 （definite repetition）。 例： 1. 1+2+3+100 2. 求全班学生的平均成绩(学生人数确定) 用记数器作为循环控制变量，循环控制变量的值在每次循环中要改变。,标记值控制的循环,执行循环前不能确定循环的次数不定数循环 （infinite repetition）。 如 1. sum = 1+2+3+n, 使sum不超过32767 。（n?） 2. 求一组数的平均值(数的个数不确定),循环的组成,四部分 循环初始化 循环条件 循环体 下一次循环的准备工作,三种循环语句,在C+中，可用三种循环语句实现循环： 1. for循环 2. while循环 3. do/while循环,（while循环）,for 循环 (P53),1. 语句格式： for(E1;E2;E3) S/循环体 多用于定数循环, 也能用于标记值控制的循环 2. 流程图：,#include /P56 using namespace std; void main(void) int n,i,f; cin n; for (i=2,f=1; /循环初始化 i=n; /循环条件 i+) /下一次循环准备 f *= i; /循环体 cout“factorial of “ n “ = “ f endl; ,用for语句求n!,注意:n!增长很快,注意数据类型,注意,E2的类型可以任意，其值非零时循环继续。 注意避免无限循环（死循环） 当E2省略时，成为永真循环。,常用的for语句格式,for(循环变量置初值；循环条件；改变循环变量的值) /循环体语句 例 sum=0; for (I=1; I=10; I+) sum+=I*I; ,void main(void) int i; int sum=0; for (i=1;i=100; i+ ) sum+=i; coutsumendl; ,常用的for语句格式 - 例（续）,prod=1; n=50； for(j=1; j=n; j+=2) prod*=j; ,for(sum=0,I=1;sum=32767;I+) sum+=I; ,for语句的一些变形,E1，E2，E3都可以省略，但“；”不能省。 P54 求n! n=100; I=2,f=1; for(;I=n;) f*=I; I+; ,while 循环,1语句格式： while (E) /循环体 2流程图： 3.注意： 当E的值非零时，执行循环体。 当E的值为零时，退出循环体。 如果条件开始就不成立，循环体一次也不执行。,用while语句求n!,#include using namespace std; void main(void) int n; cin n; int i=2,f=1; /循环初始化 while (i = n) /循环条件 f *= i; i+; /下一次循环准备 cout “factorial of “ n “ = “ f endl; ,例 1+2+100,void main(void) int i=1; int sum=0; while(i=100) sum+=i; i+; coutsumendl; ,例P55, 3-14,do/while 循环,1语句格式： do s/循环体语句 while(E); 2 流程图： 3. 注意： 当E的值非零时，循环继续。 当E的值为零时，退出循环体。,用do-while语句求n!,#include using namespace std; void main(void) int n; cin n; int i=1,f=1; /循环初始化 do f *= i; i+; /下一次循环的准备 while (i = n); /循环条件 cout “factorial of “ n “ = “ f endl; ,例 1+2+100,void main(void) int i=1; int sum=0; do sum+=i; i+; while(i=100); coutsumendl; ,例56，3-15,While 循环与do/while循环比较,当条件一开始成立时，二者相同； 当条件一开始不成立时，二者不同。 例 （WhileDifDow.cpp， do.prj),结果相同,int i=1; int sum=0; /sum=1+2+3+.+9 while(i10) sum+=i; i+; cout“n Use WHILE :sum=“sumendl; i=1;sum=0; do sum+=i; i+; while(i10); cout“n Use DO(WHILE) :sum=“ sumendl;,结果不同,i=20;sum=0; while(i10) sum+=i; i+; cout“n Use WHILE :sum=“sumendl; i=20;sum=0; do sum+=i; i+; while(i10); cout“n Use DO(WHILE) :sum=“sumendl;,for 语句与while 语句互相转换,例 奇数之和不超过给定数 （1+3+5+nTOTAL） N=?,奇数之和不超过给定数,i=BEGIN; sum=0; while(sumTOTAL, sum - (i-2) cout“nUse WHILE repeat: n=“ i-4t“sum=“sum-(i-2)endl;,例P56, 3-16判断一个正整数是否为素数 效率较低,continue语句,continue语句用于循环语句中，用来跳过循环体中剩余的语句，提前进入下一轮循环。 语句格式： continue; 例如: for (i=1;i=5 P64 例22 如果输入的是正数,则求其平方根,break语句在循环体中,break语句用于循环体中，提前结束（退出）本层循环，不再判断循环结束条件。,for (i=1;i=10;i+) if(i=5) break; couti“t“; ,i=BEGIN; sum=0; while(1) sum+=i; if(sumTOTAL) break; i+=2; ,循环嵌套,一个循环体中的语句也可以是循环语句，称为嵌套的循环语句。 循环嵌套的层次可以任意。（一般不超过三重（层）循环）。 注意： 1）循环嵌套必须完全嵌套，不可骑跨。 2）循环控制变量不可混淆。 (forfor.cpp),例,for(int i=0;i10;i+) int j=0; while(j10) couti*10+jt; j+; /* for( j=0;j10-i;j+) couti*10+jt; */ cout“n“; ,三种循环语句的使用原则,一般记数循环用for循环语句 标记值控制的循环 使用 while或do-while循环语句 至少执行一次用 do-while循环语句 三种循环语句可以互相转换,使用循环的例,P55求一组整数的和：例 3.13 ，3.14 对输入数据合法性的判断 ：P56例3.15 直到输入”合法”的数据 三角形的三条边（a0,b0,c0) sqrt(x), 要求 x=0 判断一个数是否为素数：P56 例3.16 循环结束的条件是什么?,double a,b,c; do cout0,b0,c0“abc; while(a=0|b=0|c=0);,使用循环的例(续),P57 例3.17第n个Fibonacci数 P58 例3.18 牛顿迭代公式 （输入0时不能得到正确的结果） 例3.19 求素数: 减少循环次数。 算法的优化,提高程序的效率 避免在循环中重复计算不变的表达式 例3.20 求级数的前n项之和(P60) 以空间换时间 效率提高,但精度损失 （累积误差）,0,1,1,2,3,5,8,13,. #include / P67 例3.17 using namespace std; void main(void) int n; cin n; int fib1=0; /用于记住前一个Fibonacci数 int fib2=1; /用于记住新的Fibonacci数 for (int i=3; i=n; i+) int temp=fib1+fib2; /计算新的Fibonacci数 fib1 = fib2; /记住前一个Fibonacci数 fib2 = temp; /记住新的Fibonacci数 cout “第“ n “个费波那契数是：“ fib2 endl; 另一种方法:(以时间换空间 ) Fib_2=fib_1 + fib_2; fib_1= fib_2 fib_1,例：求第n个费波那契(Fibonacci)数,#include #include using namespace std; int main() int n; cin n; /从键盘输入一个数 if (n sqrt(i) /i是素数 count+; cout i “,“; cout endl; return 0; , int j = 2, k=sqrt(i) ; while ( j k) /i是素数。 ,循环结构的测试,循环结构可以看成是一种特殊的判定结构。 1单循环测试 测试包括下列情形： 1） 0次循环测试，不执行循环的情况； 2） 一次循环测试，测试初始化是否有问题； 3） 二次循环测试，测试循环变量控制问题 2嵌套循环测试 1）对全部各层循环同时取最小循环次数； 2）对全部各层循环同时取最大循环次数；( 多一次或少一次) 3）取指定层的循环，遍历单循环的全部情况，其他各层循环均取最大循环次数；再将各层作为指定层,goto语句,goto语句的格式如下： goto ； 为标识符，其定义格式为： ： 在使用goto语句时，应该注意： 不能用goto语句从一个函数外部转入该函数的内部（函数体），也不能用goto语句从一个函数的内部转到该函数的外部。 C+允许用goto语句从内层复合语句转到外层复合语句或从外层复合语句转入内层复合语句,但是，goto语句不能掠过带有初始化的变量定义。,关于goto语句,goto语句会使得程序的静态结构和动态结构不一致，导致程序难以理解、可靠性下降和不容易维护。 从结构化程序设计的角度讲， goto语句会破坏程序中的每一个结构所具有的单入口/单出口的性质。 实际上，goto语句的使用可以分成两类： 向前的转移（forward）（可用分支结构实现） 往回的转移（backward）（可用循环结构实现）,用goto语句求n!,#include using namespace std; void main(void) int n; cin n; int i=1,f=1; loop: f *= i; i+; if (i = n) goto loop; cout “factorial of “ n “=“ f endl; ,空语句,空语句的格式为： ; 空语句不做任何事情，其作用是用于语法上需要一条语句的地方，而该地方又不需做任何事情。空语句常常作为结构语句的子句。 在一个复合语句中，需要转向该复合语句中最后一条语句之后，这时可以采用以下的做法： . goto end; end:; 用空语句和goto语句可以来实现continue语句的功能,用空语句和goto语句实现continue语句的功能,while (.) . continue; 上述程序等价于： while (.) . goto end; end:; ,程序设计风格,指对程序进行静态分析所能确认的程序特性 涉及程序的易读性和易维护性。 采用一致/有意义的标识符为程序实体（如：变量、函数等）命名。 使用符号常量 为程序书写注释 （行注释/， 块注释/*/) 采用代码的缩进格式等 结构化程序设计就是一种良好程序设计风格的典范。,结构化程序设计,结构化程序设计（Structured Programming，简称SP） 按照一组能够提高程序易读性与易维护性的规则进行程序设计的方法 SP不仅要求所编出的程序结构良好，而且还要求程序设计过程结构良好，后者是前者的基础。 对程序设计过程而言，“结构良好”是指 采用分解和抽象的方法来完成程序设计任务， 具体体现为：“自顶向下、逐步精化”的程序设计过程。 对程序代码而言，“结构良好”是指： 每个程序单位应具有单入口、单出口的性质。 不包含不会停止执行的语句，程序在有限时间内结束。 程序中没有无用语句，程序中所有语句都有被执行的机会。,结构化程序设计（续）,结构化程序设计通常可用三种基本结构来实现 三种结构都具有单入口、单出口的性质,（顺序）,（选择）,（循环）,三种基本结构： 顺序结构，选择分支结构，循环结构。 结论(1966 Bohm, Jacopini ) 任何复杂的程序可由三种基本结构组成。,常用算法设计,算法即操作步骤或解题思路。 3种基本结构是程序算法的基础。 穷举 递推 模拟 又称为仿真,穷举法,穷举即一一列举各种可能解，对它们分别进行测试，找出合适的解。 穷举法是数学上一种常用的方法。 计算机的运算速度很快，用循环结构可以实现穷举。 例 例 大奖赛评分程序； （去掉一个最高分和一个最低分的平均成绩） 例 求3300间的全部素数。（P59 例3.19） （判断每一个数是否为素数）,评分,max=MIN-1; min=MAX+1; coutscore; while (score=MIN) if(maxscore) min=score; average +=score; N+; cinscore; if(N2) average -= max; average-=min; average /= (N-2); cout“ The average score is: “averageendl; else cout“ 评委人数太少！“; ,int N=0; int max,min,score; int MAX,MIN; coutMAX; coutMIN;,尽量减小穷举规模,使用穷举算法，要尽量减小穷举规模，提高速度。 例: 搬砖 36块砖，36人搬，男搬4、女搬3、两个小儿抬一砖。要求一次搬完，问男、女、小儿各若干？ 男人数：0，8，若为9，总人数不等于36； 女人数：0，11； 小孩数：0，34的偶数（36-男人数-女人数）,#include void main(void) int menNum,womenNum,childNum; for(menNum=0; menNum=8; menNum+) for (womenNum=0; womenNum=11; womenNum+) childNum = 36-menNum-womenNum; if(childNum%2=0 ,递推,不断地由已知数据推得新的数据，直至求得解。 例 P58 3.18（牛顿迭代公式） 例 用辗转相除法求二个非负整数的最大公因子。 (m=n) u0= m, v0=n, 重复 r i = u i % vi ; u i +1= vi ; vi+1 = r i; 直到 r i为0。,if(mn) u=m;v=n; else u=n;v=m; int r=u%v; while(r) / while r is 0, v is the GCD u=v; v=r; r=u%v; ,例 猴子吃桃,假设猴子每天吃的桃子数为前一天的一半多b个，第n天，还乘下k个. 问原来有多少个桃子? 从最后一天往前推， 第n天剩下桃子数为restn , 则有restn = restn-1 - （restn-1/2 +b）; restn-1=2*( restn + b) 直到算出rest 1 。 For(r=k,b=s,day=n;day1;day-) r = 2*(r+b); day=1? Or day1?,模拟(simulation),模拟 将一个问题的模型在计算机系统的环境中对真实系统进行研究。 计算机模拟的一般过程是： 1） 描述问题 2） 构造模型 3） 设计模拟算法和程序 4） 运行并验证模型的准确性和精度； 几种模拟方法 时间步长法 事件步长法,时间步长法,每隔一段时间对系统的状态进行描述。 例 导弹追击飞机 示意图: 假设飞机只沿X轴水平飞行 导弹在同一平面内飞行。 采用时间步长法。 * 导弹、飞机的飞行轨迹都是时间的函数，,导弹追击飞机,某一时刻：导弹的位置（x,y）； VM：导弹的速度； 飞机的位置（d,0）; VA :飞机的速度； S:该时刻导弹与飞机的距离。 则：S=sqrt(y*y + (x-d)*(x-d); （S小于一个限定值，认为击中) 导弹在某一时刻测得飞机的位置，调整角度。 sin() = (d-x)/s; cos() = -y/s; 间隔dt时间后 d = d + VA*dt ; x = x + VM*dt*sin(); y = y + VM*dt*cos(); S=,代码段,x=X0; y=Y0; d=0; steps=0; / originally, the aeroplane is in (0,0) s=sqrt(y*y+(x-d)*(x-d); while(s=S0) steps+; d=d + VA*dt; x=x + VM*dt*(d-x)/s; y=y - VM*dt*y/s; s=sqrt(y*y+(x-d)*(x-d); ,事件步长法,当一个事件发生时,模拟一次 现实世界中有很多随机性的因素。 例 随机抽样 rand () 在 iostrem.h 中, 返回一个随机整数。 ( 例 random.prj , randomize.cpp ),产生随机数,#include #include using namespace std; void main( void ) /* See