C++程序设计课程介绍第4章 循环控制.ppt

第4章 循环控制,重复N次循环While循环Do while循环循环的中途退出枚举法贪婪法,重复N次操作,某一组语句要重复执行N次“重复n次”循环通常用 for 语句实现，如将1到100十个数相加可写为：s=0;for(i=1;i=100;+i)s+=i;,i 称为循环变量,循环条件,每次循环后循环变量的变化,for循环语句,格式：for（表达式1；表达式2；表达式3）语句执行过程：1.执行表达式12.执行表达式23.如果表达式2的结果为“true”，则执行循环体和表达式3，然后回到2，否则for语句执行结束,循环体,循环控制行,for循环语句 续,作为计数循环，可以理解为for(循环变量赋初值；循环条件；循环变量增值)符合循环条件时的执行语句循环体所有语句的一次完全执行称为一个循环周期循环体可以是复合语句或空语句,空语句和复合语句,单个分号组成的语句成为空语句用 括起来的一组语句称为复合语句。在逻辑上看成一个语句。复合语句可以放在任何单语句出现的地方在复合语句中可以定义变量,For循环实例,某班级有100个学生，设计一程序统计该班级某门考试成绩中的最高分、最低分和平均分。方案一：先输入100个整型数，保存在各自的变量中。然后依次检查这100个数，找出最大的和最小的。在找的过程中顺便可以把所有的数都加起来。最后将总和除100就得到了平均值。,方案一的缺陷,需要定义100个变量需要输入100个变量的值从100个变量中找出最大者，需要100个if 语句从100个变量中找出最小者，需要100个if 语句将这100个变量加起来需要一个长长的算术表达式,方案二,每个学生的分数在处理过后就没用了，为此，可以用一个变量保存当前正在处理的分数每次输入分数的同时将它们加起来：70加40等于110，110加80等于190。并记住最低分的和最高分的值。上述过程重复100次。,方案二的实现,定义：int value,total，max,min;当输入每个数值时必须执行下面的步骤，这可以用for循环实现请求用户输入一个整数值，将它存储在变量value中。将value加入到保存当前和的变量total中。如果value大于max，将value存于max。如果value小于min，将value存于min。,#includeusing namespace std;int main()int value,total,max,min,i;/value：当前输入数据，i为循环变量 total=0;max=0;min=100;/变量的初始化 for(i=1;i value;total+=value;if(value max)max=value;if(value min)min=value;cout n最高分：max endl;cout 最低分：min endl;cout 平均分：total/100 endl;return 0;,注意缩进,For循环的进一步讨论,For循环的三个表达式可以是任意表达式三个表达式都是可选的。如果循环不需要任何初始化工作，则表达式1可以缺省。如循环前需要做多个初始化工作，可以将多个初始化工作组合成一个逗号表达式，作为表达式1。,逗号表达式,格式：表达式1，表达式2，,表达式n 执行过程：先执行表达式1，再执行表达式2，再执行表达式n，整个表达式的计算结果为最后一个表达式的值逗号运算符的优先级是所有运算符中最低的 如a的初值为0，则表达式 a+=1,a+=2,a+=3,a+=4,a+=5的结果为 15,有了逗号表达式，从1加到100的问题就可以只用一个语句：for(i=1,s=0;i=100;+i)s+=i;或将所有的初始化都放在循环外，即i=1；s=0；for(；i=100;+i)s+=i;建议还是用 s=0;for(i=1;i=100;+i)s+=i;,For循环的进一步讨论 续,表达式2也不一定是关系表达式。它可以是逻辑表达式，甚至可以是算术表达式。当表达式2是算术表达式时，只要表达式的值为非0，就执行循环体，表达式的值为0时退出循环。如果表达式2省略，即不判断循环条件，循环将无终止地进行下去。无终止的循环称为“死循环”最简单的死循环是 for(;);要结束一个无限循环，必须从键盘上输入特殊的命令以中断程序执行并强制退出,For循环的进一步讨论 续,表达式3也可以是任何表达式，一般为赋值表达式或逗号表达式。表达式3是在每个循环周期结束后对循环变量的修正。表达式3也可以省略，此时做完循环体后直接执行表达式2。如从1加到100，可以写为 s=0;for(i=1;i=100;)s+=i,i+;或 s=0;for(i=1;i=100;s+=i,i+);,循环的嵌套,将一个for循环嵌入到另一个for循环中 内层的for循环在外层循环的每一个周期中都将执行它的所有的周期 每个for循环都要有一个自己的循环变量以避免循环变量间的互相干扰,打印九九乘法表,#includeusing namespace std;void main()int i,j;for(i=1;i=9;+i)for(j=1;j=9;+j)cout i*j t;cout endl;,第4章 循环控制,重复N次循环While循环Do while循环循环的中途退出枚举法贪婪法,While循环,如何对不同人数的班级完成分数统计任务?方法一：在程序的开始部分请求用户输入数据个数，并将之存放在某个变量中，以此来替换for语句控制行中使用的常量100 方法二：定义一个特殊的输入数据，用户可以通过输入该数据来标识输入序列的结束 方法二需要另外一种的循环控制结构,While 循环语句,格式：while（表达式）语句执行过程：先计算出条件表达式的值。如果是false，循环终止，并接着执行在整个while循环之后的语句。如果是true，整个循环体将被执行，而后又回到while语句的第一行，再次对条件进行检查。用途：用于循环次数不定的循环。循环是否结束取决于某一个条件是否成立,While语句实例,设计一个程序，统计某个班级某门考试成绩中的最高分、最低分和平均分。当输入的分数为-1时，输入结束,int main()int value,total,max,min,noOfInput;/total总分，noOfInput人数 total=0;max=0;min=100;noOfInput=0;/置初值 cout value;while(value!=-1)+noOfInput;total+=value;if(value max)max=value;if(value value;cout n最高分：max endl;cout 最低分：min endl;cout 平均分：total/noOfInput endl;return 0;,eg 2.求,时结束。,ex=0;p=1;while(p0.000001)ex+=p;计算新的p；,问题：如何计算p？计算第i个p，需要两个i次的循环。第一个循环计算xi，第二个循环计算i！解决方案：从前一项计算后一项。如果p是第i项的值，则第 i+1 项的值为 p*x/(i+1),int main()double ex,x,p;/ex存储ex的值，p保存当前项的值 int i;cout x;ex=0;p=1;i=0;while(p 1e-6)ex+=p;+i;p=p*x/i;cout e的 x 次方等于：ex endl;return 0;,例子：将输入句子中的字符全部输出为大写,/Capitalize lowercase lettersint main()char c;cout c;while(c!=.)if(a=c,第4章 循环控制,重复N次循环While循环Do while循环循环的中途退出枚举法贪婪法,DoWhile 循环语句,格式：do 语句 while(表达式)执行过程：先执行循环体，然后判断循环条件。如条件成立，继续循环，直到条件为假如将若干个输入数相加，直到输入0为止。total=0;do cout value;total+=value;while(value!=0);,第4章 循环控制,重复N次循环While循环Do while循环循环的中途退出枚举法贪婪法,循环的中途退出,考虑一个读入数据直到读到标志值的问题。如用自然语言描述，基于标志的循环的结构由以下步骤组成：读入一个值如果读入值与标志值相等，则退出循环执行在读入那个特定值情况下需要执行的语句当一个循环中有一些操作必须在条件测试之前执行时，称为循环的中途退出问题。,问题,由于循环语句是先判断条件再决定是否执行循环体，循环的中途退出将使得循环体中的某些语句必须重复出现。基于标志的循环结构被改为：读入一个值While（读入值与标志值不相等）执行在读入那个特定值情况下需要执行的语句 读入一个值,解决方案,break语句：跳出循环上述问题可以用下列方案解决：while(true)提示用户并读入数据 if(value=标志)break;根据数据作出处理 continue语句：跳出当前循环周期,第4章 循环控制,重复N次循环While循环Do while循环循环的中途退出枚举法贪婪法,枚举法,对所有可能的情况一种一种去尝试，直到找到正确的答案。枚举法的实现基础是循环。,枚举法实例一,用50元钱买了三种水果。各种水果加起来一共100个。西瓜5元一个，苹果1元一个，桔子1元3个，设计一程序输出每种水果各买了几个 它有两个约束条件：第一是三种水果一共100个；第二是三种水果一共花了50元可以按一个约束条件列出所有可行的情况，然后对每个可能解检查它是否满足第二个约束条件。也可以用第二个约束条件列出所有情况，然后对每个可能解检查它是否满足第一个约束条件。,#include using namespace std;int main()int mellon,apple,orange;/分别表示西瓜数、苹果数和桔子数 for(mellon=1;mellon10;+mellon)/对每种可能的西瓜数 for(apple=1;apple 50-5*mellon;+apple)/当西瓜数给定后可能的苹果数 orange=3*(50-5*mellon-apple);/剩下的钱全买了桔子 if(mellon+apple+orange=100)/三种水果数之和是否为100 cout mellon:mellon;cout apple:apple;cout orange:orange endl;return 0;,执行结果,Mellon：1 apple：18 orange：81Mellon：2 apple：11 orange：87Mellon：3 apple：4 orange：93,实例二 四大湖问题,上地理课时，四个学生回答我国四大湖的大小时分别说：甲：洞庭最大，洪泽最小，鄱阳第三 乙：洪泽最大，洞庭最小，鄱阳第二，太湖第三 丙：洪泽最小，洞庭第三 丁：鄱阳最大，太湖最小，洪泽第二，洞庭第三对于每个湖的大小，每个人仅答对一个，设计一程序让计算机通过这些信息去判别四个湖的大小。,解题思路,如果用a,b,c,d分别表示四个湖的排序。a表示洞庭湖，b表示洪泽湖，c表示鄱阳湖，d表示太湖。我们可以假设：洞庭最大，洪泽第二，鄱阳第三，太湖第四，然后检查每位同学是否都讲对了一个。如果不是，再尝试下一种情况：洞庭最大，洪泽第二，鄱阳第四，太湖第三，再检查每位同学是否都讲对了一个。尝试所有可能的情况，直到满足每位同学都讲对一个为止。,枚举法续,为了尝试所有情况，我们需要假设洞庭湖可能是最大，也可能是第二、第三或第四。因此，a的值可能从1变到4。同样，b,c,d的值也都可能从1变到4。为此，我们需要一个控制结构，使a,b,c,d的值能自动从1变到4。这种结构就是循环结构。,四大湖排列问题的解,main()int a,b,c,d;for(a=1;a=4;+a)for(b=1;b=4;+b)if(a=b)continue;else for(c=1;c=4;+c)if(c=a|c=b)continue;else d=10 a b-c;if(a=1)+(b=4)+(c=3)=1,问题：效率差解决方法：一旦找到答案就应该结束,main()int a,b,c,d;bool flag=false;for(a=1;a=4;+a)for(b=1;b=4;+b)if(a=b)continue;else for(c=1;c=4;+c)if(c=a|c=b)continue;else d=10 a b-c;if(a=1)+(b=4)+(c=3)=1,改进版1：,程序不够简练,main()int a,b,c,d;bool flag=false;for(a=1;a=4,改进版2,列出ABC三个字母的全排列,解题思路：让第一个位置的值从A依次变到C让第一个位置的值从A依次变到C让第一个位置的值从A依次变到C注意三个位置的值不能相同可以用一个三层的嵌套循环实现，循环变量是字符类型,int main()char c1,c2,c3;for(c1=A;c1=C;+c1)for(c2=A;c2=C;+c2)if(c1=c2)continue;else for(c3=A;c3=C;+c3)if(c3=a1|c3=c2)continue;else cout c1 c2 c3 endl;,第4章 循环控制,重复N次循环While循环Do while循环循环的中途退出枚举法贪婪法,贪婪法的基本思想,在求解过程的每一步都选取一个局部最优的策略，把问题规模缩小，最后把每一步的结果合并起来形成一个全局解。基本步骤：从某个初始解出发采用迭代的过程，当可以向目标前进一步时，就根据局最优策略，得到一个部分解，缩小问题规模。将所有解综合起来,硬币找零问题,对于一种货币，有面值为1分,2分,5分和1角的硬币，最少需要多少个硬币来找出K分钱的零钱。,贪婪法解题思想,不断地使用面值最大的硬币。如要找零的值小于最大的硬币值，则尝试第二大的硬币。依此类推。不断尝试的过程就是循环,#includeusing namespace std;#define ONEFEN 1#define TWOFEN 2#define FIVEFEN 5#define ONEJIAO 10int main()int money;int onefen=0,twofen=0,fivefen=0,onejiao=0;cout money;,/不断尝试每一种硬币 while(money=ONEJIAO)onejiao+;money-=ONEJIAO;while(money=FIVEFEN)fivefen+;money-=FIVEFEN;while(money=TWOFEN)twofen+;money-=TWOFEN;while(money=ONEFEN)onefen+;money-=ONEFEN;/输出结果 cout 1角硬币数：onejiao endl;cout 5分硬币数：fivefen endl;cout 2分硬币数：twofen endl;cout 1分硬币数：onefen endl;return 0;,小结,计算机的强项是不厌其烦地做同样的操作，这是通过循环语句实现的 循环语句：while、do.while和for 基于循环的算法：枚举法：对某些问题，在寻找它的解时需要检查所有的可能的方案，从中找出可行解。贪婪法：可用于求问题的最优解。但不一定对所有问题都能得到最优解。,