跳转到内容

A-level 计算机/WJEC (Eduqas)/组件 1/算法和程序

Add links
来自维基教科书，开放书籍，开放世界

算法

算法是解决特定问题的有限指令集。它可以使用伪代码、流程图或结构化英语来表示。

表示

[编辑 | 编辑源代码]

伪代码

[编辑 | 编辑源代码]

伪代码是用“通用”语言编写的算法。它们是在没有考虑任何特定编程语言的情况下编写的，而是旨在更接近于纯英语。这使程序员能够理解解决方案的逻辑和算法方面，而无需担心编码语言的细微差别。提供伪代码是明确的，并且遵循任何编程语言的基本规则（例如变量声明）。在考试中，你会遇到这种伪代码

标准 表示
变量声明 Num 是整数
变量初始化 设置 Num = 0
用户输入 输入 Num
输出消息 输出“输入下一个数字。”
注释/标注 {添加增值税后的价格}
连接 输出“最高分数”, 总计
选择（IF） 如果平均值 > 75 则

输出“需要进一步治疗。”

否则

输出“不需要进一步治疗。”

结束 IF

While 循环 当 Num < 0 时

输入 Num

结束 While

For 循环 对于 Count = 1 到 20

如果 Value > Max 则 Max = Value

结束 For

While 循环 重复

如果 Number MOD Divisor = 0 则

Prime = FALSE

结束 IF


设置 Divisor = Divisor +1

直到 (Prime = FALSE) 或 (Divisor = Number)

流程图

[编辑 | 编辑源代码]
在流程图中显示决策。这些形状的组合构成了决策流程图。

流程图是可视化表示算法的一种方法（有关形状，请参见规范中的附录 D）。这是通过使用图表来完成的，从开始标签开始，并遵循各种语句和问题之间的线条，这些语句和问题被执行和遵守，直到到达终点。

每个不同的指令类型都用不同的形状表示：开始和结束点通常用椭圆形或圆角矩形表示，过程（例如计算）发生在矩形内，输入由梯形接收，平行四边形表示输出，菱形（菱形）用于表示决策。决策菱形是流程图路径分叉的地方，从它出来有两条线，通常标记为“是”或“否”。在遵循流程图时，根据决策菱形本身写出的问题的答案选择正确的线。

正如你可能已经知道的那样，对于较大的程序，流程图很快就会变得复杂，创建足够复杂的流程图可能需要一段时间，并且通常难以遵循。因此，流程图通常只用于较小的、不太复杂的程序。

目录

[编辑 | 编辑源代码]

变量和常量

[编辑 | 编辑源代码]

常量

[编辑 | 编辑源代码]
Algorithm CalculateVAT

RateVAT = 0.2   {this is a constant to store the VAT rate}

这些在程序中保存固定值，与变量不同，变量可以随时更改。相反，常量在程序顶部定义，并在整个程序中保存相同的值，如果程序的任何部分尝试更改它，则会抛出错误。这可以防止意外更改常量。常量不会经常改变，但如果改变，在程序顶部更改它们比在程序主体中出现的地方更容易（例如，在程序中变量的多个实例）。

标识符

[编辑 | 编辑源代码]

自文档标识符

[编辑 | 编辑源代码]

不可避免地，其他人会阅读你的代码，独自工作的情况很少见。变量应该以一种你可以理解其内容将包含什么的方式命名，例如，MemberID 将包含成员的 ID。它是自文档的，你不需要阅读任何额外的内容或查阅解释以理解它将包含什么内容。一个非自文档变量的例子是“value”或“x”，因为含义非常不清楚。

注释

[编辑 | 编辑源代码]
{comments help other programmers to understand code}

注释是插入到代码中的英文片段。它们帮助其他程序员理解代码，但对于程序运行来说是完全不需要的。注释用于通过不同的程序员或同一程序员在以后的时间（例如，在提高效率时）使程序更易于阅读。当程序被编译时，注释会被丢弃。

程序布局

[编辑 | 编辑源代码]

有些语言明确要求您以特定方式布局代码，以便代码能够正常运行。然而，其他语言在方法上则比较宽松。良好的程序布局要求您缩进代码并符合某些标准，例如在运算符之间添加空格。有些公司更喜欢用 驼峰式命名法 编写代码，而其他公司更喜欢用 蛇形命名法，但无论您使用哪种方法，都应该在整个编码项目中保持一致。请查看以下示例，了解程序布局的含义。

If CodeLayoutCheckPassed = 1 Then
       codeIndented = 1
       selfDocumentingIdentifiersUtilised = 1
Else
       codeIndented = 0
       selfDocumentingIdentifiersUtilised = 0
End If

这种方式不太好，因为您无法清楚地看到程序可能采用的不同路径。

If CodeLayoutCheckPassed=1 Then
code_Indented=1
self_Documenting_IdentifiersUtilised=1
Else
code_Indented=0
self_DocumentingIdentifiersUtilised=0
End If

变量的作用域

[edit | edit source]

变量具有作用域。作用域是指变量在程序中可以使用的地方。局部变量只能在定义它们的子程序中使用，而全局变量可以在整个程序中使用。全局变量仅在程序运行期间存在，并且可以在任何时候访问。局部变量仅在程序处于声明它们的范围时存在，例如在 For 循环中，当循环结束时，"Item" 变量会递增 1。

子程序

[edit | edit source]

大型程序也可以被分解成执行特定任务的命名代码块。这些就是子程序，它们很重要，因为一旦定义，子程序可以在程序中的任何位置被调用以执行其任务。这使得它们成为解决需要在整个程序中重复相同指令序列的问题的理想选择。大多数语言使用两种类型的子程序——函数和过程。两者在功能上非常相似，除了一个重要的区别：函数 **必须** 将单个值返回到程序的主体，而过程则不会。这种区别通常在函数和过程的定义方式中明确表示。

参数

[edit | edit source]

两种类型的子程序都依赖于参数来传递要利用的值。传递参数有两种方式：按值传递或按引用传递。按值传递是指创建一个局部 **副本** ，并在过程运行后将其丢弃。按引用传递是指传递 **地址** 而不是实际数据。按值传递的优点是它避免了意外的副作用，在这些副作用中，参数的值在主程序中发生变化，并且该过程也发生了变化。按引用传递的优点是它避免了与创建数据副本相关的大量处理和存储，并允许将所需的更改传递回主程序。

递归

[edit | edit source]
Function Fvalue (Num: Integer) : Integer
If Num = 1 Then
    Set Fvalue = 0
Else
    If Num = 2 Then
        Set Fvalue = 1
    Else
        Set Fvalue = Fvalue(Num-2) + Fvalue
    End If
End If
End Function

递归算法是指 **算法在自身中调用自身**，直到满足终止的 **基本情况**。程序会打开多个“副本”，直到这些副本终止（结束）。一个常见的例子是阶乘，它是小于或等于该值的全部正整数的乘积。例如，

数学运算

[edit | edit source]
运算符 符号 描述 示例
加法 + 这些值的总和。
减法 - 从另一个值中减去一个值。
乘法 * 两个数字的重复加法。
除法 / 计算一个数字包含在另一个数字中的次数。
整数除法 DIV 返回一个数字包含在另一个数字中的次数。
取模 MOD 返回计算一个数字包含在另一个数字中的次数后的余数。
取反 - 翻转数字的符号。
指数 ^ 将第一个数字提升到第二个数字的幂。

第二种是选择。这些语句根据给定的输入和程序员设置的逻辑规则，决定输出（或要运行的代码）。这是基本的 IF 语句——如果这是真的，那么执行此操作，否则执行另一个操作。算法的最后部分是迭代——其中代码旨在多次运行，直到满足终止条件。例如，FOR 循环将重复一定次数，而 WHILE 循环将在某个条件为真时重复。

任何算法的每个部分都依赖于变量来存储数据。变量是计算机内存中一个命名的位置，它可以在程序运行时用于存储数据，然后可以在以后被调用。这存储在计算机的 RAM 中，并从 0 开始用内存地址进行标记。变量通常在程序中分配名称，而存储位置的具体细节留给翻译器处理。除了它存储的信息之外，变量还有两个主要属性——作用域和生命周期。简单来说，变量的作用域是指它在程序中可以访问的地方，而变量的生命周期是指变量可以访问的时间长度。局部变量的作用域很小，生命周期有限，因为它只能在定义它的子程序中访问，而全局变量存在于程序的整个生命周期中，将具有较大的作用域和较长的生命周期。

验证与确认

[edit | edit source]
类型和示例
合适的检查 无效数据的示例
存在性检查 框中没有内容
格式检查，以确保数据项与先前确定的模式匹配，例如只接受 7 位数字。 12345X
长度检查用于确保输入数据的长度合理，例如在 8 到 13 之间。 12345678901234567890
类型检查用于确保数据项属于特定类型，例如所有条目必须为数字。 Micheal

验证

[edit | edit source]

验证发生在**数据输入时**。验证检查的目的是检测错误并确保数据合理。一些常见的例子包括：存在检查，其中输入不能为 NULL（空），长度检查以确保输入满足字符限制/要求（对密码字段强制执行），格式检查以确保数据以特定方式输入（电子邮件必须包含 @ 符号），或者字符检查以检查仅输入接受的字符（不想在信用卡号中输入文本）。

验证

[edit | edit source]

验证发生在**数据输入时**或当数据从一个地方传输到另一个地方时。验证的目的是确保数据一致性（误输入）并确保数据没有被破坏。有两个常见的验证方式：双重输入（通常用于密码）和校对，例如，在订购披萨之前呈现一个带有总结的页面。双重输入是指输入两个值并**比较**它们。如果它们匹配，则没有输入错误；如果它们不匹配，则存在输入错误。

搜索

[edit | edit source]

搜索算法允许定位特定数据，例如特定用户或其组权限。

[edit | edit source]

从数组的开头开始，将 SearchValue 与数组中的**每个连续项**进行比较。此过程一直持续到找到匹配项（找到 SearchValue）或到达数组的**末尾**（SearchValue 不存在于数组中）。

myArray(6) Is Integer
SearchValue Is Integer
Found Is Boolean
Set Found = False
    
Input SearchValue
    
For i = 0 to 6
    If SearchValue = myArray(i)then
        Set Found = True
        Output "SearchValue found at position ", i
    End If
End For

If Found = False
    Output "SearchValue not found."
End if
[edit | edit source]

首先，二分搜索要求所有元素按升序排序。这种搜索比线性搜索好得多，因为如果发现大于 SearchValue 的元素，则可以终止搜索，因为所有其他项都将大于 SearchValue。其工作原理如下：

  1. 计算一个中点，并将 SearchValue 与中间元素进行比较。
  2. 如果这不是 SearchValue，则搜索下半部分或上半部分，直到找到 SearchValue 或中间元素大于 SearchValue。
myArray(6) Is Integer
Start Is Integer
End Is Integer
Found Is Integer
Mid Is Integer

Set Start = 0
Set End = 6
Set Found = False

Input SearchValue

    Repeat
        Set Mid = (Start + End) DIV 2

        If SearchValue = myArray(Mid) Then
            Set Found = True
            Output "SearchValue found at position ", Mid
        End If

        If SearchValue > myArray(Mid) Then
            Set Start = Mid + 1
        End If

        If SearchValue < myArray(Mid) Then
            Set End = Mid – 1
        End If

    Until (Found = True) OR (End < Start)

If Found = False
    Output "SearchValue not found."
endif

排序

[edit | edit source]

排序算法允许将一组无序的数据元素进行组织，例如按升序/降序或按字母顺序。

冒泡排序

[edit | edit source]

在冒泡排序中，项目根据它们是否高于或低于列表中的下一项进行移动。这导致最大的项重复地“冒泡”到列表的顶部，这就是该算法名称的来源。

  1. 对数据进行一次遍历，将每个值与其后续值进行比较，并在必要时交换它们。
  2. 重复此过程，直到数据按顺序排列，并且不再进行交换。
Start Procedure SortMyArray
    n Is Integer
    temp Is Integer
    swapped Is Boolean

    set n = length(myArray) {returns the length of myArray}
    repeat
        set swapped = FALSE
            for i = 0 to (n – 1)
                if myArray(i) < myArray(i + 1) then
                temp = myArray(i + 1)
                myArray(i + 1) = myArray(i)
                myArray(i) = temp
                swapped = TRUE
                end if
            end for
   until (swapped = FALSE)

End Procedure

插入排序

[edit | edit source]
  1. 项目逐个复制到一个新的排序数组中。
  2. 每个新项目都插入到正确的位置。
  3. 新数组中的所有项目都向上移动一个位置。

快速排序

[edit | edit source]
  1. 选择一个项目/枢纽（哪个项目并不重要）
  2. 生成两个新列表，分别包含较小的数字和较大的数字
  3. 对新子列表重复以上步骤（递归地），直到排序完成
Declare subprocedure QuickSort (myArray is string, indexLow is integer, indexHi is integer)

Pivot is string
tmpSwap is string
tmpLow is integer
tmpHi is integer
tmpLow = indexLow
tmpHi =indexHi
pivot = myArray (int(indexLow + indexHi)/2))

while (tmpLow <= tmpHi)
    while (myArray(tmpLow) < pivot and tmpLow < indexHi)
        tmpLow = tmpLow + 1
    wend

    while (myArray(tmpHi) > pivot and tmpHi > indexLow)
        tmpHi = tmpHi – 1
    wend

    if (tmpLow <= tmpHi) then
        tmpSwap = myArray(tmpLow)
        myArray(tmpLow) = myArray(tmpHi)
        myArray(tmpHi) = tmpSwap
        tmpLow = tmpLow + 1
        tmpHi = tmpHi -1
    end if
wend

if (indexLow < tmpHi) then
    QuickSort (myArray , indexLow, tmpHi)
Elseif (indexHi > tmpLow) then
    QuickSort (my Array, tmpLow, indexHi)
end if

end sub

编程结构

[edit | edit source]

顺序

[edit | edit source]

顺序表示逐行执行指令，一次执行一条。下面是使用汇编语言编写的代码片段，每行代码将依次执行以运行该代码片段。

LOAD 1,d1
LOAD 2,d2
XORR 1,2
STOR 1,d3
XORR 1,2

选择和重复

[edit | edit source]

选择的目的是在满足特定条件时执行代码，在本例中，如果 Num2> Biggest 为 True，则执行 Biggest = Num2。

重复（也称为循环）的目的是重复执行代码，直到满足某个条件，在本例中，直到 Num1 为整数为止。

Biggest Is Integer
Num1 Is Integer
Num2 Is Integer

Repeat
    Input Num1
Until (Num1 is an Integer)

Repeat
    Input Num2
Until (Num1 is an Integer)

Set Biggest = Num1

If Num2 > Biggest Then Biggest = Num2

Output Biggest

计数

[edit | edit source]

使用一个**变量**（整数）来计算满足某个条件的值。

请记住，计数总是从 0 开始，因此必须将变量的值**初始化**为 0。

异常值

[edit | edit source]

异常值被查找表视为终止信号。

模块化编程

[edit | edit source]

标准函数

[edit | edit source]

标准函数是指由解释器或编译器提供的某些常用函数，例如平方根、随机数生成器和在 Visual Basic 中看到的输出消息框等。包含这些标准函数的语言比没有这些函数的语言要好得多，因为它们可以节省程序员的时间，因为他们不需要编写那么多代码。该函数在之前已经过测试，不太可能包含错误，并且它是由该领域的专家编写的，因此将简洁高效。

用户定义子程序

[edit | edit source]

与一个大型程序相比，用户定义的子程序（如模块和函数）更容易编写，使程序更易读，易于单独测试，并且可以由个人编写并实施在大型程序中。它们也可能是以前编写的，可以从另一个程序中复制，或者可能已经存在于特定问题中。

压缩

[edit | edit source]

压缩文件时，会使文件变小（可能通过减少数据量）。压缩文件可以节省存储空间，并在通过网络发送文件时加快传输速度。压缩主要有两种类型：有损压缩和无损压缩。

有损压缩和无损压缩

[edit | edit source]

有损压缩（正如您可能从名称中猜到的那样）是指使文件变小，但在过程中会丢失一些信息。无损压缩是指使文件变小，但不会丢失任何信息。大多数情况下，无损压缩更可取，但有损压缩用于网站上的图像，尤其是当它们很小的时候，因为少量丢失的信息（质量）不会有太大影响，但会加快页面加载速度。

无损压缩的示例

[edit | edit source]

当一个字符被重复多次时，会使用行程长度编码，它可以在重复特定像素颜色的图像中使用。它使用一个标志字符来表示开始 ($)、重复的字母以及它重复的次数，因此 AAAAAAAAA 会变成 $A9。你明白了吧。

霍夫曼编码是字典编码的一个例子（一个包含常用字符的字典，每个字符都有自己的引用）。在英语中，一些字母的使用频率远高于其他字母，例如“A”比“Z”更常见。霍夫曼编码通过为出现频率更高的字母赋予更短的代码，为出现频率更低的字母赋予更长的代码来工作，从而产生一个更小的压缩文件。

比较压缩

[edit | edit source]

您可能会被要求比较有损压缩和无损压缩，甚至在考试中比较给定的压缩算法。要记住的第一点是，有损压缩总是比无损压缩更好，因为可以更容易地丢弃更多的数据，因为质量会丢失。压缩文件和随后解压缩文件需要一定的时间，这些分别称为压缩时间和解压缩时间。为了计算压缩算法的效率，我们可以计算“压缩比”，它是

测试

[edit | edit source]

您必须考虑三种类型的测试数据，请参考下表（1-100 是允许的数据）。

测试 意义 示例
正常/有效 这是我们希望用户输入的数据类型，它在我们的允许值范围内。 50
无效 此数据超出了我们接受的范围，或者完全是不同的数据类型。 200 和“twenty”
边界/极端 此数据位于我们接受值的边缘。 1 或 100
Retrieved from "https://wikibooks.cn/w/index.php?title=A-level_Computing/WJEC_(Eduqas)/Component_1/Algorithms_and_programs&oldid=4393876"
华夏公益教科书