c完全讲义pptunit.ppt

第二章 基本控制结构程序设计,结构化程序设计的特点是任何程序都可由三种基本结构及其组合来描述。 本章将介绍C+分支结构和循环结构的设计方法。还将介绍一些常用算法。,第二章 基本控制结构程序设计,2.2 分支结构程序设计,2.7 枚举类型,2.6 常用算法的应用实例,2.4 转向语句,2.3 循环结构程序设计,2.8 输入输出文件简介,2.5 结构化程序设计思想（选读）,2.1 算法的概念与表示方法,2.1 算法的概念与表示方法,2.1.1 算 法 的 概 念,2.1.3 算 法描述的三种基本结构,2.1.2 算 法 的 表 示,2.1.1 算 法 的 概 念,算法： 算法是解决问题的步骤。 计算机算法的特征： 可执行性 确定性 有穷性 可输入输出信息 算法是程序设计学习的重点。,2.1.2算法的表示,流程图： 流程图是图形化的表示方法，比较直观，基本组成元件包括矩形框、菱形框、箭头线等。其中矩形框表示要执行的指令，在框内标注指令内容；菱形框表示要判断其中表达式的值是真还是假；箭头线则标示指令的流程方向。 伪码： 伪码是介于自然语言和程序设计语言之间的一种类自然语言的表示方法，书写形式自由，容易转换为程序。,2.1.3算法描述的三种基本结构,3 循 环 结 构,1 顺 序 结 构,2 分 支 结 构,算法的基本结构： 对算法的理论研究和实践表明，任何算法的描述都可以分解为三种基本结构或它们的组合，这三种基本结构是顺序结构、分支结构和循环结构。,num115；,2.1.3算法描述的三种基本结构,(1) 顺序结构,【例21】 求两数之和。,流程图,显示结果：35,num220；,sumnum1+num2;,演示算法执行过程,输出sum;,2.1.3算法描述的三种基本结构,(2) 分支结构,【例22】 输入三个数，输出其中的最大数。,x7;,y12;,z10;,if(xy) maxx; else max y;,if (zmax) maxz;,输出max;,显示结果：12,流程图,块1,块2,真,假,演示算法执行过程,2.1.3算法描述的三种基本结构,【例23】求4个整数的和。,显示结果：60,演示算法执行过程,12,3,14,26,2,16,42,1,18,60,0,count4; /整数个数 sum0; /累加和的初值 while (count0) x输入一个整数; sumsum+x; countcount-1; 输出sum;,2.2 分支结构程序设计,对程序的运行流程进行控制，主要通过执行专门用来控制流程的语句来实现。 分支语句是基本流程控制语句之一。C+提供三种分支语句。,2.2.1 if语句,2.2.2 if语句的嵌套,2.2.4 swich语句,2.2.3 条件运算符“?:”,2.2.1 if 语句,if语句基本格式： 1、if (表达式) 语句1; 2、if (表达式) 语句1； else语句2;,【例2.4】 输入一个年份，判断是否闰年。,【例2.5】 从键盘上输入三个整数，输出其中的最大数。,嵌套if语句： if 语句中，如果内嵌语句又是if语句，就构成了嵌套if语句。if 语句可实现二选一分支，而嵌套if语句则可以实现多选一的多路分支情况。 嵌套有两种形式，嵌套在else分支中: if (表达式1) 语句1; else if (表达式2) 语句2; else if else 语句n; 嵌套在if分支中： if () if () ； else;,2.2.2 if 语句的嵌套,【例2.6】用嵌套if语句完成【例2.5】的任务。,else和if的配对关系： C+规定了if和else的“就近配对”原则，即相距最近且还没有配对的一对if和else首先配对。按上述规定，第二种嵌套形式中的else应与第二个if配对。如果根据程序的逻辑需要改变配对关系，则要将属于同一层的语句放在一对“”中。如第二种嵌套形式中，要让else和第一个if配对，语句必须写成： if (表达式1) if (表达式2) 语句1 ; else 语句2 ; 第二种嵌套形式较容易产生逻辑错误，而第一种形式配对关系则非常明确，因此从程序可读性角度出发，建议尽量使用第一种嵌套形式。,2.2.2 if 语句的嵌套,配对关系实例： /语句1： if(n%3=0) if(n%5=0) coutn是15的倍数endl; else cout n是3的倍数但不是5的倍数 endl; /语句2： if(n%3=0) if(n%5=0) coutn是15的倍数endl; else cout n 不是3的倍数 两个语句的差别只在于一个“”，但表达的逻辑关系却完全不同。,【例2.7】 某商场购物优惠活动,【例2.8】 求一元二次方程的根。,2.2.3 条件运算符“?:”,三元运算符： 三元运算符条件运算符“?:”可以用来简化if语句表达。其构成的表达式格式为： 表达式1 ? 表达式2 : 表达式3 例如：int a=6,b=7, min=ab?a:b; /min=6 min=ab?+a:+b; /min=7 a=7 b=7 min=ab?a+:b+; /min=6 a=7 b=7,ok,2.2.4 switch语句,开关语句(switch语句) 用来实现多选一： switch (表达式) case 常量表达式: 语句序列break; case 常量表达式n:语句序列nbreak; default:语句序列 ,开关语句注意要点： （1）各个case（包括default）分支出现的次序可以任意，通常将default放在最后。 （2）break语句可选，如果没有break语句，每一个case分支都只作为开关语句的执行入口，执行完该分支后，还将接着执行其后的所有分支。因此，为保证逻辑的正确实现，通常每个case 分支都与break语句联用。,2.2.4 switch语句,（3）每个常量表达式的取值必须各不相同，否则将引起歧义。 （4）允许多个常量表达式对应同一个语句序列。 例如： char score; cinscore; switch (score) case A: case a: coutexcellent; break; case B: case b: coutgood; break; default: coutfair; ,（5）从形式上看，switch语句的可读性比嵌套if语句好，但不是所有多选一的问题都可由开关语句完成，这是因为开关语句中限定了条件表达式的取值类型。,ok,【例2.9】 运输货物实行分段计费。采用不带break的开关语句实例,【例2.10】 设计一个计算器程序， 实现加、减、乘、除运算。,2.2.4 switch语句,循环控制语句是基本流程控制语句之一。C+提供三种循环语句：,2.3.1 while语句,2.3.4 循环的嵌套,2.3.3 for语句,2.3.2 do-while 语句,2.3 循环结构程序设计,2.3.1 while 语句,while语句也称为当循环。 语句格式为： while (表达式) 循环体语句；,图2.5 while语句的执行流程图,求表达式的值,表达式值为真?,是,否,执行循环体语句,【例2.11】 求1+2+3 +4+100的值。,2.3.1 while 语句,注意： 在有循环语句的程序中，通常循环开始前对循环条件进行初始化；而在循环体语句中要包含修改循环条件的语句，否则循环将不能终止而陷入死循环。 C+表达方式灵活，上例中的循环语句还可以写成： while (i=n) sum+=i+; 或者 while (sum+=i+, i=n) ;/循环体为空语句 修改程序后在VC+平台上运行，看是否正确,2.3.2 do-while 语句,do-while语句称为直到循环，格式为： do 循环体语句 while( 表达式 ),否,是,表达式的 值为真?,执行循环体语句,求表达式的值,图2.6 do-while语句的执行流程图,2.3.2 do-while 语句,do/while语句和while语句的区别： do/while语句至少执行一次循环体后再判断循环条件是否满足； while语句先判断条件是否满足，然后才执行循环体。可能一次也不执行。 多数情况下可以互相替代。,【例2.12】 用迭代法求a的平方根近似值。,【例2.13】 输入一段文本，统计文本的行数、单词数及字符数。,2.3.3 for 语句,for循环语句的格式为： for ( 表达式1; 表达式2; 表达式3 ) 循环体语句,ok,for语句、while语句、do/while语句比较：,int i=1,sum=0; /循环初始条件 while(i=4) sum+=i; i+; /修改循环条件 ,int i=1,sum=0; /循环初始条件 do sum+=i; i+;/修改循环条件 while(i=4);,int i,sum=0; for( i=1; i=4; i+ ) sum+=i; /*习惯上：表达式1：循环初始条件；表达式2：循环终止条件；表达式3：修改循环条件*/,ok,for 语句的应用,for语句的几点说明： 1、是先判断型的，同while语句； 2、使用更为灵活： 三个表达式可以是任意表达式，因此它们就可以实现循环初始化、计算、修改循环条件等任务，而不一定非在循环体中进行；,for 语句的应用,【例2.14】运行结果： 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181,【例2.15】 输入一个不超过5位的整数，将其反向后输出。,【例2.14】 设计程序输出Fibonacii 数列的前20项,2.3.4 循环的嵌套,【例2.16】 打印九九表。,嵌套循环： 当循环语句中的循环体中又有循环语句时，就构成了嵌套循环。 嵌套层次一般不超过3层，以保证可读性。,【例2.17】打印如下图形。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *,2.4 转向语句,break语句,return语句,goto 语句,continue语句,2.4 转向语句,break语句只能用在switch语句和循环语句中，用来跳出switch语句或提前终止循环，转去执行switch语句或循环语句之后的语句。 在for循环中可以用break结束循环： for(; ;) if() break; ,Break语句：,【例2.18】 给定正整数m，判定其是否为素数。,2.4 转向语句,continue语句只能用在循环语句中，用来终止本次循环。当程序执行到continue语句时，将跳过其后尚未执行的循环体语句，开始下一次循环。下一次循环是否执行仍然取决于循环条件的判断。 continue语句与break语句的区别在于，continue语句结束的只是本次循环，而break结束的是整个循环。,continue语句：,例：输出1100内3的倍数。 分析：设置整型变量I从1变化到100，依次测试I是否3的倍数，算法属于穷举法。 for (I=1;I=100;I+) if ( I%3！=0) continue; /I不是3的倍数，不输出，继续下一个I; 输出I的值；/I是3的倍数才输出 ,2.4 转向语句,goto语句和标号语句一起使用，所谓标号语句是用标识符标识的语句，它控制程序从goto语句所在的地方转移到标号语句处。goto语句会导致程序结构混乱，可读性降低，而且它所完成的功能完全可以用算法的三种基本结构实现，因此一般不提倡使用goto语句。但在某些特定场合下goto语句可能会显出价值，比如在多层循环嵌套中，要从深层地方跳出所有循环，如果用break语句，不仅要使用多次，而且可读性较差，这时goto语句可以发挥作用。,goto语句：,2.4 转向语句,return语句用于结束函数的执行，返回调用者，如果是主函数，则返回至操作系统。 利用一个return语句可以将一个数据返回给调用者。通常，当函数的返回类型为void时， return语句可以省略，如果使用也仅作为函数或程序结束的标志。,return语句：,2.5 结构化程序设计思想（选读）,传统的程序设计方法可以归结为“程序=算法+数据结构”，将程序定义为处理数据的一系列过程。这种设计方法的着眼点是面向过程的，特点是数据与程序分离，即数据与数据处理分离。 结构化程序设计的基本思想是采用自顶向下、逐步细化的设计方法和单入单出的控制结构。,结构化程序设计方法：,2.5 结构化程序设计思想（选读）,举一个简单的例子，要求读入一组整数，统计其中正整数和负整数的个数。 该任务的模块结构及细化过程如下：,2.5 结构化程序设计思想（选读）,（1）难以适应大型软件的设计。由于数据与数据处理相对独立，在大型多文件软件系统中，随着数据量的增大，程序越来越变得难以理解，多个文件之间的数据沟通也变得困难，还容易产生意想不到的结果，即所谓副作用。 （2）程序可重用性差。处理方法的改变或数据类型的改变都将导致重新设计，这种额外开销与可重用性相左，称为重复投入,结构化程序设计缺陷：,2.6 常用算法的应用实例,【例2.20】世界数学史上著名的“百鸡问题”,【例2.21】用欧基里德算法（也称辗转法） 求两个整数的最大公约数,【例2.23】输入一个8位二进制数，将其转换为十进制数输出。,【例2.19】 用筛选法求100之内的所有素数,【例2.22】输入一个小于1的数x，求sinx的近似值,2.7 枚举类型,2.7.1 枚举类型的定义,2.7.2 枚举变量的使用,枚举类型(enumerate)是c+中的一种派生数据类型，它是用户定义的若干枚举常量的集合。 枚举类型的变量，只能取枚举常量表中所列的值。 定义枚举类型的主要目的是增加程序的可读性。,2.7.1 枚举类型的定义,枚举类型定义： enum ; 关键字enum指明其后的标识符是一个类型的名字，枚举常量表中列出该类型的所有取值，各枚举常量之间以“，”间隔。 例： enmu color_set1 RED, BLUE, WHITE, BLACK; enum week Sun, Mon, Tue, Wed, Thu, Fri, Sat; 枚举常量（或称枚举成员）是以标识符形式表示的整型量，非法定义实例： enum letter_set a, d, F, s, T; /枚举常量只能是标识符 enum year_set2000,2001,2002,2003,2004,2005; /改为y2000等则正确,2.7.1 枚举类型的定义,枚举常量： 枚举常量代表该枚举类型的变量可能取的值，编译系统为每个枚举常量指定一个整数值，缺省状态下，这个整数就是所列举元素的序号，序号从0开始。如上例中RED、 BLUE、 WHITE、 BLACK的值分别为0、1、2、3。 用户也可以在类型定义时为部分或全部枚举常量指定整数值，在第一个指定值之前的枚举常量仍按缺省方式取值，而指定值之后的枚举常量按依次加1的原则取值。各枚举常量的值可以重复，但各枚举常量标识符必须不同。 例： enum fruit_set apple, orange, banana=1, peach, grape enum week Sun=7, Mon=1, Tue, Wed, Thu, Fri, Sat; 枚举常量apple、orange、banana、peach、grape的值分别为0、1、1、2、3。枚举常量Sun, Mon, Tue, Wed, Thu, Fri, Sat的值分别为7、1、2、3、4、5、6。,2.7.2 枚举类型的变量的使用,枚举类型应用要点： 1、定义枚举类型之后，就可以定义枚举类型的变量；亦可类型与变量同时定义（甚至类型名可省）： color_set1 color1, color2; enum Sun, Mon, Tue, Wed, Thu, Fri, Sat weekday1, weekday2; 2、枚举变量的取值范围就是整型数的一个子集。枚举变量占用内存的大小与整型数相同。 3、枚举变量允许的操作只有赋值和关系运算；如： color3=color4=BLUE； if (color3=color4) cout”相等”； cout color3WHITE; /输出“真”，即1,4、枚举变量不能直接输入，可以直接输出，但输出的是变量的整数值。例如： cincolor1/非法 coutcolor3/合法，输出的是2 从程序的合法性和可读性出发，枚举变量的输入输出一般都采用switch语句将其转换为字符或字符串。同时，枚举类型数据的其他处理也往往应用switch语句。,2.7.2 枚举类型的变量的使用,*【例2.24】 口袋中有红、黄、蓝、白、黑五种颜色的球若干个，每次从口袋中取三个不同颜色的球，统计并输出所有的取法。,2.8 输入输出文件简介,使用文件的步骤如下： (1) 说明一个文件流对象（内部文件）。文件流类型ifstream支持从输入文件提取数据的操作。而文件流类型ofstream完成数据写入输出文件的各种操作。 ifstream ifile; /定义输入文件，ifile为文件名，可用任意标识符 ofstream ofile; /定义输出文件，ofile为文件名，可用任意标识符 (2) 打开文件。 ifile.open(”d:my_in_file.txt”); ofile.open(”d:my_out_file.txt”); 引号中的”d:my_in_file.txt” 和”d:my_out_file.txt”为磁盘文件路径名，这样在文件流对象和磁盘文件名之间建立了联系。,(3) 对文件进行读写操作。最常见的文件读写是顺序的，所谓“顺序”指的是从文件头开始进行读写。顺序读写可用C+的提取运算符（）和插入运算符（）进行。也可以用读字符的get()和读字符串的getling()等函数。读写是在文件缓冲区中进行。 (4) 关闭文件。当打开一个文件进行读写后，应该显式地关闭该文件。与打开文件相对应： ifile.close(); ofile.close(); 关闭文件时，系统把与该文件相关联的文件缓冲区中的数据写到磁盘文件中，保证文件的完整；同时把磁盘文件名与文件流对象之间的关联断开，可防止误操作修改了磁盘文件。,【例2.25】将百鸡问题计算结果存入文件。,【例2.26】读出存放百鸡问题计算结果的文件。,第二章 基本控制结构程序设计,结束,欢迎再来！,if 语句【例24】,【例24】 输入一个年份，判断是否闰年。 算法分析：假定年份为year, 闰年的条件是 : year%4=0 ,ok,分析：读入三个数，先求出两个数中较大者，再将该大数与第三个数比较，求出最大数。 int main() int a, b, c, max; coutabc; coutb) max=a; else max=b; if(cmax) cout “最大数为:”cendl; else cout “最大数为:”maxendl; return 0; ,if 语句【例25】,【例2.5】 从键盘上输入三个整数，输出其中的最大数。,ok,/方法1：采用if中嵌套形式 int main() int a, b, c, max; coutabc; coutb) if(ac) max=a; /ab且ac else max=c; /ab且ac) max=b; /ac else max=c; /a=b且bc cout最大数max=max; return 0; ,if 语句【例26】,【例2.6】用嵌套if语句完成【例2.5】的任务。,ok,/方法2：采用else中嵌套形式 int main() int a,b,c,max; coutabc; coutb ,if 语句【例26】,ok,【例2.7】 某商场优惠活动规定，某种商品单 价为80元，一次购买5件以上（包含5件）10件以下（不包含10件）打9折，一次购买10件以上（包含10件）打8折。设计程序根据客户的购买量计 算总价。,算法 1、输入购买件数count，设置单价price=80(元) 2、根据count值确定折扣discount； 3、实际售价amount=price*count*discount； 4、输出amount的值。 算法细化： 2.1、if（count=5/单价,折扣,总价 int count;/购买件数 coutcount; if(count5) discount=1; else if(count10) discount=0.9; else discount=0.8; amount=price*count*discount; cout购买件数：countendl; cout单价：pricet折扣：“ discountendl; cout总价：amountendl; return 0; 请在VC+平台上运行，输入不同的件数，使程序所有分支都可以被执行一次。,ok,if 语句【例27】,【例2.8】 求一元二次方程 ax2+bx+c=0 的根。 其中系数a(a0)、b、c的值由键盘输入。 分析：输入系数a(a0)、b、c后，令delta= b24ac,结果有三种情况： *若delta=0， 方程有两个相同实根； *若delta0， 方程有两个不同实根； * 若delta0，方程无实根。,if 语句【例28】,#include #include using namespace std; int main() float a,b,c; float delta,x1,x2; const float zero=0.0001; /定义一个很小的常数 coutabc; couta=atb=bt c=cendl; delta=b*b-4*a*c;,求一元二次方程的根源程序,if 语句【例28】,if(fabs(delta)0) delta=sqrt(delta); x1=(-b+delta)/(2*a); x2=(-b-delta)/(2*a); cout方程有两个不同实根:; coutx1=x1tx2=“ x2endl; else cout方程无实根!endl; /delta0 return 0; 请在VC+平台上运行，输入不同的系数，使程序所有分支都可以被执行一次。,if 语句【例28】,不带break的开关语句实例,【例2.9】 运输公司对所运货物实行分段计费。设运输里程为s，则运费打折情况如下： s250 不打折扣 250=s500 2%折扣 500=s10005%折扣 1000=s20008%折扣 2000=s300010%折扣 3000=s15%折扣 设每公里每吨的基本运费为p，货物重量为w，总运输里程在某段中的里程为s，折扣为d，则该段运费为：p*w*s*(1-d) 设计程序，当输入p、w和s后，计算运费f。,算法： 总费用为各段费用之和，可采用不加break的switch语句。 分析：switch语句要求条件表达式取值为确定的若干个开关量，而不能使用关系表达式，用里程s进行判断似乎不符合条件。但是分析发现，里程s的分段点均是250的倍数，因此，将里程s除以250，取整数商c，可得到若干整数值。因此算法描述如下：,ok,不带break的开关语句实例,switch(c) default: d=0.15;f+=p*w*(s-3000)*(1-d);s=3000; case 8: case 9: case 10: case 11: d=0.1;f+=p*w*(s-2000)*(1-d);s=2000; case 4: case 5: case 6: case 7: d=0.08;f+=p*w*(s-1000)*(1-d);s=1000; case 2: case 3 d=0.05;f+=p*w*(s-500)*(1-d);s=500; case 1: d=0.02;f+=p*w*(s-250)*(1-d);s=250; case 0: d=0;f+=p*w*s*(1-d); ,3000=s 15%折扣 2000=s3000 10%折扣 1000=s2000 8%折扣 500=s1000 5%折扣 250=s500 2%折扣 s250 不打折扣,不带break的开关语句实例,int main() int c,s;double p,w,d,f; coutpws; f=0; c=s/250; switch(c) default: d=0.15;f+=p*w*(s-3000)*(1-d);s=3000; case 8: case 9: case 10: case 11: d=0.1;f+=p*w*(s-2000)*(1-d);s=2000; case 4: case 5: case 6: case 7: d=0.08;f+=p*w*(s-1000)*(1-d);s=1000; case 2: case 3: d=0.05;f+=p*w*(s-500)*(1-d);s=500; case 1: d=0.02;f+=p*w*(s-250)*(1-d);s=250; case 0: d=0;f+=p*w*s*(1-d); cout运输单价:pt重量:wt里程:sendl; cout折扣后运费:fendl; return 0; 请在VC+平台上运行，输入不同的里程。,【例2.10】 设计一个计算器程序，实现加、减、乘、除运算。 分析：读入两个操作数和运算符，根据运算符完成相应运算。 #include using namespace std; int main( ) float num1,num2; char op; coutnum1opnum2; switch(op) case +: coutnum1opnum2=num1+num2endl; break; case -: coutnum1opnum2=num1-num2endl; break; case *: coutnum1opnum2=num1*num2endl; break; case /: coutnum1opnum2=num1/num2endl; break; default : coutop是无效运算符!; return 0; 常量表达式采用字符型，上机运行一下。,while 语句【例2.11】,【例2.11】 求1+2+3+4+100的值。,ok,N个连续整数相加算法 1、设置变量i用来放加数，变量sum用来放被加数与和值,并初始化; 2、从第一个数开始，依次将加数赋给i，并进行操作sumsum+i，称为累加； 3、输出sum； 细化算法2： while(还有加数) i=当前加数； sum+=i; i准备接受下一个加数； ,源程序如下： #include using namespace std; const int n=100; /用常变量利于修改程序 int main( ) int i=1,sum=0;/循环初始条件 while(i=n) sum+=i; i+;/修改循环条件 coutsum=sumendl; return 0; 在VC+平台上运行，试一试是否正确,ok,【例2.12】 用迭代法求a的平方根近似值。求平方根的迭代公式为： 要求前后两个迭代根之差小于10- 5。,do-while 语句【例2.12】,迭代法求解：a是已知正数，x 0是迭代初值，给x 0一个值，假定 x 0 = a/2；则用迭代公式依次计算： x1=(x0+a/x0)/2；x2=(x1+a/x1)/2； xk+1=(xk+a/xk)/2； 当|xk+1 xk|(是一个较小的正数)时，迭代终止，取xk+1的值为a的平方根近似值。,ok,1、输入a(a0)及较小正数delta(也可用常变量)； 2、x 0 = a/2； 用迭代公式算 x1=(x0+a/x0)/2； 3、while（|x1 x0|=delta） x 0 = x 1 ；/把最近的值给x 0 x1=(x0+a/x0)/2； /求xk+1时只需要知道xk的值，所以只需2个变量 4、取x1的值为a的平方根近似值，输出。 2、3步骤很适合用do/while语句实现： x 1 = a/2； dox0=x1; x1=(x0+a/x0)/2； while（|x1 x0|=delta）;,和迭代法对应的程序算法是递推算法：,int main( ) float x0,x1,a; couta; if(a=1e-5); cout a的平方根为：x1endl; return 0; 在VC+平台上运行，输入2，3，4，5试一试是否正确,【例2.13】 输入一段文本，统计文本的行数、单词数及字符数。假定单词之间以空格或跳格或换行符间隔，且文本开始没有空行。 算法分析： 1、逐个读入文本中的字符，直到读到一个输入结束符EOF为止。 2、如何算行数？行结束标志为读到字符n； 3、如何算单词数？设一个变量isword，读到字符时isword=1，读到间隔符时isword=0；如果读到一个间隔符而此时isword值为1，则说明刚读完一个单词；（如果读到一个字符而此时isword值为0，则说明刚开始读一个单词；） 4、如何算字符数？,do-while 语句【例2.13】,ok,do-while 语句【例2.13】,算法： 1、设置变量line、word、ch分别代表行数、单词数、非分隔字符数，并初始化;设置变量isword来辅助统计单词数; 2、do从键盘读入一个字符c； if ( c=n) line+; if (是单词开头) word+; if (c不是分隔符) ch+; while (c!= EOF ); 3、输出统计结果。,int main( ) char c; int line=0, word=0, ch=0; int isword=0; cout输入一段文本（无空行）：endl; do c=cin.get(); if (ch= n) line+; /遇换行符行数+1 if (c!= ,【例2.14】 设计程序输出Fibonacii数列的前20项，要求每行输出5个数据。 Fibonacii数列定义如下：,算法分析：除了第0项和第1项外，每一项都是由类似方法产生，即前两项之和；所以求当前项时，只需要记住前两项；程序不需要为每一项设置专用变量； 属递推算法。,for 语句的应用【例2.14】,算法： 1、设置变量n表示第几项，变量 f 1和 f 2用来记住当前项f 3之前的两项 ；变量初始化n=0； 2、while （当前项不到第20项） if (当前项是第0项) f 1=0; if (当前项是第1项) f 2=1; if (当前项是第2项或更高项)f 3=f 1+f 2; 按要求输出 f 3 ; f 1=f 2; f 2=f 3; /记住最近两项 当前项后移一位； ,程序如下： /文件名：Ex2_14.cpp int main() int fib0=0,fib1=1,fib2; coutsetw(5)fib0setw(5)fib1 endl; for(int n=3;n=20;n+) fib2=fib0+fib1; coutsetw(5)fib2; if(n%5=0) coutendl; /控制每行5个数据 fib0=fib1; fib1=fib2; return 0； ,for 语句的应用【例2.14】,【例2.15】 输入一个不超过5位的整数，将其反向后输出。例如输入247，变成742输出。 算法分析： 1、将整数的各个数位逐个位分开，用一个数组保存各个位的值，然后反向组成新的整数。 2、将整数各位数字分开的方法是，通过求余得到个位数，然后将整数缩小十倍，再求余，并重复上述过程，分别得到十位、百位，直到整数的值变成0为止。,for 语句的应用【例2.15】,ok,数据处理： 1、设置变量num表示输入的整数，整型数组digit5用来存放num 的各个位；变量i用来表示数组的当前下标； 算法： 1、输入num; 变量初始化：i=0; 2、while （num!=0） num对10取余,得num的当前个位数digiti； num整除10，即去掉个位数，十位变个位，百位变十位，； i+;数组digit准备记录下一位； 3、将数组元素按下标从低到高的顺序输出；,程序如下： int main() int i,num,subscript; int digit5; coutnum; cout0); for(i=0;isubscript;i+) /整数的反向组合 num=num*10+digiti; cout反向后整数为：numendl; return 0； 在VC+平台上运行，试一试是否正确,循环的嵌套【例2.16】,分析： 1、计算机的输出是按行进行的，因此可以先用一个循环语句输出第一行表头。 2、表中各行数据的输出可以用下面的算法描述： for (i=1; i10; i+) couti; /输出行号 输出第i行数据； /A coutendl; /准备输出下一行 ,【例2.16】 打印九九表。打印格式为： * 1 2 3 4 5 6 7 8 9 1 1 2 2 4 3 3 6 9 9 9 18 27 36 45 54 63 72 81,3、第A行需要进一步细化。由于第i行数据是一组有规律的数列，每个数的值是其所在行与列的乘积，因此输出第i行可以： for (j=1; j10; j+) coutsetw(4)i*j; 4、按上述算法输出的每一行都将有九列，即打印出的是矩形表而不是下三角形表。进一步分析发现每一行的列数与所在行数相关，因此要输出三角形表，上面的循环语句需稍作修改： for (j=1; j=i; j+) coutsetw(4)i*j; 将此语句放到顶层算法的A行即可。,循环的嵌套【例2.16】,算法： 1、输出表头，用一个循环语句即可； 2、输出表体： for (i=1; i10; i+) couti; /输出行号 输出第i行数据； /A coutendl; /准备输出下一行 3、A行细化： for (j=1; j=i; j+) coutsetw(4)i*j;,循环的嵌套【例2.16】,在VC+平台上运行下面的程序： int main() int i,j; coutsetw(3)*setw(4) ; for(i=1;i10;i+) coutsetw(4)i; /输出表头(乘数) coutendlendl; for(i=1;i10;i+) coutsetw(3)isetw(4) ; /输出行号(被乘数) for(j=1;j=i;j+) coutsetw(4)i*j;/输出表中数据(乘积) coutendl; /准备输出下一行 return 0; ,循环嵌套【例2.16】 _打印九九表,【例2.17】打印如下图形。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 分析：根据按行输出的特点，语句书写如下： for (i=1; i=5; i+) 打印第i行；/B coutendl;/准备输出下一行 细化第B行。第i行可以看作两部分，先输出若干空格，接着输出若干*。每行输出的*数是同的，而空格数则与所在行相关，很明显，第i行空格数为5-i。故B行细化为以下两个语句： for (j=1; j=5-i; j+) cout ; for(j=1;j=11;j+) cout* ;,2.3.4 循环嵌套【例2.17】,#include #include using namespace std; int main() int i,j; for(i=1;i=5;i+) /外层循环的大括号一定不能丢掉 for(j=1;j=5-i;j+) cout ; /输出若干空格 for(j=1;j=11;j+) cout* ; /输出若干* coutendl; /准备输出下一行 return 0; ,2.3.4 循环嵌套【例2.17】,break 语句应用【例2.18】,【例2.18】 给定正整数m，判定其是否为素数。 分析：如果m2，m是素数的条件是不能被2,3,，（取整）整除。因此可以用2,3,，（取整）逐个去除m，如果被其中某个数整除了，则m不是素数，否则是素数。算法属于穷举法。 1、输入被测数m（m2）；令整型变量 k= sqrt(m) 2、判断m是否素数：设置辅助整型变量i, 使i从2开始直到k依次测试m能否整除i, 若能，则不是素数；for( i=2;i=k;i+）if(m%i=0) break； /* 条件满足，m不是素数,停止测试,结束for语句。*/ 3、根据i是否已达到k，输出结果是否为素数。,int main() int m,i,k; coutm; if(m=2) coutk) cout m是素数endl;/循环提前终止表示是非素数 else cout m不是素数endl; return 0; 在VC+平台上运行，改一下，使程序自动算出100以内的素数,2.6 常用算法的应用实例【例2.19】,直接法直接法是根据问题给出的条件直接求解。 【例2.19】 用筛选法求100之内的所有素数，并将这些素数输出，每行输出 2个数据。 分析 算法一 穷举法： 1、判断一个数是否素数？方法穷举法; 2、100之内的所有素数？方法：一个个试; 综上所述，得到一个循环嵌套的算法： for（m=2；m=100；m+）/穷举法 if（m是素数）按要求的格式输出m;,k= sqrt(m); for(i=2；i=k;i+) /穷举法 if(m%i=0) break； /m不是素数 if (i=k) m是素数； /刚才的for是由break结束的,分析 算法二 筛选法： 1、一个数如果是其他数的倍数，则这个数肯定不是素数； 2、在由 多个大于1的数 组成的集合中，剔除所有的非素数，剩下的就都是素数了； 综上所述，得到算法二（及所需的相应数据）： 1、将100之内的整数映射到一个集合。可以采用一个数组a来表示，数组元素值为各个整数； 2、在数组a中，从素数2开始剔除掉新找到的素数的整数倍的元素值（置0，非素数）； 3、输出数组a中数组元素值非0的元素，他们都是素数。,算法二 第 2步 的细化（筛选法）： for (i=0; i=99; i+) /数组下标099，元素值1100 2.1、 if (ai=0) continue; / ai已被定为非素数，并已被筛掉 2.2、将数组中所有是ai倍数的元素置0； for( j=i+1；j=99；j+) if(aj%ai=0) aj=0; ,2.6 常用算法的应用实例【例2.19】,#include #include #include using namespace std; const int n=100; int main() int an; int i,j; for(i=0;in;i+) ai=1+i; /用数组保存整数1-100 a0=0; /1不是素数，置0 for(i=1;in;i+) if(ai=0) continue; /该数已经置0,判断下一个 for(j=i+1;jn;j+)if(aj%ai=0) aj=0; /是ai倍数的元素置0； ,2.6 常用算法的应用实例【例2.19】,程序：,int count=0; cout1 n之间的素数：endl; for(i=0;in;i+) /输出所有素数 if(ai!=0) coutsetw(6)ai; count+; if(count%10=0) coutendl;/每行10个 coutendl; return 0; 运行结果：1100之间的素数： 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,2.6 常用算法的应用实例【例2.19】,2. 枚举法枚举法也称穷举法，基本思想是，在有限范围内列举所有可能的结果，找出其中符合要求的解。枚举法适合求解的问题是：可能的答案是有限个且答案是可知的，但又难以用解析法描述。这种算法通常用循环结构来完成。 【例2.20】 世界数学史上著名的“百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？ 分析：设鸡翁、母、雏分别为i，j，k，根据题意可得： i*5+j*3+k/3*1=100; i+j+k=100; 两个方程无法解出三个变量，只能将各种可能的取值代入，其中能满足两个方程的就是所需的解，因此这是枚举算法（也叫穷举法）的应用。 i、j、k可能的取值有哪些？分析可知，百钱最多可买鸡翁20，鸡母33，鸡雏300。,算法： for (i=0; i=20;i+) for (j=0; j=33;j+) for (k=0; k=300;k+) if (i+j+k=100) 这个算法使用三重循环，执行时间函数是立方阶，循环体将执行20*33*300=198000次。 我们希望在算法上改进一下，如能减少一重循环，将大大缩短运行时间。,2.6 常用算法的应用实例【例2.20】,实际上，当i、j确定时，k就可由题目要求确定为100-i-j，因此实际上只要用i、j去测试，用钱数检测就可以了。循环体将执行: 20*33=660次。 算法改进为： for (i=0; i+=20;) for (j=0; j+=33;) if ( 5*i+3*j+(100-i-j)/3=100 ) coutijk;,2.6 常用算法的应用实例【例2.20】,程序： #include #include using namespace std; int main() int i,j,k; cout 公鸡 母鸡 小鸡endl; for(i=0;i=20;i+) for(j=0;j=33;j+) k=100-i-j; if(5*i+3*j+k/3=100),2.6 常用算法的应用实例【例2.20】,注意：穷举法采用循环，须剔除的情况，应在循环体内用用条件语句实现，不可放在循环条件中，请考虑为什么？本例是选合条件的，如去除不合条件用continue语句，改改看？ 程序运行结果： 公鸡母鸡小鸡 0 25 75 4 18 78 8 11 81 12 4 84,2.6 常用算法的应用实例【例2.20】,2.6 常用算法的应用实例【例2.21】,3.递推法：递推算法是通过问题的一个或多个已知解，用同样的方法逐个推算出其他解，如数列问题，近似计算问题等，通常也要借助于循环结构完成。 【例2.21】 用欧基里德算法（也称辗转法）求两个整数的最大公约数。 分析：假定两个整数分别为num1和num2，最大公约数应当是不超过其中较小数的一个整数。 辗转法：用num1除以num2，求出余数resd，如果resd=0，则当前num2就是最大公约数，否则如果resd!=0，num1=num2, num2=resd, 重复以上过程，直到resd=0为止。,1、设置两个整型变量num1和num2代表两个数；输入num1、num2； 2、辗转法： 2.1、使num1num2; 2.2.1、设置变量resd=num1%num2； 2.2.2、if（resd=0）当前num2就是最大公 约数； Else num1=num2, num2=resd; 重复2.2.1和2.2.2，直到resd=0为止。 2.2、do resd=num1%num2； if（resd=0）当前num2就是最大公约数； else num1=num2, num2=resd; while (resd!=0); 3、输出当前的num2。,程序： int main( ) int num1,num2,resd; coutnum1num2; coutnum1和num2的最大公约数为：; for(;) resd=num1%num2; if(resd=0) break; num1=num2; num2=resd; coutnum2endl; return 0;,【例2.22】 输入一个小于1的数x，求sinx的近似值，要求误差小于0.0001。近似计算公式如下： 分析：这个近似计算可以看作一个累加过程，关键在于累加项数的确定。该求近似值的奇次多项式各项顺序改变符号，若取前n项累加和作为sin(x)的近似值，则第n+1项的绝对值就是误差限。因此可以这样考虑，若公式中第一项作为累加和的初值，则第二项就是误差，如果误差不满足要求，则将该项累加到累加和上，进而用该项推出第三项，第三项又是新的累加和的误差。经过这样累加、递推，直至满足要求为止。如果用item保存第n项，则推出第n+1项的方法为： itemitem*x*x/(2*n)*(2*n+1),2.6 常用算法的应用实例【例2.22】,程序： int main() const double epsilon=0.0001; /用epsilon保存误差 double x,sinx,item; int n=3,sign=-1; /sign保存符号 coutx; sinx=x;item=x*x*x/6; /第一项作为初值，第二项为误差项 while(itemeps