第4章循环控制ppt课件.ppt

程序设计 cs.sjtu 2011.9程序设计-1第4章循环控制ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望程序设计 cs.sjtu 2011.9程序设计-2for循环语句循环语句v格式：格式：forfor（表达式（表达式1 1；表达式；表达式2 2；表达式；表达式3 3）语句句v执行行过程：程：1.1.执行表达式行表达式1 12.2.执行表达式行表达式2 23.3.如果表达式如果表达式2 2的的结果果为“truetrue”，则执行循行循环体体和表达式和表达式3 3，然后回到，然后回到2 2，否，否则forfor语句句执行行结束束循环体循环体循环控制行循环控制行程序设计 cs.sjtu 2011.9程序设计-3for循环语句循环语句 续续续续v作作为计数循数循环，可以理解，可以理解为for(循循环变量量赋初初值；循；循环条件；循条件；循环变量增量增值)符合循符合循环条件条件时的的执行行语句句v循循环体所有体所有语句的一次完全句的一次完全执行称行称为一个循一个循环周期周期v循循环体可以是复合体可以是复合语句或空句或空语句句程序设计 cs.sjtu 2011.9程序设计-4逗号表达式逗号表达式v格式：表达式格式：表达式1，表达式，表达式2，,表达式表达式n v执行行过程：先程：先执行表达式行表达式1，再，再执行表达式行表达式2，再，再执行表达式行表达式n，整个表达式的，整个表达式的计算算结果果为最后一个表达式的最后一个表达式的值v逗号运算符的逗号运算符的优先先级是所有运算符中最低的是所有运算符中最低的 如如a的初的初值为0，则表达式表达式 a+=1,a+=2,a+=3,a+=4,a+=5的的结果果为 15 程序设计 cs.sjtu 2011.9程序设计-5v有了逗号表达式，从有了逗号表达式，从1加到加到100的的问题就就可以只用一个可以只用一个语句：句：for(i=1,s=0;i=100;+i)s+=i;或将所有的初始化都放在循或将所有的初始化都放在循环外，即外，即i=1；s=0；for(；i=100;+i)s+=i;v建建议还是用是用s=0;for(i=1;i=100;+i)s+=i;程序设计 cs.sjtu 2011.9程序设计-6for循环的进一步讨论循环的进一步讨论 续续v表达式表达式2也不一定是关系表达式。它可以是也不一定是关系表达式。它可以是逻辑表表达式，甚至可以是算达式，甚至可以是算术表达式。当表达式表达式。当表达式2是算是算术表达式表达式时，只要表达式的，只要表达式的值为非非0，就，就执行循行循环体，体，表达式的表达式的值为0时退出循退出循环。v如果表达式如果表达式2省略，即不判断循省略，即不判断循环条件，循条件，循环将无将无终止地止地进行下去。行下去。v无无终止的循止的循环称称为“死循死循环”v最最简单的死循的死循环是是 for(;);v要要结束一个无限循束一个无限循环，必，必须从从键盘上上输入特殊的入特殊的命令以中断程序命令以中断程序执行并行并强制退出制退出 程序设计 cs.sjtu 2011.9程序设计-7For循环的进一步讨论循环的进一步讨论 续续v表达式表达式3也可以是任何表达式，一般也可以是任何表达式，一般为赋值表表达式或逗号表达式。表达式达式或逗号表达式。表达式3是在每个循是在每个循环周周期期结束后束后对循循环变量的修正。表达式量的修正。表达式3也可以也可以省略，此省略，此时做完循做完循环体后直接体后直接执行表达式行表达式2。v如从如从1加到加到100，可以写，可以写为 s=0;for(i=1;i=100;)s+=i,i+;或或 s=0;for(i=1;i=100;s+=i,i+);程序设计 cs.sjtu 2011.9程序设计-8For循环实例循环实例v求函数求函数 在区在区间a,b之之间的定的定积分分v实现思想：函数与思想：函数与x轴围成的区域的面成的区域的面积。定。定积分分可以通可以通过将将这块面面积分解成一分解成一连串的小矩形，串的小矩形，计算各小矩形的面算各小矩形的面积的和而得到的和而得到 ab程序设计 cs.sjtu 2011.9程序设计-9int main()double a,b,dlt,integral=0;cout a b;cout dlt;for(double x=a+dlt/2;x b;x+=dlt)integral+=(x*x+5*x+1)*dlt;cout 积分分值为：integral 0.000001)while(p0.000001)ex+=p;ex+=p;计算新的计算新的p p；问题：如何计算p？计算第i个p，需要两个i次的循环。第一个循环计算xi，第二个循环计算i！解决方案：从前一项计算后一项。如果p是第i项的值，则第i+1项的值为 p*x/(i+1)程序设计 cs.sjtu 2011.9程序设计-13int main()int main()double ex,x,p;/exdouble ex,x,p;/ex存储存储e ex x的值，的值，p p保存当前项的值保存当前项的值 int i;int i;cout cout x;cin x;ex=0;p=1;i=0;ex=0;p=1;i=0;while(p 1e-6)while(p 1e-6)ex+=p;ex+=p;+i;+i;p=p*x/i;p=p*x/i;cout e cout e的的 x x 次方等于次方等于：ex endl;ex endl;return 0;return 0;程序设计 cs.sjtu 2011.9程序设计-14第第4章章 循环控制循环控制 重复重复N次循次循环While循循环Do while循循环循循环的中途退出的中途退出枚枚举法法贪婪法婪法程序设计 cs.sjtu 2011.9程序设计-15DoWhile 循环语句循环语句v格式：格式：do do 语句句 while(while(表达式表达式)v执行行过程：先程：先执行循行循环体，然后判断循体，然后判断循环条件。如条条件。如条件成立，件成立，继续循循环，直到条件，直到条件为假假v如将若干个如将若干个输入数相加，直到入数相加，直到输入入0 0为止。止。total=0;total=0;do cout do cout value;cin value;total+=value;total+=value;while(value!=0);while(value!=0);程序设计 cs.sjtu 2011.9程序设计-16编程实例编程实例v计算方程算方程f(x)在区在区间a,b之之间的根的根。注意，。注意，f(a)和和f(b)必必须异号异号v假假设方程方程为 ，区，区间为-1,1 程序设计 cs.sjtu 2011.9程序设计-17计算方法计算方法v令令x1=a,x2=bv连接连接(x1,f(x1)和和(x2,f(x2)的弦交与的弦交与x轴的坐标点可轴的坐标点可用如下公式求出用如下公式求出 v若若f(x)与与f(x1)同符号，则方程的根在同符号，则方程的根在(x,x2)之间，将之间，将x作为新的作为新的x1。否则根在。否则根在(x1,x)之间，将之间，将x设为新的设为新的x2。v重复步骤重复步骤和和，直到，直到f(x)小于某个指定的精度为止。小于某个指定的精度为止。此时的此时的x为方程为方程f(x)=0的根。的根。程序设计 cs.sjtu 2011.9程序设计-18int main()double x,x1=-1,x2=1,fx1,fx2,fx;do fx1=x1*x1*x1+2*x1*x1+5*x1-1;fx2=x2*x2*x2+2*x2*x2+5*x2-1;x=(x1*fx2-x2*fx1)/(fx2-fx1);fx=x*x*x+2*x*x+5*x-1;if(fx*fx1 0)x1=x;else x2=x;while(fabs(fx)1e-7);cout 方程的根方程的根为：x endl;return 0;程序设计 cs.sjtu 2011.9程序设计-19第第4章章 循环控制循环控制 重复重复N次循次循环While循循环Do while循循环循循环的中途退出的中途退出枚枚举法法贪婪法婪法程序设计 cs.sjtu 2011.9程序设计-20循环的中途退出循环的中途退出v考考虑一个一个读入数据直到入数据直到读到到标志志值的的问题。如。如用自然用自然语言描述，基于言描述，基于标志的循志的循环的的结构由以构由以下步下步骤组成：成：读入一个入一个值如果如果读入入值与与标志志值相等，相等，则退出循退出循环执行在行在读入那个特定入那个特定值情况下需要情况下需要执行的行的语句句v当一个循当一个循环中有一些操作必中有一些操作必须在条件在条件测试之前之前执行行时，称，称为循循环的中途退出的中途退出问题。程序设计 cs.sjtu 2011.9程序设计-21问题问题v由于循由于循环语句是先判断条件再决定是否句是先判断条件再决定是否执行循行循环体，循体，循环的中途退出将使得循的中途退出将使得循环体中的某些体中的某些语句句必必须重复出重复出现。v基于基于标志的循志的循环结构被改构被改为：读入一个入一个值While（读入入值与与标志志值不相等）不相等）执行在行在读入那个特定入那个特定值情况下需要情况下需要执行的行的语句句 读入一个入一个值 程序设计 cs.sjtu 2011.9程序设计-22解决方案解决方案vbreak语句：跳出循句：跳出循环v上述上述问题可以用下列方案解决：可以用下列方案解决：while(true)提示用提示用户并并读入数据入数据 if (value=标志志)break;根据数据作出根据数据作出处理理 vcontinue语句：跳出当前循句：跳出当前循环周期周期程序设计 cs.sjtu 2011.9程序设计-23第第4章章 循环控制循环控制 重复重复N次循次循环While循循环Do while循循环循循环的中途退出的中途退出枚枚举法法贪婪法婪法程序设计 cs.sjtu 2011.9程序设计-24枚举法枚举法v对所有可能的情况一种一种去所有可能的情况一种一种去尝试，直，直到找到正确的答案。到找到正确的答案。v枚枚举法的法的实现基基础是循是循环。程序设计 cs.sjtu 2011.9程序设计-25枚举法实例一枚举法实例一v用用50元元钱买了三种水果。各种水果加起来一共了三种水果。各种水果加起来一共100个。西个。西瓜瓜5元一个，苹果元一个，苹果1元一个，桔子元一个，桔子1元元3个，个，设计一程序一程序输出出每种水果各每种水果各买了几个了几个 v它有两个它有两个约束条件：束条件：第一是三种水果一共第一是三种水果一共100个；个；第二是三种水果一共花了第二是三种水果一共花了50元元v可以按一个可以按一个约束条件列出所有可行的情况，然后束条件列出所有可行的情况，然后对每个可每个可能解能解检查它是否它是否满足第二个足第二个约束条件束条件。也可以用第二个。也可以用第二个约束条件列出所有情况，然后束条件列出所有情况，然后对每个可能解每个可能解检查它是否它是否满足第一个足第一个约束条件束条件。程序设计 cs.sjtu 2011.9程序设计-26#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;程序设计 cs.sjtu 2011.9程序设计-27执行结果执行结果Mellon：1 apple：18 orange：81Mellon：2 apple：11 orange：87Mellon：3 apple：4 orange：93程序设计 cs.sjtu 2011.9程序设计-28实例二实例二 四大湖问题四大湖问题上地理上地理课时，四个学生回答我国四大湖的大小，四个学生回答我国四大湖的大小时分分别说：甲：洞庭最大，洪甲：洞庭最大，洪泽最小，鄱阳第三最小，鄱阳第三 乙：洪乙：洪泽最大，洞庭最小，鄱阳第二，太湖第三最大，洞庭最小，鄱阳第二，太湖第三 丙：洪丙：洪泽最小，洞庭第三最小，洞庭第三 丁：鄱阳最大，太湖最小，洪丁：鄱阳最大，太湖最小，洪泽第二，洞庭第三第二，洞庭第三对于每个湖的大小，每个人于每个湖的大小，每个人仅答答对一个，一个，设计一程序一程序让计算机通算机通过这些信息去判些信息去判别四个湖的大小。四个湖的大小。程序设计 cs.sjtu 2011.9程序设计-29解题思路解题思路v如果如果用用a,b,c,d分分别表示四个湖的排序。表示四个湖的排序。a表示洞庭湖，表示洞庭湖，b表示洪表示洪泽湖，湖，c表示鄱阳湖，表示鄱阳湖，d表示太湖。我表示太湖。我们可以可以假假设：洞庭最大，洪洞庭最大，洪泽第二，鄱阳第三，太湖第四，第二，鄱阳第三，太湖第四，然后然后检查每位同学是否都每位同学是否都讲对了一个。如果不是，再了一个。如果不是，再尝试下一种情况：洞庭最大，洪下一种情况：洞庭最大，洪泽第二，鄱阳第四，第二，鄱阳第四，太湖第三，再太湖第三，再检查每位同学是否都每位同学是否都讲对了一个。了一个。尝试所有可能的情况，直到所有可能的情况，直到满足每位同学都足每位同学都讲对一个一个为止。止。程序设计 cs.sjtu 2011.9程序设计-30枚举法枚举法续续续续v为了了尝试所有情况，我所有情况，我们需要假需要假设洞庭洞庭湖可能是最大，也可能是第二、第三或湖可能是最大，也可能是第二、第三或第四。因此，第四。因此，a的的值可能从可能从1变到到4。同。同样，b,c,d的的值也都可能从也都可能从1变到到4。为此，此，我我们需要一个控制需要一个控制结构，使构，使a,b,c,d的的值能自能自动从从1变到到4。这种种结构就是循构就是循环结构。构。程序设计 cs.sjtu 2011.9程序设计-31四大湖排列问题的解四大湖排列问题的解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&(b=1)+(a=4)+(c=2)+(d=3)=1&(b=4)+(a=3)=1&(c=1)+(d=4)+(b=2)+(a=3)=1)cout a b c d;问题：效率差解决方法：一旦找到答案就应该结束程序设计 cs.sjtu 2011.9程序设计-32main()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&(b=1)+(a=4)+(c=2)+(d=3)=1&(b=4)+(a=3)=1&(c=1)+(d=4)+(b=2)+(a=3)=1)cout a b c d;flag=true;break;if (flag)break;if(flag)break;改进版1：程序不够简练程序设计 cs.sjtu 2011.9程序设计-33main()int a,b,c,d;bool flag=false;for(a=1;a=4&!flag;+a)for(b=1;b=4&!flag;+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&(b=1)+(a=4)+(c=2)+(d=3)=1&(b=4)+(a=3)=1&(c=1)+(d=4)+(b=2)+(a=3)=1)cout a b c d;flag=true;break;改进版2程序设计 cs.sjtu 2011.9程序设计-34列出列出ABC三个字母的全排列三个字母的全排列v解解题思路：思路：让第一个位置的第一个位置的值从从A依次依次变到到C让第一个位置的第一个位置的值从从A依次依次变到到C让第一个位置的第一个位置的值从从A依次依次变到到C注意三个位置的注意三个位置的值不能相同不能相同v可以用一个三可以用一个三层的嵌套循的嵌套循环实现，循，循环变量是量是字符字符类型型程序设计 cs.sjtu 2011.9程序设计-35int 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;程序设计 cs.sjtu 2011.9程序设计-36第第4章章 循环控制循环控制 重复重复N次循次循环While循循环Do while循循环循循环的中途退出的中途退出枚枚举法法贪婪法婪法程序设计 cs.sjtu 2011.9程序设计-37贪婪法的基本思想贪婪法的基本思想v在求解在求解过程的每一步都程的每一步都选取一个局部最取一个局部最优的策略，把的策略，把问题规模模缩小，最后把每一步小，最后把每一步的的结果合并起来形成一个全局解。果合并起来形成一个全局解。v基本步基本步骤：从某个初始解出从某个初始解出发采用迭代的采用迭代的过程，当可以向目程，当可以向目标前前进一步一步时，就根据局最就根据局最优策略，得到一个部分解，策略，得到一个部分解，缩小小问题规模。模。将所有解将所有解综合起来合起来程序设计 cs.sjtu 2011.9程序设计-38硬币找零问题硬币找零问题v对于一种于一种货币，有面，有面值为1分分,2分分,5分和分和1角的硬角的硬币，最少需要多少个硬，最少需要多少个硬币来找出来找出K分分钱的零的零钱。程序设计 cs.sjtu 2011.9程序设计-39贪婪法解题思想贪婪法解题思想v不断地使用面不断地使用面值最大的硬最大的硬币。如要找零。如要找零的的值小于最大的硬小于最大的硬币值，则尝试第二大第二大的硬的硬币。依此。依此类推。推。v不断不断尝试的的过程就是循程就是循环程序设计 cs.sjtu 2011.9程序设计-40#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;程序设计 cs.sjtu 2011.9程序设计-41/不断尝试每一种硬币不断尝试每一种硬币 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;程序设计 cs.sjtu 2011.9程序设计-42小结小结v计算机的算机的强项是不是不厌其其烦地做同地做同样的操作，的操作，这是通是通过循循环语句句实现的的 v循循环语句：句：while、do.while和和for v基于循基于循环的算法：的算法：枚枚举法：法：对某些某些问题，在，在寻找它的解找它的解时需要需要检查所有的可能的方案，从中找出可行解。所有的可能的方案，从中找出可行解。贪婪法：可用于求婪法：可用于求问题的最的最优解。但不一定解。但不一定对所所有有问题都能得到最都能得到最优解。解。