程序设计 cs.sjtu 2011.9程序设计 - 1第第4章章 循环控制循环控制 重复重复N次循环次循环While循环循环Do while循环循环循环的中途退出循环的中途退出枚举法枚举法贪婪法贪婪法程序设计 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(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;s=0; for (i=1; i=100; +i) s += i; 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基于循环的算法：基于循环的算法：枚举法：对某些问题，在寻找它的解时需要检查枚举法：对某些问题，在寻找它的解时需要检查所有的可能的方案，从中找出可行解。所有的可能的方案，从中找出可行解。贪婪法：可用于求问题的最优解。但不一定对所贪婪法：可用于求问题的最优解。但不一定对所有问题都能得到最优解。有问题都能得到最优解。