热身问答

• Algorithm翻译成中文是什么？
  • 算法
• 辗转相除法是用于计算什么的算法？
  • 是用于计算最大公约数的算法。
  • 最大公约数指的是两个整数的公共约数中最大的数。使用辗转相除法，就可以通过机械的步骤求出最大公约数。
• 程序中的”哨兵“指的是什么？

  • **“哨兵”指的是一种含有特殊值的数据，可用于标识数据的结尾等。**
    

  • 字符串的末尾用 0 表示，链表的末尾用－1 表示，像这种特殊的数据就是哨兵。

5.2 要点 1：算法中解决问题的步骤是明确且有限的

算法： 把解决问题的步骤无一遗漏地用编程语言表达出来， 并且步骤必须是明确且有限的。

举例：

问题：求出 12 和 42 的最大公约数。 最大公约数是指两个整数的公共约数（能整除被除数的数）中最大的数。

我们的求解方式：

我们把两个数写在一排，不断地寻找能够同时整除这两个整数的除数。最后把这些除数相乘就得到了最大公约数。 可是这些步骤并不能称为算法， 因为步骤不够明确。 计算机并不能判断第一步要用2整除， 第二步用3整除， 因为计算机不能思考没有直觉。 所以， 这不是算法。

5.3 要点 2：计算机不靠直觉而是机械地解决问题

典型算法： 按照机械的步骤就可以解决一个问题的算法。

譬如辗转相除法（又称欧几里得算法）就是一个求解最大公约数的典型算法。

步骤：用两个数中较大的数减去较小的数（步骤），反复进行上述步骤，直到两个数的值相等（步骤的终止）。如果最终这两个数相同，那么这个数就是最大公约数。

那么这个步骤就是：1. 步骤是明确的、完全不依赖直觉的；2. 步骤是机械的、不需要动脑筋就能完成的；3. 使步骤终止的原因是明确的。

a = 12
b = 42
While a <> b
    If a > b Then
        a = a - b
    Else
        b = b - a
    End If
Wend
MsgBox "最大公约数为 " & CStr(b) & "."

将此文件保存为扩展名为 .vbs的文件，双击此文件程序就可以运行了。

5.3 要点 3：了解并应用典型算法

5.5 要点4： 利用计算机的处理速度

问题1： 判定 91 是否是素数

思考： 能不能找到比91小的、能够整除的数， 找不到91就是素数。

算法： 埃拉托斯特尼筛法. 要判定91 是否是素数，只要分别除以 2～90 之间的每个数就可以了（因为 1肯定能够整除任何数，所以从 2 开始检测）。

a = 91
s = "是素数. "
For i = 2 to (a - 1)
    If a Mod i = 0 Then
        s = " 不是素数. "
        Exit For
    End If
Next
MsgBox CStr(a) & s
   

所以计算机的处理速度是非常快的。

问题2：鸡兔同笼问题：鸡和兔子共计 10 只，把它们的脚加起来共计 32 只，问鸡和兔子分别有多少只？设有 x 只鸡，y 只兔子，那么就可以列出如下的联立方程组。

x + y = 10

2x + 4y = 32

机械步骤： 因为鸡和兔子的只数应该都在 0～10 这个范围内，所以就试着把0～10 中的每个数依次代入 x 和 y，只要能够找到使这两个方程同时成立的数值也就求出了答案。

For x = 0 To 10
    For y = 0 To 10
        a = x + y
        b = 2 * x + 4 * y
        If (a = 10) And (b = 32) Then 
            MsgBox "鸡 = " & CStr(x) & ", 兔子 = " & CStr(y)
        End If
    Next
Next

5.6 要点 5：使用编程技巧提升程序执行速度

虽然计算机的处理速度快得惊人，但是当处理的数据数值巨大或是数量繁多时还是要花费大量的时间。所以我们还是要追求执行时间较短的算法。

例如，判定 91 是否是素数的过程一下子就有结果了，可是要去判定 999999937 的话，笔者的电脑就要花费大约 55 分钟之久（言外之意 999999937 是素数）

可以缩短处理时间的技巧： 在判定素数上，原先的过程是用待判定的数除以比它小的所有正整数，可以改成用待判定的数除以比它的 1/2 小的所有数，处理时间就会缩短。

我们有一个应该熟知的技巧叫做“哨兵”， 此技巧多用于线性搜索。 线性搜索是从若干数据中查找目标数据。线性搜索的基本过程是将若干个数据从头到尾，依次逐个比对，直到找到目标数据。

例如：假设有 100 个箱子，里面分别装有一个写有任意数字的纸条，箱子上面标有 1～100 的序号。现在要从这100 个箱子当中查找是否有箱子装有写着要查找数字的纸条。

• 不使用哨兵：从第一个箱子开始依次检查每个箱子中的纸条。每检查完一个纸条，还要再检查箱子的编号（用变量 N表示），并进一步确认编号是否已超过最后一个编号了

  • 不必要处理： 每次都要检查箱子的编号有没有到100

  • 

• 使用哨兵：我们添加了一个101号箱子， 在里面预先放入的纸条上写有正要查找的数字。这种数据就被称为“哨兵”。通过放入哨兵，就一定能找到要找的数据了。找到要找的数据后，如果该箱子的编号还没有到101 就意味着找到了实际的数据；如果该箱子的编号是 101，则意味着找到的是哨兵，而没有找到实际的数据。

  • 于是执行时间缩减。

  • 

5.7 要点 6：找出数字间的规律

现在我们想要写出一个判定石头剪刀布游戏胜负的算法。没有任何技巧时， 我们可以通过以下9种组合来判断输赢， 但是这种方法太冗长枯燥了。 所以我们开始寻找数字间的一种规律。 根据平局、A获胜、B获胜情况时数字的不同， 我们可以发现：

• 如果变量 A 和 B 相等就是“平局”
• 如果用 B＋1 除以 3 得到的余数与变量 A 相等就是“玩家 B获胜”
• 其余的情况都是“玩家 A 获胜”

If A = B Then
    MsgBox "平局"
ElseIf A = (B + 1) Mod 3 Then
    MsgBox "玩家B获胜"
Else
    MsgBox "玩家A获胜"
End If

5.8 要点 7：先在纸上考虑算法

绘画流程图！