跳至内容
Topos Uranos
中文 (中国)

从问题到算法

摘要

本课不含代码，这并非疏忽：算法先于程序，不会精确描述该做什么的人，用 C++ 也同样说不出来。首先学习如何规约一个问题，也就是声明它接收哪些数据、必须给出什么结果、以及二者之间由什么关系联系起来，并说明同一个题述可以有不同的规格说明。然后把算法定义为有穷、确定而通用的过程，并用编号步骤写出逐次相减的除法算法。接着学习用跟踪表手工执行算法，在整个课程中，跟踪表都将是理解程序和调试程序的第一件工具。最后介绍组合步骤的三种方式（顺序、选择和重复），任何算法都由它们写成，并学习借助一个每轮都减小、又不能无限减小下去的量，来论证一个重复会终止。

学习目标

  1. 规约一个简单的问题，指明它的输入、输出以及它们必须满足的条件。
  2. 用编号步骤描述算法，没有歧义，选择和重复都明确写出。
  3. 用跟踪表手工执行算法，并确定它对给定输入的结果。
  4. 在给定的过程中区分顺序、选择和重复，并论证一个重复会终止。

什么是计算问题

计算问题是两类数据之间的关系：一类是接收的数据，称为输入；另一类是必须给出的数据，称为输出。解决它并不是为某一个情形得到答案，而是掌握一种方法，对每个容许的输入都产生满足该关系的输出。“17 除以 5 是多少？”是一个提问；“给定两个整数，求它们的商和余数”是一个问题，因为它同时谈论所有的整数对。

然而，日常语言并不精确，同一个题述可以有多种理解。因此，在求解之前要先规约：写明输入什么、输出什么，以及各自必须满足什么条件。规格说明有三个部分。输入列出各项数据及其类别（整数、小数、单词）和对它们提出的条件，这些条件称为前置条件：使用解法的人承诺遵守它们。输出列出各项结果。关系，或称后置条件，说明输出相对于输入必须满足什么：编写解法的人承诺，只要前置条件得到遵守，就保证它成立。由此可知，规格说明是提出问题的人与解决问题的人之间的契约，而在前置条件之外，解法不作任何承诺。

例题三个数的最大值

日常题述：“找出三个数中最大的一个”。规格说明：

  • 输入：三个数 xx、yy、zz（整数或小数，没有其他条件）。
  • 输出：一个数 mm。
  • 关系：mm 是三个数据之一，并且其中没有一个大于 mm；也就是说，m≥xm \geq x、m≥ym \geq y 且 m≥zm \geq z。

这个关系并没有说“三者中最大的”，那恰恰是想要说清楚的东西；它给出的是两个可以检验的条件。第一个条件要求 mm 是数据之一（没有它，数 1000 对几乎任何输入都满足第二个条件）；第二个条件要求没有一个数据超过它。规格说明还顺带消除了题述留下的一个疑问：如果两个数据并列最大，如 (4,9,9)(4, 9, 9)，输出就是 99，其中没有任何错误。

同一个题述可以有不同的规格说明，在它们之间作出选择是一项决定，而不是疏忽。最有启发性的例子是整数除法。对于整数 a≥0a \geq 0 和 b>0b > 0，大家的意见一致：商 qq 和余数 rr 是满足下式的唯一一对整数

a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

这样，当 a=17a = 17、b=5b = 5 时，有 q=3q = 3、r=2r = 2，因为 17=5⋅3+217 = 5 \cdot 3 + 2。但是题述“两个整数相除”没有说明 aa 为负时怎么办，而这个问题并非无关紧要：当 a=−7a = -7、b=2b = 2 时，有两个合理的答案。

例题被除数为负时除法的两种规格说明

第一种规格说明：余数永不为负，0≤r<b0 \leq r < b。于是 −7=2⋅(−4)+1-7 = 2 \cdot (-4) + 1，输出为 q=−4q = -4，r=1r = 1。这是数学中研究的那一种，见“代数与几何 I”课程中的“整除与带余除法”一课。

第二种规格说明：商是带小数除法的结果去掉小数部分，即向零舍入；余数是差下的部分，其符号与被除数相同。于是 −7/2=−3.5-7 / 2 = -3.5 截断为 −3-3，并且 −7=2⋅(−3)+(−1)-7 = 2 \cdot (-3) + (-1)：输出为 q=−3q = -3，r=−1r = -1。

两者都满足 a=b⋅q+ra = b \cdot q + r；它们的区别在于对余数施加的条件。两者都不是错误，但一个程序如果用的是其中一种，却以为用的是另一种，遇到负数时就会给出错误的结果。先透露一点：C++ 采用的是第二种，这将在算术运算一课中看到；期待第一种的人会大吃一惊。

还有第三种选择，也是实践中最常见的：用前置条件把这种情形排除在外。如果规格说明要求 a≥0a \geq 0，负数的问题就消失了，不是因为它已被解决，而是因为使用解法的人已承诺不提出它。不能做的，是让这个问题悬而不决。出于同样的理由，规格说明要求 b>0b > 0：当 b=0b = 0 时，不存在满足关系的 qq 和 rr，契约必须说明这一点。

一个常见的错误是用例子来规约：“17 和 5 的输出是 3 和 2”。例子能说明问题，却不能规约问题，因为它没有说其他输入会怎样；无穷多个不同的关系都在同一个情形上重合。规格说明要写成一般的条件，例子则在之后用来检验它。

算法

问题一旦规约好，就要寻找求解的方法。算法是一列指令，把它应用于任何满足前置条件的输入，都会在有限步之内产生满足后置条件的输出。这个定义包含三项要求。

  • 有穷性。算法用有限条指令写成，并且对每个容许的输入，执行有限条指令之后就终止。一个对某个输入永远进行下去的过程，对那个输入而言不是算法。
  • 确定性。每条指令只有一种含义，执行者在任何时刻都知道该做什么、下一条指令是哪一条。没有任何决定留给执行者自行判断。
  • 通用性。算法对所有容许的输入解决问题，而不只是对某一个情形。

稍宽松地说，一个确定的、会终止、但对某个容许的输入不满足后置条件的过程，也被称为算法：严格地说，它是另一个问题的算法，对于所规约的问题，我们说它是不正确的。本课的问题就用这种说法，它们用反例来驳倒不正确的算法。

菜谱很像算法，所以它是常用的比喻；但几乎没有哪个菜谱真是算法。“加一撮盐”不确定，因为一撮不是一个数量；“烤到金黄”取决于一种判断，两个人会作出不同的判断；“搅打几次”没有说多少次。厨师用经验来填补这些空白；计算机却毫无经验。由此得出支配整个课程的要求：一个算法必须能让不理解问题的人照着执行，而无须猜测任何东西。如果执行一个步骤必须知道它的用途，这个步骤就写得不好。

本课程的算法首先用编号步骤、用中文写出，并遵循一些约定。在算法执行过程中会改变的数据用字母或单词命名，例如 qq 或 rr，称为变量。写“rr 取值为 r−br - b”，表示计算 r−br - b（用 rr 的当前值），其结果成为 rr 的新值；旧值丢失。在做笔记时使用的简写中，同一条指令用一个向左的箭头写出，在键盘上就是 r <- r - b。指令按编号顺序执行，除非其中某条另有规定。

例题逐次相减的除法

问题就是前一节规约的那个：输入，两个整数 a≥0a \geq 0 和 b>0b > 0；输出，两个整数 qq 和 rr，满足 a=b⋅q+ra = b \cdot q + r 且 0≤r<b0 \leq r < b。思路是分东西：只要还能分，就从 aa 中一组一组地取走 bb，数一数取走了多少组，剩下的就是余数。

  1. qq 取值为 00，rr 取值为 aa。
  2. 当 r≥br \geq b 成立时，重复步骤 3 和 4；当它不再成立时，转到步骤 5。
  3. rr 取值为 r−br - b。
  4. qq 取值为 q+1q + 1；回到步骤 2。
  5. 输出 qq 和 rr，然后终止。

步骤 2 是一个每次都要提出的问题：在第一轮之前，以及每一轮之后。步骤 3 和 4 构成重复的循环体，也就是被重复的部分。没有任何东西留给执行者自行判断：在每一时刻，下一条指令都只有一条。

这个算法很慢（一百万除以三要进行三十多万轮），学校里教的除法要快得多；但它是正确的，而它的简单使它成为学习对算法进行推理的理想对象。课程将在算法的代价一课中回到正确的算法与高效的算法之间的区别。

最后，应当把算法与它的书写分开。逐次相减的除法算法，无论用中文、用图、用 C++ 还是用任何其他编程语言写出，都是同一个算法：决定它的是运算的序列，而不是文字。程序是用机器能够执行的语言写出的算法，程序、编译器与 C++一课将说明这种执行是怎样发生的。如果是这样，一个程序可能以两种截然不同的方式出错：一是算法不正确，这时任何语言都救不了它；二是算法正确，但写错了。区分这两种情形是调试工作的一半，所以本课程总是先写出算法。

手工执行算法

读一个算法并不足以知道它做什么；必须执行它。像机器那样手工执行它，不跳过步骤，也不猜测结果，是编程者最有用的本领：有了它，可以在写下算法之前检验算法，在运行程序之前预测程序的输出，并找出出错程序中的错误。

所用的工具是跟踪表：一列记录正在执行的步骤编号，每个变量一列，必要时再加一列记录求值的条件；每执行一个步骤占一行。每一行记下在该步骤中改变的变量的新值，没有改变的留空，于是一个变量的当前值就是它那一列中最后写下的值。条件连同其结果一起记下。

例题17 除以 5 的跟踪

我们以 a=17a = 17、b=5b = 5 跟踪逐次相减的除法。图中的箭头指出刚刚执行的步骤；虚线提醒步骤 4 回到步骤 2。

证明

  1. (q,r)=(0,17)(q, r) = (0, 17)

    步骤 1：赋初值。输入满足前置条件，因为 17≥017 \geq 0 且 5>05 > 0。

  2. (q,r)=(1,12)(q, r) = (1, 12)

    第一轮。在步骤 2 中检验得 17≥517 \geq 5，于是执行循环体：步骤 3 取走一组五个，步骤 4 把它计数。

  3. (q,r)=(2,7)(q, r) = (2, 7)

    第二轮：12≥512 \geq 5，循环体再执行一次。

  4. (q,r)=(3,2)(q, r) = (3, 2)

    第三轮：7≥57 \geq 5，循环体再执行一次。

  5. 17=5⋅3+2,0≤2<517 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5

    在步骤 2 中条件不成立，因为 2<52 < 5：算法转到步骤 5，输出 q=3q = 3 和 r=2r = 2。输出满足后置条件。

完整的表格有十二行：步骤 1，三轮各三行（步骤 2、3 和 4），不成立的那次检验，以及输出。

关于这张表有两点说明。第一：轮数等于商，33，而步骤 2 比循环体多执行了一次，共 44 次；这种形式的重复总是如此，因为最后一次检验正是不成立的那一次。第二：跟踪揭示了算法文本乍看之下没有说出的东西；如果 a<ba < b，例如 a=3a = 3、b=5b = 5，条件第一次就不成立，循环体一次也不执行，输出为 q=0q = 0，r=3r = 3，这是正确的，因为 3=5⋅0+33 = 5 \cdot 0 + 3。忘记重复一次也不执行的情形，是设计算法时最常见的错误之一，而用小输入进行跟踪就能发现它。

对一个情形的跟踪并不能证明算法正确：它只检验了一个情形。但精心挑选的跟踪（一个常见情形、一个边界情形、重复一次也不执行的情形）能发现大部分错误，而出错的那次跟踪会指出错误在哪里。设计正确的循环一课将讲授如何从情形走向证明。

顺序、选择和重复

仔细看来，算法是用很少几种部件搭建起来的。有一些基本指令（给变量赋值、输出结果），以及组合它们的三种方式。

  • 顺序：一条指令接着一条指令，依次执行。除法的步骤 3 和 4 是一个顺序：先减，后数。
  • 选择：根据某个条件成立与否，执行这一部分或那一部分（或者执行一部分或什么都不执行）。“如果 y>my > m，则 mm 取值为 yy”是一个选择。
  • 重复：只要某个条件成立，就一遍又一遍地执行某一部分。除法的步骤 2 连同它的循环体是一个重复。

每种结构都只有一个入口和一个出口，而它的内部本身又可以是三者中的任何一种：重复的循环体可以包含选择，选择的一个分支可以包含重复，依此类推。如果是这样，用这三种结构就能搭建任意复杂的算法，正如用少数几种相互契合的部件可以建起任何建筑。这三种结构足以表达一切算法，这是程序设计理论中的一个著名结果（由科拉多·伯姆和朱塞佩·雅科皮尼于 1966 年证明）；这里不加证明，但整个课程都会印证它：课程中将要写的程序，无论多长，除了这三种结构之外不会用到别的东西，它们在 C++ 中写作 if（选择）以及 while 或 for（重复），分别见判断和循环两课。

观察算法结构的一种有用的记法是流程图：每条指令是一个矩形，每个条件是一个有两个出口的菱形（成立，图中标为 11；不成立，标为 00），箭头指明下一步是哪一步。它是一种记法，而不是目的：可以用来一眼看清一个小算法，但它不能扩展到大规模，没有人靠画图来写大程序。

例题三种结构及其组合

图中用一般性的指令 AA 和 BB 以及条件 cc 画出三种结构，然后把它们组合成逐次相减的除法的流程图。

证明

  1. A;BA ; B

    顺序：先执行 AA，再执行 BB；只有一个入口和一个出口。

  2. c=1⇒A,c=0⇒Bc = 1 \Rightarrow A, \quad c = 0 \Rightarrow B

    选择：若 cc 成立，执行 AA；否则执行 BB。两个分支汇合到同一个出口。

  3. c,A,c,A,…,cc, A, c, A, \ldots, c

    重复：对 cc 求值；若成立，执行 AA，然后再对 cc 求值；否则退出。条件比循环体多求值一次。

  4. a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

    组合：逐次相减的除法是一个顺序（赋初值、重复、输出），其中的重复以另一个顺序（减、数）为循环体。

在用日常语言写成的过程中区分这三种结构，是把它翻译成程序的第一步。选择的标志是“如果”“在……情况下”或“根据”；重复的标志是“当……时”“直到”“对每个”或“……多少次就……多少次”。一个过程如果没有这些词，就是一个顺序；而如果它必须处理大小可变的输入（一列数、一段文本），它就缺了一个重复。

会终止吗？

有穷性是算法定义的一部分，而重复是唯一可能失去它的地方：五个步骤的顺序执行五个步骤，选择执行它的一个分支；但重复执行循环体的次数等于条件成立的次数，没有任何东西能事先保证条件会不再成立。

为了论证一个重复会终止，要寻找一个由变量计算出来的量，它满足两个条件：只要重复还在继续，它就是自然数（非负整数），并且每一轮都严格递减。如果是这样，重复就会终止：严格递减的自然数序列不可能是无穷的，因为每一轮至少使它减少一，而从一个自然数 nn 到零，不会多于 nn 级台阶。这个量称为变式或界函数，设计正确的循环一课将系统地使用它。

例题逐次相减的除法的变式

在逐次相减的除法中，变式是 rr。只要重复还在继续，就有 r≥b>0r \geq b > 0，所以 rr 是自然数。每一轮中，rr 取值为 r−br - b，又因为 b>0b > 0（前置条件），新值严格更小。因此，重复会终止，而且至多经过 aa 轮（实际上恰好经过 qq 轮，即商）。

请注意前置条件 b>0b > 0 用在了哪里。如果以 b=0b = 0 执行算法，步骤 3 使 rr 保持不变，条件 r≥0r \geq 0 总是成立，重复永远不会终止：算法并没有错，而是给了它一个契约所排除的输入。如果 bb 是负数，rr 每一轮都会增大。前置条件不是装饰：它恰恰是推理成立所需要的东西。

变式的两个条件都是必要的，而在任何一个上都容易出错。考虑下面这个过程，它打算判定一个自然数 nn 是否为偶数：“当 n≠0n \neq 0 时，nn 取值为 n−2n - 2；如果到达零，则 nn 原来是偶数”。量 nn 每一轮都减小，然而若 nn 是奇数，这个过程就不会终止：当 n=5n = 5 时，它经过 33、11、−1-1、−3-3，而条件 n≠0n \neq 0 永远成立。不满足的是另一个条件：nn 不再是自然数，因为重复的条件并不阻止它降到零以下。改正的办法是：当 n≥2n \geq 2 时重复，最后根据剩下的值 00 或 11 作出判定；现在 nn 在每一轮都是自然数，因为只在 n≥2n \geq 2 时才做减法，而且它递减：过程会终止。

判定一个重复是否终止并不总是容易的。一个著名的例子：从自然数 n≥1n \geq 1 出发，当 n≠1n \neq 1 时，若 nn 是偶数就除以二，若是奇数就换成 3n+13n + 1。当 n=6n = 6 时，序列是 6,3,10,5,16,8,4,2,16, 3, 10, 5, 16, 8, 4, 2, 1，它终止了。没有人找到使它不终止的 nn，人们已经用计算机对极多的值验证过；但没有人能证明它总会终止：这就是考拉兹猜想，数学中的一个未解问题。没有已知的量在每一轮都减小。对编程者来说，教训朴素而坚定：一个无法论证其终止性的算法，还没有完成。

常见错误

  • 有歧义的步骤。“重复几次”“直到合适为止”“取一个适当的数”。每一步都必须在不理解问题的情况下也能执行；否则就写得不好。
  • 忘记重复一次也不执行的情形。任何把条件放在开头的重复，都可能执行循环体零次。必须时刻问自己，算法在这种情形下输出什么，而用最小的输入进行跟踪就能回答。
  • 用例子来规约。“对 17 和 5 得 3 和 2”不是规格说明；关系要写成一般的条件，例子只是用来说明它。
  • 把算法与它的程序混为一谈。一个出错的程序，错的可能是算法，也可能是算法的书写。事先没有写出算法的人，不知道该在两者中的哪一个里找错。
  • 想当然地认为会终止。一个量在减小还不够：只要重复还在继续，它还必须是自然数。

例题

例题 1三个数中的最大者，含并列情形

写一个满足第一节中三个数最大值规格说明的算法，并对输入 (7,2,5)(7, 2, 5) 和 (4,9,9)(4, 9, 9) 手工执行。

解答

  1. m=xm = x

    思路：遍历输入，把迄今见到的最大者保存在变量 mm 中。第一步：mm 取值为 xx。此后，mm 是已见数据中的最大值，而已见数据只有 xx。

  2. m=max⁡(x,y,z)m = \max(x, y, z)

    第二步：若 y>my > m，则 mm 取值为 yy。第三步：若 z>mz > m，则 mm 取值为 zz。第四步：输出 mm。这是顺序排列的三条指令，其中两条是没有另一分支的选择。

  3. (x,y,z)=(7,2,5)⇒m=7(x, y, z) = (7, 2, 5) \Rightarrow m = 7

    对 (7,2,5)(7, 2, 5) 的跟踪：第一步之后 m=7m = 7；第二步中，2>72 > 7 为假，mm 不变；第三步中，5>75 > 7 为假，mm 不变。输出 77。

  4. (x,y,z)=(4,9,9)⇒m=9(x, y, z) = (4, 9, 9) \Rightarrow m = 9

    对 (4,9,9)(4, 9, 9) 的跟踪：第一步之后 m=4m = 4；第二步中，9>49 > 4，于是 mm 变为 99；第三步中，9>99 > 9 为假，mm 不变。输出 99，这是正确的：并列无须专门处理。

  5. m≥x,m≥y,m≥zm \geq x, \quad m \geq y, \quad m \geq z

    论证：每一步之后，mm 都是已见数据之一，且已见数据中没有一个超过它。第一步之后这成立，而每个选择都保持它：如果新数据更大，它就成为 mm；否则，它不超过 mm。最后三个数据都已见过，mm 满足后置条件。

  6. (x,y,z)=(4,9,9)⇒p∈{2,3}(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}

    如果写的是 y≥my \geq m 而不是 y>my > m，结果相同，因为并列时赋的是相等的值。在 >> 与 ≥\geq 之间的选择，只有在还要求给出最大值的位置时才重要：用 >> 时给出并列位置中的第一个，用 ≥\geq 时给出最后一个，公式中把它记作 pp。

例题 2闰年，用一个反例改正

在格里高利历中，一个年份如果能被 44 整除，就是闰年，但能被 100100 整除的年份除外，它们只有同时能被 400400 整除时才是闰年。一名学生提出算法：“如果年份能被 44 整除，输出是；否则输出否”。找出它出错的一个年份，并写出一个正确的算法及其规格说明。

解答

  1. (4∣n∧¬(100∣n))∨400∣n(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n

    规格说明。输入：一个整数 n≥1583n \geq 1583（格里高利历自 1582 年 10 月起施行）。输出：是或否。关系：输出为是，当且仅当 nn 能被 44 整除而不能被 100100 整除，或者能被 400400 整除。

  2. 1900=4⋅475,1900=400⋅4+3001900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300

    所提出的算法对大多数年份都对，所以看起来是正确的。要驳倒它，只需一个能被 100100 整除而不能被 400400 整除的年份：19001900 能被 44 整除，算法输出是；但 19001900 年不是闰年。

  3. 400∣n,100∣n,4∣n400 \mid n, \quad 100 \mid n, \quad 4 \mid n

    改正后的算法，由三个连锁的选择组成。步骤 1：若 nn 能被 400400 整除，输出是并终止。步骤 2：若 nn 能被 100100 整除，输出否并终止。步骤 3：若 nn 能被 44 整除，输出是；否则输出否。

  4. 2000,1900,2024,20232000, \quad 1900, \quad 2024, \quad 2023

    提问的顺序至关重要：它们从最特殊的规则走向最一般的规则。如果先问 44，年份 19001900 在到达例外之前就会得到是。对四个年份的跟踪，每种情形一个：20002000（步骤 1：是），19001900（步骤 2：否），20242024（步骤 3：是），20232023（步骤 3：否）。

  5. 4∣1900∧¬(400∣1900)4 \mid 1900 \wedge \neg (400 \mid 1900)

    这个教训不只关乎历法：一个反例就足以驳倒一个算法，而反例要到规则的边界去找，而不是在常见情形中找。用 20242024、20202020 和 20162016 来试，什么也发现不了。

例题 3逐次相减的除法要进行多少轮

以 a=20a = 20、b=5b = 5 以及 a=0a = 0、b=7b = 7 手工执行逐次相减的除法。然后论证：对每个容许的输入，算法恰好在 qq 轮之后终止，并且它的输出满足后置条件。

解答

  1. 20=5⋅4+020 = 5 \cdot 4 + 0

    以 a=20a = 20、b=5b = 5 跟踪：rr 依次为 2020、1515、1010、55、00，qq 依次为 00、11、22、33、44。第五次检验 0≥50 \geq 5 不成立。输出：q=4q = 4，r=0r = 0。这里的边界情形是整除：第四轮之所以进行，是因为 5≥55 \geq 5，所以条件必须是 ≥\geq 而不是 >>。

  2. 0=7⋅0+00 = 7 \cdot 0 + 0

    以 a=0a = 0、b=7b = 7 跟踪：第一次检验 0≥70 \geq 7 就不成立；循环体一次也不执行。输出：q=0q = 0，r=0r = 0，这是正确的。

  3. b⋅(q+1)+(r−b)=b⋅q+r=a\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}

    一个保持不变的关系。在第一轮之前，b⋅q+r=b⋅0+a=ab \cdot q + r = b \cdot 0 + a = a。每一轮中 rr 减少 bb，qq 增加 11，所以 b⋅q+rb \cdot q + r 不变。因此，这个等式在每一轮之后都成立。

  4. r0>r1>r2>⋯≥0r_0 > r_1 > r_2 > \cdots \geq 0

    终止性。只要重复还在继续，就有 r≥b>0r \geq b > 0，并且 rr 是自然数；每一轮它都减少 b≥1b \geq 1。严格递减的自然数序列是有限的：重复会终止。

  5. a=b⋅q+r,0≤r<ba = b \cdot q + r, \quad 0 \leq r < b

    终止时条件不成立：r<br < b。此外 r≥0r \geq 0，因为减去 bb 只在 r≥br \geq b 时进行。再结合保持不变的关系，输出满足后置条件；又因为 qq 计数的是轮数，所以轮数就是商。

在线练习

练习 1数一数轮数

手工执行下面的算法，并在框中写出它输出的值，只写数字。

  1. nn 取值为 2929，kk 取值为 00。
  2. 当 n>1n > 1 成立时，重复步骤 3 和 4；当它不再成立时，转到步骤 5。
  3. 若 nn 是偶数，nn 取值为 n/2n / 2；若是奇数，nn 取值为 n+1n + 1。
  4. kk 取值为 k+1k + 1；回到步骤 2。
  5. 输出 kk。

浏览器会即时检查你的答案，但不会评分。

提示

列出表格：第一轮中 nn 从 2929 变为 3030。nn 每变化一次就数一轮，直到 nn 等于 11。

练习 2缺少的条件

下面用简写形式写出的算法应当用逐次相减计算除法的商和余数，但它缺少重复的条件。请用正确的条件替换下划线那一行中的空缺，其余部分不要改动。

浏览器会即时检查你的答案，但不会评分。

提示

以 a=10a = 10 和 b=5b = 5 手工执行算法：即使余数恰好为 55，第二轮也必须进行。

练习题

每道题都有一条提示，最好在自己尝试之后再打开；还有一个答案，打开提示后才会出现。

练习题 1规约三个数的排序

写出问题“把三个数排序”的规格说明（输入、输出和关系），并指出它迫使我们作出哪些题述没有作出的决定。然后验证：对于输入 (5,2,5)(5, 2, 5)，规格说明排除 (2,5,6)(2, 5, 6) 和 (2,5,5,5)(2, 5, 5, 5) 这两个输出，而接受 (2,5,5)(2, 5, 5)。

提示

一个“有序”的输出可能与输入毫无关系。什么条件把输出中的数与输入中的数联系起来，包括重复的数？递增还是递减？严格还是不严格？

答案

输入：三个数 xx、yy、zz。输出：三个数 uu、vv、ww。关系：u≤v≤wu \leq v \leq w，并且 (u,v,w)(u, v, w) 是 (x,y,z)(x, y, z) 的一个重排，也就是说，它以同样的重复次数含有同样的值。题述没有作出的决定：方向（这里是从小到大）；顺序不是严格的（是 ≤\leq 而不是 <<，因为有重复的值时严格的顺序不可能成立）；以及输出必须是一个重排。(2,5,6)(2, 5, 6) 是有序的，但含有原来没有的 66；(2,5,5,5)(2, 5, 5, 5) 有四个值；(2,5,5)(2, 5, 5) 满足两个条件。没有重排这个条件，(0,0,0)(0, 0, 0) 对任何输入都会是正确的输出。

练习题 2一个数的各位数字，从右到左

写出一个用编号步骤表示的算法，它接收自然数 nn，并从最后一位到第一位输出它的各位数字（对 40724072，输出 22、77、00、44），只使用除以 1010 的商和余数。对 40724072 和 00 手工执行它，并论证它对每个 nn 都会终止。

提示

除以 1010 的余数是最后一位数字，而商就是去掉这一位后的数。决定条件是在输出一位数字之前还是之后提问，并看看 n=0n = 0 时会发生什么，它有一位数字。

答案

一个正确的算法：(1) 输出 nn 除以 1010 的余数；(2) nn 取值为 nn 除以 1010 的商；(3) 若 n>0n > 0，回到步骤 1；否则终止。提问放在循环体之后，所以循环体至少执行一次：对 n=0n = 0 输出 00，这是它唯一的一位数字。如果在开头提问（“当 n>0n > 0 时”），对 n=0n = 0 就什么也不输出；这正是忘记重复一次也不执行的情形的错误。对 40724072 的跟踪：输出 22、77、00、44，而 nn 依次为 407407、4040、44、00。终止性：变式是 nn，它是自然数；如果回到步骤 1，那是因为 n>0n > 0，而对 n≥1n \geq 1，除以 1010 的商严格小于 nn，所以 nn 每一轮都严格递减。

练习题 3用硬币找零

有面值为 5050、1010 和 11 个单位的硬币，数量不限。规格说明：输入，一个自然数 mm；输出，三个自然数 c50c_{50}、c10c_{10}、c1c_1，满足 50c50+10c10+c1=m50 c_{50} + 10 c_{10} + c_1 = m，并使硬币枚数 c50+c10+c1c_{50} + c_{10} + c_1 尽可能少。有人提出下面的算法。找出一个使它出错的输入，解释每个缺陷并加以改正。

  1. c50c_{50}、c10c_{10} 和 c1c_1 取值为 00。
  2. 若 m≥50m \geq 50，c50c_{50} 取值为 c50+1c_{50} + 1，且 mm 取值为 m−50m - 50。
  3. 当 m>10m > 10 时：c10c_{10} 取值为 c10+1c_{10} + 1，且 mm 取值为 m−10m - 10。
  4. 当 m>0m > 0 时：c1c_1 取值为 c1+1c_1 + 1，且 mm 取值为 m−1m - 1。
  5. 输出 c50c_{50}、c10c_{10} 和 c1c_1。
提示

硬币的总额总是 mm；可能出错的是枚数。试一个 1010 的整倍数和一个大于 100100 的金额，并问问自己，步骤 2 用的是哪种组合步骤的方式，又应当用哪一种。

答案

有两个缺陷。第一，步骤 3 用的是 m>10m > 10：当 m=10m = 10 时，它不给出任何面值 1010 的硬币，而给出十枚面值 11 的硬币，而不是一枚。第二，步骤 2 在需要重复的地方用了选择：当 m=120m = 120 时，按原样写的算法给出一枚面值 5050 的、六枚面值 1010 的和十枚面值 11 的硬币（共十七枚），即使步骤 3 已经改正，也会给出一枚面值 5050 的和七枚面值 1010 的（共八枚），而不是两枚面值 5050 的和两枚面值 1010 的（共四枚）。输入 m=100m = 100 同时暴露了两个缺陷：算法给出一枚面值 5050 的、四枚面值 1010 的和十枚面值 11 的，共十五枚，而不是两枚。改正：步骤 2，“当 m≥50m \geq 50 时，……”；步骤 3，“当 m≥10m \geq 10 时，……”。这样改正后，算法总是取能放得下的最大硬币，而对这三种硬币，这样得到的枚数最少：mm 的个位数字只能用面值 11 的硬币支付，剩下的部分应尽可能多地用面值 5050 的硬币支付，因为五枚面值 1010 的与一枚面值 5050 的等值。换成别的硬币，例如面值 11、33 和 44，金额 m=6m = 6，总取最大者就不再能得到最小值（4+1+14 + 1 + 1 对 3+33 + 3）。