3.2. 问题、算法与程序¶
3.2.1. 问题、算法与程序¶
3.2.1.1. 问题¶
程序员通常要与问题、算法和计算机程序打交道。这是三个截然不同的概念。
正如你的直觉所示， 问题 是一项有待完成的任务。最好把问题理解为输入与对应输出之间的匹配关系。问题的定义不应包含关于 如何 求解该问题的任何约束。求解方法只应在问题被精确定义并充分理解之后才去发展。不过，问题的定义应当对任何可接受的解法所能消耗的资源作出约束。凡是要靠计算机求解的问题，总存在这样的约束，无论是明说还是隐含。例如，任何计算机程序都只能使用可用的主存和磁盘空间，而且必须在 "合理"的时间内运行完毕。
可以把问题看作数学意义上的函数。 函数 是输入（即 定义域 ）与输出（即 值域 ）之间的对应关系。函数的输入可以是单个值，也可以是一组信息。构成输入的各个值称为函数的 参数 。为参数选定一组具体取值，就得到问题的一个 实例 。例如，排序函数的输入参数可能是一个整数数组。一个特定的整数数组，若给定其长度且数组中每个位置都有确定的值，就是排序问题的一个实例。不同的实例可能产生相同的输出。然而，只要用某个特定的输入来计算函数，同一个问题实例就必须总是产生相同的输出。
"所有问题都表现得像数学函数"这一观念，可能与你对计算机
程序行为的直觉不符。
你也许见过这样的程序：在两个不同时刻给它相同的输入值，
却得到两个不同的输出。
例如，在典型的 Linux 命令行提示符下输入 date ，
你就会得到当前日期。
自然，即便输入的是同一条命令，不同日子得到的日期值也不同。
不过，对 date 程序而言，其输入显然不止你为运行它而敲入的
那条命令。
date 程序计算的也是一个函数。
换句话说，在任何一个特定的日子里，对完全确定的输入，
正常运行的 date 程序只能返回一个答案。
对所有计算机程序而言，输出完全由程序的全部输入决定。
即使是"随机数生成器"，也完全由其输入决定
（尽管有些随机数生成系统似乎绕开了这一点，
它们从用户无法控制的物理过程中接受随机输入）。
程序所能实现的函数是有极限的，
这正是 可计算性
所研究的内容。
3.2.1.2. 算法¶
算法 是求解问题时所遵循的一种方法或过程。如果把问题看作函数，那么算法就是这个函数的一种实现，它把输入变换为对应的输出。一个问题可以由许多不同的算法来求解，而一个给定的算法只能求解一个问题（即计算一个特定的函数）。 OpenDSA 的模块涵盖许多问题，其中若干问题我们会看到不止一种算法。对于排序这个重要问题，广为人知的算法就有十几种！
了解一个问题多种解法的好处在于：对于问题的某个特定变体或某一类特定输入，解法 \(\mathbf{A}\) 可能比解法 \(\mathbf{B}\) 更高效，而对另一种变体或另一类输入，解法 \(\mathbf{B}\) 又可能比 \(\mathbf{A}\) 更高效。例如，有的排序算法可能最适合对少量整数排序（如果需要反复做这件事，这一点很重要）；有的可能最适合对大量整数排序；还有的可能最适合对一组变长字符串排序。
按照定义，只有具备以下全部性质，才能称为算法。
它必须是 正确的 。换句话说，它必须计算期望的函数，把每个输入都转换为正确的输出。注意，每个算法都实现了某个函数，因为每个算法都把每个输入映射到某个输出（哪怕这个输出是程序崩溃）。这里的关键在于，给定的算法是否实现了 预期的 函数。
它由一系列 具体步骤 组成。"具体"是指：对于必须执行该算法的人或机器来说，这一步所描述的动作是完全可理解并且可做的。每一步还必须能在有限的时间内完成。于是，算法给了我们一张通过执行一系列步骤来解决问题的"菜谱"，其中每一步都在我们的能力范围之内。能否执行某一步，可能取决于打算让谁（或什么东西）来执行这张菜谱。例如，烹饪书里饼干配方中的步骤，对指导人类厨师来说足够具体，但对编写自动饼干工厂的程序来说就不够了。
对于下一步将执行哪一步， 绝不能有歧义 。通常就是算法描述中的下一步。选择结构（例如
if语句）通常是任何算法描述语言的一部分。选择允许对下一步执行哪一步做出抉择，但在做出抉择的时刻，选择过程是无歧义的。它必须由 有限 步组成。如果算法的描述由无限多步构成，我们既无法把它写下来，也无法把它实现为计算机程序。大多数算法描述语言（包括英语和"伪代码"）都提供了执行重复动作的方法，即迭代。程序设计语言中迭代的例子包括
while和for循环结构。迭代使得描述可以很简短，而实际执行的步数由输入控制。它必须 终止 。换句话说，不能陷入无限循环。
3.2.1.3. 程序¶
我们常把计算机 程序 想成某个算法在某种程序设计语言中的实例，即具体表示。算法通常借助程序或程序的一部分来呈现。自然，同一个算法会有许多程序作为其实例，因为任何现代计算机程序设计语言都可以用来实现同一批算法（尽管某些程序设计语言能让程序员的日子好过些）。为了表述简便，人们常常把"算法"和"程序"混用，尽管它们实际上是两个不同的概念。按照定义，算法必须足够详细，以便在需要时能够转换为程序。
算法必须终止，这一要求意味着并非所有计算机程序都符合算法的技术定义。你的操作系统就是一个这样的程序。不过，你可以把操作系统的各项任务（每项任务都有各自的输入和输出）看作一个个独立的问题，每个问题都由操作系统程序的某一部分实现的特定算法来求解，而且一旦产出输出就会终止。
3.2.1.4. 小结¶
小结一下： 问题 是一个函数，或者说从输入到输出的映射。 算法 是求解问题的一张"菜谱"，其步骤具体且无歧义。算法必须正确、长度有限，并且对所有输入都必须终止。 程序 是算法在某种程序设计语言中的实例化。下面的幻灯片应当有助于你直观地看出这些区别。
