1 第 3 章 C++ 中的条件与循环 第 3 次见面！ acm.nefu.edu.cn/C++_03.ppt.

Presentation on theme: "1 第 3 章 C++ 中的条件与循环 第 3 次见面！ acm.nefu.edu.cn/C++_03.ppt."— Presentation transcript:

1 1 第 3 章 C++ 中的条件与循环 第 3 次见面！ acm.nefu.edu.cn/C++_03.ppt

2 2 这 2 天你们 C++ 吗？ 一夜北风寒，万里彤云厚； 长空雪乱飘，改尽江山旧。 仰面观太虚，疑是玉龙斗； 纷纷鳞甲飞，顷刻遍宇宙。 骑驴过小桥，独叹梅花瘦！ 谁知道出自 ------ ？ 是 李白 吗？

3 上次实验课总结 1 、注意汉字和英文的输入法； 2 、 endl 不是 end1; 3 、时时刻刻使用 C++ 的基本框架 3

4 上机调试的心得（授之以渔） 1 、哪行出错了 2 、提示的字符是啥 3 、是不是自己敲错了 4 、缺头文件吗？ was not declared in this scope 5 、结构，大括号，大小写 6 、然后才是真的逻辑出错了 4

5 先学习 C++ 实验的在线评测系 统 记住网址： acm.nefu.edu.cn 5

6 6

7 注册 register 7

8 Problem 题目 8

9 如何做题 先看题，如 “ 寻找吕布 ” 这题； description 三国里面吕布第一，赵云第二，典韦、 关羽和马超分别是第 3 、第 4 和第 5 名，这 是按武将的勇猛值和必杀技值的和来排 名的，即武术值 = 勇猛值 + 必杀技值，下 面给出这 5 人的勇猛值和必杀值，请你找 出吕布的武术值。 9

10 寻找吕布 input 输入数据有多组，每组数据 2 行，第一行 是 5 人的勇猛值，第二行是 5 人的必杀技 值。勇猛值和必杀值是整数哦（ 32 位） output 输出吕布的武术值。 10

11 sample_input 1 2 3 4 5 20 21 22 45 87 1 100 8 99000 23 sample_output 10 99087 hint 吕布的勇猛值和必杀技值都是第一的！ 11

12 #include using namespace std; int main() { int data[6],inp[6];// 定义变量 int ym,bs;// 勇猛值 必杀值的变量 while(cin>>data[1]>>data[2]>>data[3]>>data[4]>>data[5])// 注意 { ym=0,bs=0; // 这句很重要，必须先清 0 for(int i=1;i<=5;i++) if (ym<data[i]) ym=data[i]; cin>>inp[1]>>inp[2]>>inp[3]>>inp[4]>>inp[5]; for(int i=1;i<=5;i++) if (bs<inp[i]) bs=inp[i]; cout<<ym+bs<<endl; } //cout << “Hello world!” << endl; 记得要注视掉啊 return 0; } 12

13 再看服务器里的数据 data.in 输入文件 data.out 输出文件 1 2 3 4 5 10 1 2 3 4 5 99087 20 21 22 45 87 16 1 100 8 99000 23 1 2 6 8 9 7 4 3 2 1 你不知道服务器的数据是啥！ 13

14 提交答案 : 题目下面 submit 14

15 看评判结果 15

16 欢迎有敏感的人加入 ACM 数学好 算法好（可以培养） 能吃苦就行 16

17 条件语句 if switch 和 C 语言一样，基本知识不变 通过实例来讲解 17

18 条件表达式 ？：运算符 ：问号冒号运算符 作用：更加简练的用来表达条件执行的方式 形式 ： ( 条件 ) ? 表达式 1 : 表达式 2 执行过程：首先计算条件值。如果条件结果为 true ，则计算表达式 1 的值，并将它作为整个表 达式的值。如果条件结果为 false ，则整个表达 式的值为表达式 2 的值。

19 实例 例如将 x 和 y 中值较大的一个赋值给 max ，可以用下列语句： max = (x > y) ? x : y; ？：运算符用于输出。例如，想输出一个布尔变量 flag 的值， 如果直接用 cout << flag; 那么当 flag 为 “ 真 ” 时，输出为 1 ；当 flag 为 “ 假 ” 时，输出为 0 。 如果我们想让 flag 为 “ 真 ” 时输出 true ，为 “ 假 ” 时输出 false ，可以 用 if 语句 if (flag) cout << “true”; else cout << “false”; 看上去太罗嗦。但如果用？：运算符只需要一行 cout << ( flag ? "true" : "false" ) << endl;

20 判断闰年的程序 #include using namespace std; int main() { int year; bool result; cout << " 请输入所要验证的年份： "; cin >> year; result = (year % 4 == 0 && year % 100 !=0)|| year % 400 == 0; if (result) cout << year << " 是闰年 " << endl; else cout << year << " 不是闰年 " << endl; return 0; }

21 计算机自动出四则运算计算题 生成题目 Switch( 题目类型 ) { case 加法：显示题目，输入和的值，判断正确与否 case 减法：显示题目，输入差的值，判断正确与否 case 乘法：显示题目，输入积的值，判断正确与否 case 除法：显示题目，输入商和余数的值，判断正确与否 } 要求自动出 0 - 9 之间的四则运算题，并批改结果

22 关键问题 如何让程序每次执行的时候都出不同的题目？ 随机数生成器 rand() ：能随机生成 0 到 RAND_MAX 之间的整型数 将生成的随机数映射到 0 - 9 之间： –Rand() % 10 –rand() * 10 / (RAND_MAX + 1) 。 运算符的生成：用编码 0 - 3 表示四个运算符。因 此题目的生成就是生成 0 - 3 之间的随机数。

23 随机数的种子 计算机产生的随机数称为伪随机数，它是根据一个 算法计算出来的。 系统为每个程序、每次执行指定的随机数的种子都 是相同的，因此程序每次执行生成的随机数序列都 是相同的。 rand() 种子 12348

24 改变随机数的种子 设置种子的函数 srand ： srand （种子） 如何让程序每次执行时选择的种子都不一 样呢 ? 选择系统时间为种子： time(NULL) 取当前 的系统时间。

25 #include // 包含伪随机数生成函数 #include // 包含取系统时间的函数 #include using namespace std; int main() { int num1, num2, op, result1, result2; //num1,num2: 操作数， op: 运算符， result1,result2: 结果 srand(time(NULL)); // 随机数种子初始化 num1=rand() * 10 / (RAND_MAX + 1); // 生成运算数 RAND_MAX=32767 num2=rand() * 10 / (RAND_MAX + 1); // 生成运算数 op=rand() * 4 / (RAND_MAX + 1); // 生成运算符 0--+ ， 1-- - ， 2--* ， 3-- / 自动出题程序

26 switch (op) {case 0: cout > result1; if (num1 + num2 == result1) cout << "you are right\n"; else cout << "you are wrong\n"; break; case 1: cout > result1; if (num1 - num2 == result1) cout << "you are right\n"; else cout << "you are wrong\n"; break; case 2: cout > result1; if (num1 * num2 == result1) cout << "you are right\n"; else cout << "you are wrong\n"; break;

27 case 3: cout << num1 << "/" << num2 << "= ?" ; cin >> result1; cout > result2; if ((num1 / num2 == result1) && (num1 % num2 == result2)) cout << "you are right\n"; else cout << "you are wrong\n"; break; } return 0; }

28 该程序的缺陷 每次执行只能出一道题 减法可能出现负值 除法可能出现除 0 结果太单调

29 再看循环结构 For 基本的习惯 While 用处 Do while 29

30 For 循环实例 某班级有 100 个学生，设计一程序统计该班 级某门考试成绩中的最高分、最低分和平 均分。 方案一：先输入 100 个整型数，保存在各自 的变量中。然后依次检查这 100 个数，找出 最大的和最小的。在找的过程中顺便可以 把所有的数都加起来。最后将总和除 100 就 得到了平均值。

31 方案一的缺陷 需要定义 100 个变量 需要输入 100 个变量的值 从 100 个变量中找出最大者，需要 100 个 if 语句 从 100 个变量中找出最小者，需要 100 个 if 语句 将这 100 个变量加起来需要一个长长的算 术表达式

32 方案二 每个学生的分数在处理过后就没用了， 为此，可以用一个变量保存当前正在处 理的分数 每次输入分数的同时将它们加起来： 70 加 40 等于 110 ， 110 加 80 等于 190…… 。并 记住最低分的和最高分的值。上述过程 重复 100 次。

33 方案二的实现 定义： int value, total ， max, min; 当输入每个数值时必须执行下面的步骤，这可 以用 for 循环实现 – 请求用户输入一个整数值，将它存储在变量 value 中 。 – 将 value 加入到保存当前和的变量 total 中。 – 如果 value 大于 max ，将 value 存于 max 。 – 如果 value 小于 min ，将 value 存于 min 。

34 #include using namespace std; int main() { int value, total, max, min, i;//value ：当前输入数据， i 为循环变量 total = 0; max = 0; min = 100; // 变量的初始化 for (i=1; i<=100; ++i) { cout > 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; }

35 For 循环实例 求函数 在区间 [a, b] 之间的定积分 实现思想：函数与 x 轴围成的区域的面积。定积分 可以通过将这块面积分解成一连串的小矩形，计算 各小矩形的面积的和而得到 ab

36 int main() { double a, b, dlt, integral = 0; cout << " 请输入定积分的区间： " ; cin >> a >> b; cout << " 请输入小矩形的宽度： " ; cin >> dlt; for (double x = a + dlt / 2; x < b; x += dlt) integral += (x * x + 5 * x + 1) * dlt; cout << " 积分值为： " << integral << endl; return 0; }

37 eg 2. 求时结束 。 ex=0; p = 1; while (p>0.000001) { ex += p; 计算新的 p ； } 问题： 如何计算 p ？计算第 i 个 p ，需 要两个 i 次的循环。第一个循 环计算 x i ，第二个循环计算 i ！ 解决方案： 从前一项计算后一项。如果 p 是第 i 项的值，则第 i+1 项的值 为 p*x/(i+1)

38 int main() {double ex, x, p;//ex 存储 e x 的值， 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; }

39 枚举法 对所有可能的情况一种一种去尝试，直 到找到正确的答案。 枚举法的实现基础是循环。

40 枚举法实例一 用 50 元钱买了三种水果。各种水果加起来一共 100 个。西瓜 5 元一个，苹果 1 元一个，桔子 1 元 3 个，设计一程序输出每 种水果各买了几个 它有两个约束条件： – 第一是三种水果一共 100 个； – 第二是三种水果一共花了 50 元 可以按一个约束条件列出所有可行的情况，然后对每个可 能解检查它是否满足第二个约束条件 。也可以用第二个约 束条件列出所有情况，然后对每个可能解检查它是否满足 第一个约束条件 。

41 #include using namespace std; int main() { int mellon, apple, orange; // 分别表示西瓜数、苹果数和桔子数 for (mellon=1; mellon<10; ++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; }

42 执行结果 Mellon ： 1 apple ： 18 orange ： 81 Mellon ： 2 apple ： 11 orange ： 87 Mellon ： 3 apple ： 4 orange ： 93

43 实例二 — 四大湖问题 上地理课时，四个学生回答我国四大湖的大小时分别说 ： 甲：洞庭最大，洪泽最小，鄱阳第三 乙：洪泽最大，洞庭最小，鄱阳第二，太湖第三 丙：洪泽最小，洞庭第三 丁：鄱阳最大，太湖最小，洪泽第二，洞庭第三 对于每个湖的大小，每个人仅答对一个，设计一程序让 计算机通过这些信息去判别四个湖的大小。

44 解题思路 如果用 a,b,c,d 分别表示四个湖的排序。 a 表示洞庭湖， b 表示洪泽湖， c 表示鄱阳湖， d 表示太湖。我们可以假 设：洞庭最大，洪泽第二，鄱阳第三，太湖第四，然 后检查每位同学是否都讲对了一个。如果不是，再尝 试下一种情况：洞庭最大，洪泽第二，鄱阳第四，太 湖第三，再检查每位同学是否都讲对了一个。尝试所 有可能的情况，直到满足每位同学都讲对一个为止。

45 枚举法 — 续 为了尝试所有情况，我们需要假设洞庭 湖可能是最大，也可能是第二、第三或 第四。因此， a 的值可能从 1 变到 4 。同样 ， b, c,d 的值也都可能从 1 变到 4 。为此， 我们需要一个控制结构，使 a, b, c, d 的值 能自动从 1 变到 4 。这种结构就是循环结 构。

46 四大湖排列问题的解 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; } 问题：效率差 解决方法：一旦找到答案 就应该结束

47 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 // 注意 &&((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;} } //break 只能退出当前循环体 改进版 1 ： 程序不够简练

48 main() { 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

49 列出 ABC 三个字母的全排列 解题思路： – 让第一个位置的值从 A 依次变到 C – 注意三个位置的值不能相同 可以用一个三层的嵌套循环实现，循环变量是 字符类型

50 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 == c1 || c3 == c2)) continue; else cout << c1 << c2 << c3 << endl; }

51 贪婪法的基本思想 在求解过程的每一步都选取一个局部最优 的策略，把问题规模缩小，最后把每一步 的结果合并起来形成一个全局解。 基本步骤： – 从某个初始解出发 – 采用迭代的过程，当可以向目标前进一步时， 就根据局最优策略，得到一个部分解，缩小问 题规模。 – 将所有解综合起来

52 硬币找零问题 对于一种货币，有面值为 1 分, 2 分, 5 分和 1 角的硬币，最少需要多少个硬币来找出 K 分钱的零钱。

53 贪婪法解题思想 不断地使用面值最大的硬币。如要找零 的值小于最大的硬币值，则尝试第二大 的硬币。依此类推。 不断尝试的过程就是循环

54 #include using namespace std; #define ONEFEN 1 #define TWOFEN 2 #define FIVEFEN 5 #define ONEJIAO 10 int main() { int money; int onefen = 0, twofen = 0, fivefen = 0, onejiao = 0; cout << " 输入要找零的钱（以分为单位）： "; cin >> money;

55 // 不断尝试每一种硬币 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; }

56 2016-9-656 例：用贪心法求解付款问题。 假设有面值为 5 元、 2 元、 1 元、 5 角、 2 角、 1 角的货币，需 要找给顾客 4 元 6 角现金，为使付出的货币的数量最少，首 先选出 1 张面值不超过 4 元 6 角的最大面值的货币，即 2 元， 再选出 1 张面值不超过 2 元 6 角的最大面值的货币，即 2 元， 再选出 1 张面值不超过 6 角的最大面值的货币，即 5 角，再选 出 1 张面值不超过 1 角的最大面值的货币，即 1 角，总共付出 4 张货币。

57 2016-9-657 在付款问题每一步的贪心选择中，在不超过应付款 金额的条件下，只选择面值最大的货币，而不去考虑在 后面看来这种选择是否合理，而且它还不会改变决定： 一旦选出了一张货币，就永远选定。付款问题的贪心选 择策略是尽可能使付出的货币最快地满足支付要求，其 目的是使付出的货币张数最慢地增加，这正体现了贪心 法的设计思想。

58 2016-9-658 思考题 Nefu 90 题 今年暑假不 AC

59 2016-9-659 “ 今年暑假不 AC ？ ” “ 是的。 ” “ 那你干什么呢？ ” “ 看世界杯呀，笨蛋！ ” “ @#$%^&*%... ” 确实如此，世界杯来了，球迷的节日也来了，估计很多 ACMer 也 会抛开电脑，奔向电视了。 作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的 好青年，你一定还会看一些其它的节目，比如新闻联播（永远不 要忘记关心国家大事）、非常 6+7 、超级女生，以及王小丫的《 开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的 转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目 ）

60 2016-9-660 Input 输入数据包含多个测试实例，每个测试实例的第一行 只有一个整数 n(n<=100) ，表示你喜欢看的节目的总数 ，然后是 n 行数据，每行包括两个数据 Ti_s,Ti_e (1<=i<=n) ，分别表示第 i 个节目的开始和结束时间，为 了简化问题，每个时间都用一个正整数表示。 n=0 表示 输入结束，不做处理。 Output 对于每个测试实例，输出能完整看到的电视节目的个 数，每个测试实例的输出占一行。

61 2016-9-661 输入： 1 2 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0 输出： 5

62 2016-9-662 先按结束时间排下序（从小到大） 1 3 0 3 2 5 6 4 10 8 15 15 3 4 7 8 9 10 12 14 15 18 19 20 竖着看！ 用心一算： 1 3 5 10 15 3 4 10 15 19 本题可以冒泡

63 int main() { int tmp,n,s,e,l[5],w[5]; n=4; for(int i=1;i<=4;i++ ) {cin>>l[i]; cin>>w[i];} for(int i=1;i<n;i++) // 这是对 2 个数组的冒泡，先排第 1 个位置，最小的 {tmp=i; for(int j=i+1;j<=n;j++) if (l[j]<l[tmp]) tmp=j; s=l[i];l[i]=l[tmp];l[tmp]=s; // 看好 e=w[i];w[i]=w[tmp];w[tmp]=e; // 跟着拍了 } for(int i=1;i<=4;i++ ) { cout<<l[i]<<" "<<w[i]<<endl; } return 0; } 63

64 64

65 暑假不 AC 的贪婪代码 #include using namespace std; int main() { int n; int inp_s[100],inp_e[100];// 开始，结束 2 个数组 int s_tmp,e_tmp; while(cin>>n) { if (n==0) break; for(int i=1;i<=n;i++) cin>>inp_s[i]>>inp_e[i]; 65

66 // 排序 int tmp=0; for(int i=1;i<=n-1;i++) { tmp=i; for(int j=i+1;j<=n;j++) if (inp_e[j]<inp_e[tmp]) tmp=j; e_tmp=inp_e[i],inp_e[i]=inp_e[tmp],inp_e[tmp]=e_tmp; s_tmp=inp_s[i],inp_s[i]=inp_s[tmp],inp_s[tmp]=s_tmp; } 66

67 输出结果 int sum=0; tmp=inp_e[1]; for(int i=2;i<=n;i++) { if (tmp<=inp_s[i]) {sum++; tmp=inp_e[i];} } cout<<sum+1<<endl; } //cout << "Hello world!" << endl; return 0; } 67

68 课后一定要练习之！ 68