计算机程序设计艺术(第I卷)

算法:
    对于所有的计算机程序设计说来，算法的概念总是基本的，所以我们应当首先细心地分析这一概念。
   “ 算法”(Algorithm)一词本身就是十分有趣的。初看起来，这词好像是某人打算要写的“对数”(Logarithm)一词但却把头四个字母写得前后颠倒了。这个词直到1957年之前在《韦氏新世界词典》(Webster's New World Dictionary)中还未出现，我们只能找到带有它的古代含意的较老形式的“算术”(Algorism)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros〔费力的〕+arithmos〔数字〕组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪耳国王Algor”派生而来的。最后，数学史学者发现了算术“algorism”一词的真实起源：它来源于有名的《波斯教科书》(Persian textbook)的作者的名字阿布·贾法·穆哈默德·伊本·穆萨·阿科瓦里茨米(Abu Ja'far Mohammed ibn Musa alKhowarizml)(约公元825年)—从字面上看，是“Ja,far的父亲，Mohammed,Moses的儿子，Khowarizm的士人”。Khowarizm是今天苏联基发(ХИВА)市的小城镇。AlKhowarizml写了著名的书《复原和化简的规则》(Kitab al jabr w'al-muqabala)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。
    逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语词典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错误的造作。由algorism又变成algorithm。只要了解人们已经忘记了这个词原来派生的实况，就不难理解这种变化。一本早期的德文数学词典《大全数学辞典》(Vollstandiges Mathematisches Lexicon莱比锡，1747)，给出了Algorithmus(算法)一词的如下的定义：“在这个名称之下，组合了四种类型的算术计算的概念，即是，加法，减法，乘法和除法”。拉丁短语algorithmus infinitesimalis(无限小算法)，在当时就用来表示“莱布尼兹(Leibnitz)所发明的以无限小量进行计算的方法”。
    1950年左右，algorithm一词经常地同欧几里得算法“Euclid's algorithm”联系在一起。这算法就是在欧几里得的《几何原本》(Euclid's Elements，第VII卷，命题i和ii)中所阐述的求两个数的最大公因子的过程。在这里给出欧几里得算法来，也将是有益的：
    算法E(欧几里得算法)。给定两个正整数m和n，求它们的最大公因子，即能够同时整除m和n的最大的正整数。
    E1.〔求余数〕以n除m并令r为所得余数(我们将有0≤r＜n)。
    E2.〔余数为0？〕若r=0，算法结束；n即为答案。
    E3.〔互换〕置m←n，n←r，并返回步骤E1。■
    当然，欧几里得并非就是以这样的方式来给出他的算法的。上面的格式充分演示了在给出本书中所有的算法时贯穿全书的风格。
    我们对所讨论的每一个算法，都给出了一个标识的字母(例如上边算法中的E)，并且用这个字母后面接上数字(例如E1，E2等等)来标识这个算法的步骤。书中各章分为编了号的节，在一节之内的算法仅用字母来标识；但当在其它节中引用这些算法时，则附以相应的节号。例如，我们现在是在第1.1节；在这一节中，欧几里得算法叫做算法E，而在后边的节引用它时，就记作算法1.1E。
    一个算法的每一步(例如上边的步骤E1)以一个方括号中的一个短句开始，它尽可能简短地概括这一步的主要内容。这一短句通常也出现在一个与这个算法相对应的框图(例如图1)中。借助于框图，读者将有可能更直观地看出这个算法的流程。

                图1 算法E的框图

   在概括性的短句之后，是有待执行的某个动作或有待作出的某个判断的文字符号的叙述。偶而也有带圆括号的注释(例如，步骤E1的第二句)，它是关于这一步的说明性信息，通常指出变量的某些特征或这一步的当前目标，等等；带圆括号的注释并不影响属于这一算法的动作，而只是为了便于帮助读者理解。