摘要
本课开启本课程的第四单元,这一单元专讲流程控制。本课说明这一单元的用途:教人用判断和循环来掌控程序中语句的执行顺序,并对其正确性进行推理,也就是确保每一种情形都得到处理,每一个循环都做它应做的事,并且会终止;介绍本单元的四节课和贯穿它们的线索;回顾本单元假定已经掌握的内容,尤其是第三单元的复合条件;提出本单元要解决的问题,即一个用固定步数计算最大公因数的程序,它会因数据不同而给出错误的回答,或者停在一次除以零上;预先介绍不变式,即本单元用来论证其循环的工具;并说明本单元通向何处,包括后面各单元以及“C++ 程序设计 II”课程。
学习目标
- 描述本单元内容的先后顺序,并说明每一节课为紧随其后的那一节课提供了什么。
- 回忆第三单元的复合条件(逻辑联结词、短路求值以及按德摩根律取反),必要时加以复习。
- 借助一个例子,预先认识作为推理工具的不变式:一种在重复过程中保持不变、并在结束时给出结果的变量之间的关系。
- 认清学完本单元时应当会做的事,并把它与后面各单元将要学习的内容区分开来。
入门测评
在学习本单元之前,先测一测自己的起点是有益的。这项测评是自我测评:不计分,唯一的目的是为学习指引方向。前四道题检查本单元假定已经掌握的内容:复合条件的取反、短路求值、第 1.1 课中一个重复过程的跟踪,以及 int 的界限。其后的七道题按课的顺序涉及本单元的核心思想,其中有几道从学校数学出发:最大公因数、求和符号、一个过程的终止性。没有人必须现在就答对,其中有几道题里,“我还不知道”是诚实的回答:每个答案,无论对错,都会解释要点,并指出讲解这一要点的那节课。同样的能力会在单元末尾的总结课中再次测量。
开始本单元之前,先测一测你的起点。这是一次简短的自我测评:不计分,结果只保存在你的浏览器中。
第 1 题来自前面的单元条件
1 <= n && n <= 10的否定是什么?对每一部分都取了反,却保留了合取:忘了德摩根律。此外,没有任何数同时小于 1 又大于 10,所以这个条件总是假的。联结词换对了,关系却否定错了:多排除了边界 1 和 10,而它们满足原来的条件。只否定了第一部分。根据德摩根律,合取的否定是各个否定的析取,而1 <= n的否定是n < 1,不是n <= 1。本单元在每个判断链中都需要它,因为else分支处理的恰好是前面各条件的否定;在每个循环中也需要它,因为退出时成立的是其条件的否定。复习: 关系与逻辑
第 2 题来自前面的单元在
int d{0};和int n{5};之下,计算d != 0 && n / d > 2时会发生什么?忽略了短路求值:除法根本不会被计算。一个含有假操作数的合取不可能为真。这个表达式是正确的;编译器并不知道d在运行时的值。第一个操作数为假,短路求值不再计算第二个:左边的守卫保护了除法。本单元把这种守卫变成显式的判断,以及保护循环体的循环条件。复习: 关系与逻辑
第 3 题来自前面的单元第 1.1 课的连续减法求商从 和 开始,并重复“当 时,把 从 中减去,并给 加 1”。在 、 时,重复过程的循环体执行多少次?
数的是条件的计算次数,它比轮数多一。在 时就停止了重复:把 读成了 。把轮数与 的初始值混为一谈。跟踪得到 :循环体执行四次,而条件计算五次,因为最后一次计算正是结果为假的那一次。第 4.2 课用 C++ 写出这一重复过程,并把跟踪变成一张表。复习: 从问题到算法
第 4 题来自前面的单元对于 32 位的
int,标准对46341 * 46341的值作出了什么保证?忽略了类型的范围:这个数放不进int。以为溢出会停在边界上;标准什么也不承诺。结果的类型由操作数决定,而操作数是int,不由结果的值决定。最大值是 。本单元会在一个人们意想不到的地方遇到这个乘积:一个试除因数的循环的条件d * d <= n,它恰恰在 接近最大值时溢出。复习: 整数及其表示
第 5 题一个程序包含这样的判断链:
if (score >= 50),输出“及格”;else if (score >= 90),输出“优秀”;以及else,输出“不及格”。当score等于 95 时,它输出什么?以为最苛刻的条件胜出;胜出的是第一个成立的条件。以为所有为真的分支都会执行;在判断链中只执行一个。这是诚实的回答:第 4.1 课会解释它,结业测评还会回到判断链的边界上来。在判断链中执行的是第一个条件为真的分支,而 。“优秀”分支永远不会执行:它的实际情形是 且 ,这是空的。第 4.1 课教人读出每个分支的实际情形,并为条件排序。复习: 判断
第 6 题下面哪个表达式表示和 ?
把 个数 相加,即 :把项与上限混淆了。求的是 :挪动了界限,丢掉了最后一项,这正是循环中的差一错误。上限不能就是指标本身:这个表达式没有意义。指标 取遍从 1 到 的整数,每一项就是 本身。一个做累加的for循环正是这一记号的直接翻译:循环变量就是指标,它的界限就是求和的界限,循环体加上这一项。复习: 循环
第 7 题在
int total{0};之下,执行for (int i{0}; i < 5; ++i) { total += i; }之后,std::println("{}", total);输出什么?以为i会到达 5:把<读成了<=。把累加器与计数器混淆了:五是轮数,不是和。这是诚实的回答:第 4.2 课讲授for的形式以及如何数它的轮数。变量i依次取值 0、1、2、3 和 4,而 ;当i等于 5 时条件为假,循环体不执行。这就是上一道题中的求和,界限为 0 和 4。复习: 循环
第 8 题在连续减法求商中(,;当 时, 变为 , 变为 ),每次计算条件时,变量之间成立的是哪一个关系?
只在退出时成立:在重复过程中,条件保证的恰恰相反。只在结束时成立;在此之前, 小于商。这是诚实的回答:第 4.3 课教人找到并检验这个关系,结业测评还会再问。它在开始时成立,因为 ;如果它在某一轮之前成立,那么之后也成立,因为 。退出时再加上条件的否定 ,两者合起来就给出结果。这样的关系称为不变式,第 4.3 课把它变成设计循环并论证循环的方法。复习: 设计正确的循环
第 9 题一个过程从任意一个整数 (正数、零或负数)出发,重复“当 时,从 中减去 2”。它对每个 都会终止吗?
条件为 时才会这样;条件为 时,一旦 变为 0 或 ,重复就会停止。为负数时,条件从一开始就是假的,循环体不会执行。结论是对的,理由却不对:是整数并不够;还需要这个量在重复期间是自然数,并且不断递减。只要重复还在进行,量 就是自然数(由条件保证),并且严格递减:它是一个变式,即第 1.1 课的工具,第 4.3 课在每个循环中都要用到它。如果条件是“当 时”,答案就会改变:奇数的 会跳过零。复习: 设计正确的循环
第 10 题84 和 36 的最大公因数是多少?
它是公因数,但不是最大的。它是公因数,但不是最大的:缺少它们同样共有的因数 3。这是最小公倍数,不是最大公因数。公因数有 1、2、3、4、6 和 12。辗转相除法不用寻找因数就能得到它:,,因此 。第 4.4 课把它写成循环,并证明它为什么有效。复习: 数值算法
第 11 题要通过试除来判断 101 是否为素数,试到哪个因数就够了?
用的是一半:这是对的,但比必要的长五倍。试遍所有候选数:这是对的,但没有利用因数成对出现这一点。这是诚实的回答:第 4.4 课会证明它。如果 101 有一个因数 ,满足 ,那么 也是它的因数,而两者之中必有一个至多为 。只需试 2 到 10:没有一个能整除 101,所以它是素数。第 4.4 课证明这一规则,并且在写法中既不用开方,也不用会溢出的乘积。复习: 数值算法
正在加载内容…
已完成
登录账户以保存您的进度