第4章 循环控制.ppt

《第4章 循环控制.ppt》由会员分享，可在线阅读，更多相关《第4章 循环控制.ppt（42页珍藏版）》请在麦多课文档分享上搜索。

1、第4章 循环控制,重复N次循环 While循环 Do while循环 循环的中途退出 枚举法 贪婪法,for循环语句,格式： for（表达式1；表达式2；表达式3）语句执行过程： 1.执行表达式1 2.执行表达式2 3.如果表达式2的结果为“true”，则执行循环体和表达式3，然后回到2，否则for语句执行结束,循环体,循环控制行,for循环语句 续,作为计数循环，可以理解为 for(循环变量赋初值；循环条件；循环变量增值)符合循环条件时的执行语句 循环体所有语句的一次完全执行称为一个循环周期 循环体可以是复合语句或空语句,逗号表达式,格式：表达式1，表达式2，,表达式n 执行过程：先执行表达

2、式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也不一定是

3、关系表达式。它可以是逻辑表达式，甚至可以是算术表达式。当表达式2是算术表达式时，只要表达式的值为非0，就执行循环体，表达式的值为0时退出循环。 如果表达式2省略，即不判断循环条件，循环将无终止地进行下去。 无终止的循环称为“死循环” 最简单的死循环是 for (;); 要结束一个无限循环，必须从键盘上输入特殊的命令以中断程序执行并强制退出,For循环的进一步讨论 续,表达式3也可以是任何表达式，一般为赋值表达式或逗号表达式。表达式3是在每个循环周期结束后对循环变量的修正。表达式3也可以省略，此时做完循环体后直接执行表达式2。 如从1加到100，可以写为s=0; for (i=1; i=100;

4、 ) s += i, i+; 或s=0; for (i=1; i=100; s += i, i+) ;,For循环实例,求函数 在区间a, b之间的定积分 实现思想：函数与x轴围成的区域的面积。定积分可以通过将这块面积分解成一连串的小矩形，计算各小矩形的面积的和而得到,int 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 en

5、dl; return 0; ,第4章 循环控制,重复N次循环 While循环 Do while循环 循环的中途退出 枚举法 贪婪法,While 循环语句,格式：while （表达式） 语句 执行过程：先计算出条件表达式的值。如果是false，循环终止，并接着执行在整个while循环之后的语句。如果是true，整个循环体将被执行，而后又回到while语句的第一行，再次对条件进行检查。 用途：用于循环次数不定的循环。循环是否结束取决于某一个条件是否成立,eg 2.求,时结束。,ex=0; p = 1; while (p0.000001) ex += p;计算新的p；,问题： 如何计算p？计算第i个

6、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; ,第4章 循环控制,重复N次循环 While循环 Do while循环 循环的中途退出 枚举法 贪婪法,DoWhile 循环语句,格式： do

7、语句 while (表达式) 执行过程：先执行循环体，然后判断循环条件。如条件成立，继续循环，直到条件为假 如将若干个输入数相加，直到输入0为止。total = 0;do cout value ;total += value; while (value != 0);,编程实例,计算方程f(x)在区间a, b之间的根 。注意，f(a)和f(b)必须异号 假设方程为 ，区间为-1, 1,计算方法,令x1 = a, x2 = b 连接(x1, f(x1)和(x2, f(x2)的弦交与x轴的坐标点可用如下公式求出若f(x)与f(x1)同符号，则方程的根在(x, x2)之间，将x作为新的x1。否则根在(

8、x1, x)之间，将x设为新的x2。 重复步骤和，直到f(x)小于某个指定的精度为止。此时的x为方程f(x)=0的根。,int 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

9、 = x; else x2 = x; while (fabs( fx ) 1e-7);cout “方程的根为：“ x endl;return 0; ,第4章 循环控制,重复N次循环 While循环 Do while循环 循环的中途退出 枚举法 贪婪法,循环的中途退出,考虑一个读入数据直到读到标志值的问题。如用自然语言描述，基于标志的循环的结构由以下步骤组成： 读入一个值 如果读入值与标志值相等，则退出循环 执行在读入那个特定值情况下需要执行的语句 当一个循环中有一些操作必须在条件测试之前执行时，称为循环的中途退出问题。,问题,由于循环语句是先判断条件再决定是否执行循环体，循环的中途退出将使得循

10、环体中的某些语句必须重复出现。 基于标志的循环结构被改为： 读入一个值 While （读入值与标志值不相等） 执行在读入那个特定值情况下需要执行的语句读入一个值,解决方案,break语句：跳出循环 上述问题可以用下列方案解决： while (true) 提示用户并读入数据if (value=标志) break;根据数据作出处理 continue语句：跳出当前循环周期,第4章 循环控制,重复N次循环 While循环 Do while循环 循环的中途退出 枚举法 贪婪法,枚举法,对所有可能的情况一种一种去尝试，直到找到正确的答案。 枚举法的实现基础是循环。,枚举法实例一,用50元钱买了三种水果。各

11、种水果加起来一共100个。西瓜5元一个，苹果1元一个，桔子1元3个，设计一程序输出每种水果各买了几个 它有两个约束条件： 第一是三种水果一共100个； 第二是三种水果一共花了50元 可以按一个约束条件列出所有可行的情况，然后对每个可能解检查它是否满足第二个约束条件 。也可以用第二个约束条件列出所有情况，然后对每个可能解检查它是否满足第一个约束条件 。,#include using namespace std;int main() int mellon, apple, orange; /分别表示西瓜数、苹果数和桔子数for (mellon=1; mellon10; +mellon) / 对每种可

12、能的西瓜数for ( apple=1; apple 50 - 5 * mellon; +apple) /当西瓜数给定后可能的苹果数orange = 3*(50-5*mellon-apple); / 剩下的钱全买了桔子if (mellon+apple+orange = 100) / 三种水果数之和是否为100cout “mellon:“ mellon ;cout “apple:“ apple ;cout “orange:“ orange endl; return 0;,执行结果,Mellon：1 apple：18 orange：81 Mellon：2 apple：11 orange：87 Mel

13、lon：3 apple：4 orange：93,实例二 四大湖问题,上地理课时，四个学生回答我国四大湖的大小时分别说：甲：洞庭最大，洪泽最小，鄱阳第三乙：洪泽最大，洞庭最小，鄱阳第二，太湖第三丙：洪泽最小，洞庭第三丁：鄱阳最大，太湖最小，洪泽第二，洞庭第三 对于每个湖的大小，每个人仅答对一个，设计一程序让计算机通过这些信息去判别四个湖的大小。,解题思路,如果用a,b,c,d分别表示四个湖的排序。a表示洞庭湖，b表示洪泽湖，c表示鄱阳湖，d表示太湖。我们可以假设：洞庭最大，洪泽第二，鄱阳第三，太湖第四，然后检查每位同学是否都讲对了一个。如果不是，再尝试下一种情况：洞庭最大，洪泽第二，鄱阳第四，太

14、湖第三，再检查每位同学是否都讲对了一个。尝试所有可能的情况，直到满足每位同学都讲对一个为止。,枚举法续,为了尝试所有情况，我们需要假设洞庭湖可能是最大，也可能是第二、第三或第四。因此，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) co

15、ntinue;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

16、 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;

17、else cout c1 c2 c3 endl; ,第4章 循环控制,重复N次循环 While循环 Do while循环 循环的中途退出 枚举法 贪婪法,贪婪法的基本思想,在求解过程的每一步都选取一个局部最优的策略，把问题规模缩小，最后把每一步的结果合并起来形成一个全局解。 基本步骤： 从某个初始解出发 采用迭代的过程，当可以向目标前进一步时，就根据局最优策略，得到一个部分解，缩小问题规模。 将所有解综合起来,硬币找零问题,对于一种货币，有面值为1分, 2分, 5分和1角的硬币，最少需要多少个硬币来找出K分钱的零钱。,贪婪法解题思想,不断地使用面值最大的硬币。如要找零的值小于最大的硬币值，则尝

18、试第二大的硬币。依此类推。 不断尝试的过程就是循环,#include using 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) fiv

19、efen+; 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 基于循环的算法： 枚举法：对某些问题，在寻找它的解时需要检查所有的可能的方案，从中找出可行解。 贪婪法：可用于求问题的最优解。但不一定对所有问题都能得到最优解。,