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