步骤E3中的箭头←是最重要的替代运算(有时叫做赋值或代换)。“m←n”意思是变量m的值代之以变量n的当前值。当算法E开始时，m和n的值是原来给出的数；但当它结束时，一般说来，这些变量将有不同的值。箭号用来把替代运算同相等关系加以区别：我们将不说“置m=n”，但也许我们将要问“是否m=n？”“=”号标记一个可被测试的条件，“←”号标记一个可被执行的动作。n增1的运算通过“n←n+1”来标记(读作以n+1代替n)。一般说来，“变量←式子”意味着用出现于式子内的所有变量的当前值来计算式子，并将结果代替箭头左边的变量的原先值。不熟悉计算机工作的人们有时有这样的倾向，即用“n→n+1”来标记n增1的运算，说是“n变成n+1”，这只能导致混乱，因为它同标准的约定正相冲突，因此我们应加以避免。
注意，步骤E3中的动作的次序是重要的。“置m←n，n←r”完全不同于“置n←r，m←n”。因为后者意味着，在用n的值来置m之前，n的原先值已经失去了。因此，后一次序等价于“置n←r，m←r”。当若干个变量全都置成等于相同的量时，我们使用多重的箭头；于是，“n←r，m←r”可以写成“n←m←r”。两个变量的值相互交换，我们可以写成“交换m〈—〉n”；这一动作也可通过使用一个新变量t，并写“置t←m，m←n，n←t”来确定。
除非另有说明，一个算法总是在编号最小的步骤处，通常是在步骤1处开始，并且顺序逐步执行之。在步骤E3中，强制的“返回步骤E1”以一种明显的方式说明了进行计算的次序。在步骤E2中，以条件“若r=0”作为动作进行的前提条件；所以，如果r≠0，就不应用该句子的剩下的话。虽然这里并未说明动作，但我们总是理解成：可以加上不言而喻的句子“如果r≠0，进行步骤E3”。
粗竖线■，出现于步骤E3的末尾，用来表示算法已结束而正文将继续。
至此，我们实际上讨论了用于本书的算法中的所有记号的约定，剩下只需要来约定一个用来表示一个有序数组的元素的“带下标的”或“带足标的”项的记号了。假设我们有n个量ν1，ν2，…，νn；对于第j个元素νj，我们经常使用记号ν〔j〕来代替。类似地，对于双下标的记号如αij，有时更愿意使用α〔i,j〕。有时，变量用多个字母的名称，并把这些字母都写成大写的。例如，TEMP可以是一个用于暂时地保存一个计算的值的变量的名称，PRIME〔K〕可以表示第K个质数，等等。
关于算法的形式就谈这么多；现在让我们来实现一个算法看一看。应当立即指出，读者不要期望象读一篇小说那样来读一个算法。如果是抱着这样的企图的话，那他就会很难理解文中正在叙述的内容。一个算法应该是可以信赖的，而且学习一个算法直到彻底掌握的最好方法是反复进行试验。当读者遇到一个算法时，应立即拿起笔和纸，找出这个算法的一个例子；通常要给出这个例子的要点，要不然就是读者能容易地把它想象出来。为了能够理解一个给定的算法，这是一个简单且省力的方法，经验证明，其它的途径都是不成功的。
因此，让我们找出算法E的一个例子。假设我们给出m=119和n=544。让我们准备好由步骤E1开始(读者现在就要象我们在下边一步一步叙述的那样来遵循这个算法)。在这种情况下，以n除m是十分简单的。简直是太简单了，因为商是0，而余数是119。于是r←119。我们进行到步骤E2，而且由于r≠0，步骤E2不发生作用。在步骤E3，我们置m←544，n←119。显然，如果原来m＜n，步骤E1中的商数总为0，而算法总是首先以这样比较麻烦的方式来相互交换m和n。如果愿意，我们可以增加一个新的步骤：“E0〔保证m≥n〕如果m＜n，交换m〈—〉n。”这样一来，在算法中并无实质性的改动，只是增加了算法的长度，但却大约有一半的情况减少了用来实现算法所需的时间。
返回到步骤E1，我们发现544／119=4又68／119。所以r←68。步骤E2再一次不能用。而且在步骤E3，我们置m←119，n←68。下一轮置r←51，而且最终m←68，n←51。然后，r←17，且m←51，n←17。最后，当以17除51时，r←0，于是算法在步骤E2处结束。119和544的最大公因子是17。
所以一个算法就是这样。算法的现代的意义十分类似于处方、过程、方法、技术、规程、程序，只不过是算法一词的含意有时稍微有一点特殊。一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列；此外，一个算法还有五个重要的特性：
1)有穷性 一个算法必须总是在执行有穷步之后结束。算法E是满足这个条件的。因为在步骤E1之后，r的值小于n，所以如果r≠0，下一次进行步骤E1时，n的值已经减小。正整数的递降序列必然最后要终止。所以，对于任何给定的n的原始值，步骤E1仅仅执行有穷次。然而，注意，步骤的数目可以变成任意大；选择巨大的m和n，就可能使步骤E1执行百万次以上。
(具有算法的其它所有特征，但却可能不具有有穷性的步骤，可以叫做“计算方法”。除了给出求两个整数的最大公因子的算法外，欧几里得还给出了实际上等价于算法E的一个几何构造，不过它是求两个线段的长度的“最大公度”的步骤。这是一个计算方法，因为如果所给的两个长度是“无公度的”，那它就不终止)。
2)确定性 算法的每一个步骤，必须是确切地定义的。对于每种情况，有待执行的动作必须严格地和不含混地规定之。本书中的算法都应当符合这一准则。但是由于它们是以自然语言描述的，读者有可能未能精确地理解作者的意思是什么。为了避免这一困难，就专为描述算法设计了形式地定义的程序设计语言或计算机语言，其中每一个语句有着非常确切的意义。本书中的许多算法，将同时以自然语言和以一种计算机语言给出。当用一个计算机语言来描述一个计算方法时，其表达形式就叫做一个程序。
在算法E中，确定性准则意味着：例如应用于步骤E1，则假定读者确切地知道n除m是什么意思而余数又是什么。事实上，如果m和n不是正整数，那末这究竟是什么意思，已经没有一般的约定。-π除-8的余数是什么？0除59/13的余数是什么？因此，确定性准则意味着我们必须保证，当执行步骤E1时，m和n的值总是正整数。按假设，这在开始时是正确的。而在步骤E1之后，r是一个非负整数。如果要进行步骤E3，r还必须是非0的，所以m和n事实上总象所要求的那样，都是正整数。
(未完待续)
本文地址：http://com.8s8s.com/it/it35186.htm