上一课我们解决的是“一个变量现在是多少”本课要再向前走一步“程序接下来走哪条路要走多少遍最后会走到哪里”第五课 条件、循环与程序模拟——让计算机走迷宫程序到底会执行哪一条路一、本课学习目标① 看懂条件语句知道if else else if到底执行哪一部分。② 看懂循环能够判断for while到底执行多少次。③ 看懂break和continue知道程序什么时候提前结束循环什么时候跳过本轮循环④ 能够手工模拟程序看到for(...) { ... }不慌。拿出一张表ixy输出一行一行跑。⑤ 开始建立“程序流程图”最终形成条件决定方向循环决定次数变量记录状态。二、先给同学们讲一个故事假设我们正在玩一个迷宫游戏。角色走到一个路口会进行选择前面 ↑ | ┌─────┴─────┐ │ │ 下雨 不下雨 │ │ 带伞 不带伞计算机程序其实也经常在做类似的事情如果条件成立走这里如果不成立走那里。C中if (条件) { 做事情A; } else { 做事情B; }同学们可以理解成if就是“程序人生的岔路口”。三、第一关if——如果最简单的if (x 5) { cout 大; }意思是如果 x 大于5就输出“大”。例如int x 8; if (x 5) { cout 大; }因为8 5成立。所以输出大四、如果条件不成立呢int x 3; if (x 5) { cout 大; }判断3 5不成立。所以大括号里的代码{ cout 大; }一次都不执行。程序直接往后走。这点在程序阅读题中非常重要。五、if-else两条路选一条if (x 60) { cout 及格; } else { cout 不及格; }可以画成x 60 ? / \ 是 否 ↓ ↓ 及格 不及格所以if 和 else 是二选一。六、最重要的原则一次只走一条例如int x 80; if (x 60) { cout A; } else { cout B; }不能输出A B而是A因为if和else两个分支只会执行其中一个。七、else if——不止两个选择如果有多个情况if (score 90) { cout 优秀; } else if (score 80) { cout 良好; } else if (score 60) { cout 及格; } else { cout 不及格; }可以想象成90以上 ── 是 → 优秀 │ 否 ↓ 80以上 ── 是 → 良好 │ 否 ↓ 60以上 ── 是 → 及格 │ 否 ↓ 不及格八、else if最容易出现的错误比如int x 95; if (x 60) cout 及格; else if (x 90) cout 优秀;孩子可能认为95 ≥ 90所以优秀。实际上输出及格为什么程序先判断95 60成立。于是已经进入第一个分支。后面的else if (x 90)根本不会再判断。所以程序阅读时一定要记住if → else if → else是从上往下寻找第一个成立的条件。九、嵌套if例如int x 8; if (x 0) { if (x % 2 0) { cout 正偶数; } }程序实际上要经过两个问题x 0 ? ↓ 是 x % 2 0 ? ↓ 是 输出“正偶数”十、程序模拟的第一个工具流程图以后看到if (条件) { A; } else { B; } C;可以画成条件 / \ 真 假 ↓ ↓ A B \ / ↓ ↓ C注意A和B只能执行一个。十一、第二关for——重复做事情假设老师说“请你拍5次手。”你可能会写拍手 拍手 拍手 拍手 拍手计算机当然也能这样写但太麻烦。于是有for (int i 1; i 5; i) { cout 拍手; }意思从i1开始只要i5就执行一次然后i。十二、for循环的三个部分这是 CSP-J 必须掌握的。for (初始化; 条件; 更新) { 循环体; }例如for (int i 1; i 5; i) { cout i ; }分成初始化i 1 条件i 5 更新i十三、for到底怎么执行这要真正了解。例如for (int i 1; i 3; i) { cout i ; }千万不要背“循环3次。”我们真正要知道的是它怎么走。第一步初始化i 1第二步判断条件i 3 1 3成立。执行循环体输出1第三步更新i于是i 2第四步再次判断2 3成立。输出2然后i 3第五步3 3成立。输出3然后i 4第六步4 3不成立。循环结束。所以输出1 2 3十四、把for记成“四步法”以后所有for循环都按这个顺序初始化 → 判断 → 执行 → 更新然后判断 → 执行 → 更新不断重复。这是程序模拟的核心。十五、一个非常重要的例子for (int i 1; i 5; i) { cout i; }同学们不要只记“循环5次。”而应该知道i1 → 执行 i2 → 执行 i3 → 执行 i4 → 执行 i5 → 执行 i6 → 停止所以循环体执行了5次。十六、循环不一定从1开始例如for (int i 5; i 10; i) { cout i ; }输出5 6 7 8 9 10也可以for (int i 10; i 1; i--) { cout i ; }输出10 9 8 7 6 5 4 3 2 1所以不要看到for就默认从1增加。一定要看三个部分。十七、甚至可以跳着走例如for (int i 0; i 10; i 2) { cout i ; }执行0 2 4 6 8 10再例如for (int i 10; i 0; i - 2)就是10 8 6 4 2 0十八、循环次数怎么算例如for (int i 1; i 100; i)执行100次。但是for (int i 0; i 100; i)也是100次。因为0,1,2,...,99一共100个数。这是初赛非常喜欢考的地方。十九、i n和i n一定要非常敏感。例如for (int i 1; i 5; i)i1 2 3 4共4次。而for (int i 1; i 5; i)i1 2 3 4 5共5次。所以和只差一个等号却可能改变答案。二十、第三关while除了forC还有while例如int i 1; while (i 5) { cout i ; i; }输出1 2 3 4 5二十一、while和for的区别forfor (初始化; 条件; 更新) { 循环体; }while初始化; while (条件) { 循环体; 更新; }例如for (int i1; i5; i) cout i;大致可以改成int i1; while (i5) { cout i; i; }所以可以告诉孩子for和while本质上都是“重复做事情”。二十二、while最大的危险死循环看看int i 1; while (i 5) { cout i; }这里有什么问题i永远是1条件1 5永远成立。所以程序永远循环下去。这叫死循环二十三、如何避免死循环通常要让循环变量发生变化。例如int i 1; while (i 5) { cout i; i; }变化1 → 2 → 3 → 4 → 5 → 6到6以后6 5不成立。循环结束。二十四、do while还有一种do { 循环体; } while (条件);它和while最大的区别do while至少执行一次。例如int i 10; while (i 5) { cout i; }一次都不执行。因为一开始10 5就是假。但是int i 10; do { cout i; } while (i 5);会先输出一次10。然后再判断10 5发现是假结束。二十五、三种循环放在一起循环判断时间至少执行几次for执行前判断0while执行前判断0do while执行后判断1二十六、第四关breakbreak可以理解成“不玩了直接退出这个循环”例如for (int i 1; i 10; i) { if (i 5) break; cout i ; }执行1 2 3 4当i 5成立break;直接跳出循环。所以不会输出5 6 7 8 9 10二十七、break的核心含义记住break 彻底离开当前循环。不是“跳过这一次。”而是“以后都不循环了。”二十八、第五关continuecontinue和break很容易混。例如for (int i 1; i 5; i) { if (i 3) continue; cout i ; }输出1 2 4 5为什么当i3遇到continue;意思是这一轮不做了进入下一轮。所以1 → 输出 2 → 输出 3 → 跳过 4 → 输出 5 → 输出二十九、break和continue必须区分语句含义break彻底退出循环continue跳过本轮继续下一轮可以用上课时的比喻break“下课所有人回家”continue“这道题不做下一题继续。”三十、程序模拟的核心方法现在开始真正进入 CSP-J 程序阅读。看到程序int x 0; for (int i 1; i 5; i) { x x i; } cout x;不要直接猜。拿纸画ix初始0112336410515最后15三十一、这张表非常重要我建议同学们要画“程序状态表”例如int x 2; for (int i 1; i 4; i) { x x * 2; }画执行阶段ix初始—2第1轮14第2轮28第3轮316第4轮432答案32三十二、为什么程序模拟不能只靠脑算因为当程序变复杂以后int x 0; int y 1; for (int i 1; i 5; i) { x x y; y y * 2; }脑子很容易乱。所以画ixy初始011122343784151653132最后x31 y32三十三、条件 循环例如int x 0; for (int i 1; i 10; i) { if (i % 2 0) x x i; } cout x;问题输出什么先不要算答案。观察程序i1 → 奇数 → 不加 i2 → 偶数 → 加2 i3 → 奇数 → 不加 i4 → 偶数 → 加4 ...所以实际上计算的是246810结果30三十四、这个程序考了什么一道看似简单的题其实同时考for if % 变量更新 程序模拟这就是 CSP-J 初赛非常典型的题目。三十五、再来一个经典程序int x 0; for (int i 1; i 10; i) { if (i % 2 1) x; } cout x;这里i % 2 1表示i是奇数。1、3、5、7、9一共5个。所以x5三十六、程序模拟的“四步法”以后同学们看到程序可以严格按照这个顺序第一步找变量例如int x 0; int sum 0;先记下来x0 sum0第二步找条件例如if (x % 2 0)问什么情况下进入第三步找循环例如for (int i1; in; i)先搞清i到底取哪些值第四步建立状态表每一轮记录i x sum不要怕写草稿。三十七、嵌套循环这是程序阅读的第二个大坎。例如for (int i 1; i 3; i) { for (int j 1; j 2; j) { cout i , j endl; } }外层i1 i2 i3每一个i内层j都重新从1开始j1 j2所以输出1,1 1,2 2,1 2,2 3,1 3,2三十八、同学们容易犯的错误有的同学会错误地认为i1 → j1,2 i2 → j3,4 i3 → j5,6这是错的。因为for (int j 1; j 2; j)每进入一次外层循环j都会重新初始化为1。所以一定是i1j1,2 i2j1,2 i3j1,2三十九、嵌套循环的状态表可以画成ij执行11√12√21√22√31√32√一共3 * 2 6次。这也为下一阶段的时间复杂度埋下伏笔。讲义中对嵌套循环的分析也正是采用“最内层循环体作为基本语句”的思路。四十、嵌套循环 条件再看int sum 0; for (int i 1; i 3; i) { for (int j 1; j 3; j) { if (i j) sum; } }什么时候sum只有ij所以(1,1) (2,2) (3,3)一共3次。答案sum3四十一、break放在嵌套循环里怎么办这是一个经常考察的初赛陷阱。for (int i 1; i 3; i) { for (int j 1; j 5; j) { if (j 3) break; cout j ; } }每次外层循环j1 → 输出 j2 → 输出 j3 → break所以每次只输出1 2一共三次1 2 1 2 1 2关键break只跳出它所在的那一层循环。四十二、continue放在循环中例如int sum 0; for (int i 1; i 5; i) { if (i 3) continue; sum i; }执行i1 → sum1 i2 → sum3 i3 → 跳过 i4 → sum7 i5 → sum12答案12四十三、一个重要的程序阅读模型以后可以把程序想象成开始 ↓ 初始化 ↓ 判断 ↙ ↘ 不成立 成立 ↓ ↓ 结束 执行 ↓ 更新 ↓ 再判断这就是循环。所以循环其实就是一条“回来再走一次”的路。四十四、综合例题请看int x 0; for (int i 1; i 10; i) { if (i % 3 0) { x x i; } else { x x - 1; } } cout x;我们不要直接算。建立状态表i条件i%30x初始—01假-12假-23真14假05假-16真57假48假39真1210假11最后11四十五、再提高一点循环变量不一定只控制自己例如int i 1; int sum 0; while (i 10) { sum i; i 2; }那么i1 i3 i5 i7 i9所以sum13579答案25这告诉大家不要看到while(i10)就认为一定循环10次。真正决定循环次数的是i 到底怎样变化。四十六、程序阅读最重要的一个问题以后每看到一个循环都问“这个变量下一次会变成什么”例如i;那么i → i1如果i 2;那么i → i2如果i * 2;那么i → 2i如果i / 2;那么i → i/2这会直接影响循环次数。四十七、特别重要循环变量也可以被循环体改变例如for (int i 1; i 10; i) { i; }孩子可能认为循环10次。其实不是。每轮有两次增加循环体i 循环更新i所以1 → 2 → 3 → 4 → 5 → ...实际变化速度更快。最终i1 i3 i5 i7 i9 i11结束。所以循环体里面修改循环变量是程序阅读题非常值得警惕的地方。四十八、这一课和下一课“时间复杂度”有什么关系我们先埋一个伏笔。例如for (int i 1; i n; i) { cout i; }同学们现在首先应该知道循环体大约执行 n 次。后面学习算法复杂度就会进一步得到O(n)再例如for (int i 1; i n; i) { for (int j 1; j n; j) { cout ij; } }现在先知道外层 n 次每次内层 n 次。所以n * n n^2后面就能理解O(n^2)也是从“基本语句执行次数”出发再得到大 O。四十九、CSP-J程序阅读的“六步法”以后每一道程序阅读题同学们按照这套流程做。第1步找初始值int x0; int y1;写下来。第2步找条件if (x y)问什么情况下走这里第3步找循环变量for(int i1;in;i)写i1,2,3,...,n第4步找变量变化比如sum i;知道sum会不断增加第5步画状态表例如ixsum123245368第6步最后再看输出cout ...最后才回答输出什么五十、这一课的“知识地图”条件与循环 │ ├── 条件 │ ├── if │ ├── if-else │ ├── else if │ └── 嵌套 if │ ├── 循环 │ ├── for │ ├── while │ └── do while │ ├── 循环控制 │ ├── break │ └── continue │ └── 程序模拟 ├── 找变量 ├── 找条件 ├── 找循环 ├── 看变量变化 └── 画状态表五十一、本课十大易错点#易错点正确理解1if和else都执行二选一2else if全部判断找到第一个成立的就结束3for先执行循环体先判断条件4i5和i5一样不一样5while至少执行一次错可能0次6do while可能0次错至少1次7break跳过本轮错是退出循环8continue退出循环错是跳过本轮9嵌套循环里的j一直增加每次外层循环通常重新初始化10循环次数只看条件还要看变量如何变化五十二、课堂练习同学们先自己做再讲解。题1条件int x 8; if (x 10) cout A; else cout B;输出什么题2多个条件int x 85; if (x 90) cout A; else if (x 80) cout B; else if (x 60) cout C; else cout D;输出什么题3循环int sum 0; for (int i 1; i 5; i) sum i; cout sum;题4奇数int sum 0; for (int i 1; i 10; i) { if (i % 2 1) sum i; } cout sum;题5breakint sum 0; for (int i 1; i 10; i) { if (i 6) break; sum i; } cout sum;题6continueint sum 0; for (int i 1; i 5; i) { if (i 3) continue; sum i; } cout sum;题7嵌套循环int sum 0; for (int i 1; i 3; i) { for (int j 1; j 2; j) { sum; } } cout sum;题8综合模拟int x 1; for (int i 1; i 5; i) { if (i % 2 0) x * 2; else x 1; } cout x;必须画i条件x初始—11奇数?2偶数?3奇数?4偶数?5奇数?五十三、给大家留一道“挑战题”最后给一道稍微有挑战性的int x 0; for (int i 1; i 20; i) { if (i % 3 0) x i; else if (i % 2 0) x - i; else x; } cout x;要求第一步写出i1~20第二步判断每个i属于哪一种能被3整除 否则能被2整除 否则第三步做状态表i情况x变化x初始——01其他112偶数-2-133的倍数32…………五十四、这一课教给大家的不只是if和for如果你掌握了if是条件语句for是循环语句while是循环语句。那么这节课其实只完成了20%。真正大家应该形成的是“程序是一条路。”程序运行的时候遇到 if ↓ 选择一条路 ↓ 遇到循环 ↓ 重复走这条路 ↓ 遇到 break ↓ 离开这条路 ↓ 遇到 continue ↓ 跳过这一段重新走因此程序阅读的本质就是追踪程序的运行轨迹。最后给同学们一句口诀看到 if先判断看到 for找范围看到 while看变化看到 break直接走看到 continue本轮停遇到复杂程序别心算画状态表