算法的概念

算法是一系列解决问题的清晰指令，也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。

算法的概念本身并不依赖于计算机，也可以是人。

作为阐明算法概念的例子，本节会讨论3种方法，用于解决同一个问题：计算两个整数的最大公约数。这些例子会帮我们阐明几个要点：

  • 算法的每一个步骤清晰，明确，来不得半点含糊的。
  • 算法的输入的值域要仔细定义。
  • 同一种算法可以用几种不同的形式来描述。
  • 可能存在几种解决相同问题的算法
  • 同一个问题的算法会基于完全不同的解题思路，解题速度也会不同。

让我们回到例子来

m, n的最大公约数记为gcd(m, n)。欧几里德算法求最大公约数是重复应用gcd(m, n)=gcd(n, m, m mod n), 直到m mod n等于0.

当gcd(m, 0)=m时，m和n的最大公约数也为m。

举例来说，gcd(60, 24)可以这样计算：

gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12

下面结构化的描述该算法：

用于计算gcd(m, n)的欧几里德算法

第一步: 如果n＝0，返回m的值作为结果，同时过程结束；否则，进入第二步。
第二步: 用n去除m，将余数赋给r。
第三步: 将n的值赋给m，将r的值赋给n，返回第一步。

我们也可以使用伪代码来描述这个算法：

算法 Euclid(m, n)
     //使用欧几里德算法计算gcd(m, n)
     //输入：两个不全为0的非负整数m, n
     //输出：m，n的最大公约数
     while n ≠ 0 do 
        r <- m mod n
        m <- n
        n <- r
     return m

怎么直到欧几里德算法最终一定会结束呢？

通过观察，发现，每经过一次循环，参加运算的两个算子中的后一个都会变得更小，而且绝对不会变成负数。确实，下一次循环时，n的新值是m mod n，这个值总是比n要来的小。所以，两个算子中的后一个的值最终变为0，此时，这个算法也就停止了。

最大公约数问题的另外两种算法。

用于计算gcd(m, n)的连续整数检测算法

第一步: 将min{m, n}的值赋给t。
第二步: m除以t，如果余数为0，进入第三步；否则，进入第四步。
第三步: n除以t，如果余数为0，返回t的值作为结果；否则，进入第四步。
第四步: 把t的值减1。返回第二步。

按照这个算法的当前形式，当它的一个输入为0时，计算出来的结构是错误的。

所以我们必须认真，清晰地规定算法输入的值域。

中学里计算gcd(m, n)的过程

第一步：找到m的所有质因数。
第二步: 找到n的所有质因数。
第三步: 从第一步和第二步求得的质因数分解式中找出所有的公因数。
第四步: 将第三步找到的质因数乡城，其结果作为给定数字的最大公约数。

这样，对于60和24这两个数，我们得到：

60 = 2·2·3·5
24 = 2·2·2·3
gcd(60, 24) = 2·2·3 = 12

对于第一步和第二步，介绍一个算法用阿里产生一格不大于给定整数n的连续质数序列。

首先初始化一个2~n的连续整数序列，作为候选质数。然后在第一个循环中，将2的倍数从序列中消去。然后，指向列表中的下一个数字——3，消去3的倍数，接着继续处理质数的倍数。以这个方式不断做下去，直到序列中已经没有可消的元素为止。序列剩下的整数就是我们要求的质数。

现在我们讨论一下序列中质数p的情况。

了解一个事实可以帮助我们避免多次消去相同的数字。

我们在步骤中不断消去p的倍数，那么第一个值得考虑的倍数是p·p，因为其他更小的倍数2p, …, (p-1)p已经在先前的步骤中消去了。

显然，p·p不会大于n，即p不会大于√n向下取整的值（记作[√n]）。我们以不等式p·p ≦ n作为判定循环是否继续的条件。

算法 Sieve(n)
    //实现“艾拉托色尼的筛子”
    //输入：一个正整数 n ≧ 2
    //输出：包含所有小于等于n的质数的数组L
    for p <- 2 to n do A[p] <- p
    for p <- 2 to [√n] do    //避免消去相同的数字
        if A[p] ≠ 0    //p没有被前面的步骤消去
            j <- p * p
            while j ≦ n do
                A[j] <- 0    //将该元素标记为已经消去
                j <- j + p
    //将A中剩余的元素复制到质数数组L中
    i <- 0
    for p <- 2 to n do
        if A[p] ≠ 0
            L[i] <- A[p]
            i <- i + 1
    return L

最后做一些说明。当今所使用的大多数算法都不涉及数学问题。了解算法会帮助我们处理专业和个人的日常事务。

Loading Disqus comments...
Table of Contents