剑桥 IGCSE IGCSE, A-Level & AP 练习单预览

算法与编程

AP 计算机科学原理 · 第 3 主题

训练
讲义 词汇表

下面的代码使用 AP CSP 伪代码(AP CSP pseudocode)——考试的语言中立参考。赋值写作 a ← expression,而列表索引从 1 开始。

3.1

变量与赋值
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-1
To find specific solutions to generalizable problems, programmers represent and organize data in multiple ways.

AAP-1.A
Represent a value with a variable. [Skill 3.A]

  • AAP-1.A.1 A variable is an abstraction inside a program that can hold a value. Each variable has associated data storage that represents one value at a time, but that value can be a list or other collection that in turn contains multiple values.
  • AAP-1.A.2 Using meaningful variable names helps with the readability of program code and understanding of what values are represented by the variables.
  • AAP-1.A.3 Some programming languages provide types to represent data, which are referenced using variables. These types include numbers, Booleans, lists, and strings.
  • AAP-1.A.4 Some values are better suited to representation using one type of datum rather than another.

AAP-1.B
Determine the value of a variable as a result of an assignment. [Skill 4.B]

  • AAP-1.B.1 The assignment operator allows a program to change the value represented by a variable.

  • AAP-1.B.2 The exam reference sheet provides the "$\leftarrow$" operator to use for assignment. For example,

    Text:

    a ← expression

    Block:

    a ← expression

    evaluates expression and then assigns a copy of the result to the variable a.

  • AAP-1.B.3 The value stored in a variable will be the most recent value assigned. For example:

    a ← 1 b ← a a ← 2 display(b)

    still displays 1.

来源:美国大学理事会 AP 课程与考试说明

一个变量(variable)是一个持有一个值的命名的地方。赋值(assignment)运算符把右边的值存进左边的变量:

一个变量是一个值能变化的命名的存储
一个变量是一个值能变化的命名的存储
a ← 5
b ← a + 3      // b is now 8

一个变量一次持有一个值;再次赋值替换它。变量让一个程序存储输入、记住结果,并重用它们。

探索

Watch a variable hold and change its value

A variable is a named box that stores one value at a time. An assignment copies a value into the box; assigning again overwrites whatever was there.

词汇表 训练
英文 中文 拼音
variable 变量 biàn liàng
assignment 赋值 fù zhí
练习卷
3.2

数据抽象
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-1
To find specific solutions to generalizable problems, programmers represent and organize data in multiple ways.

AAP-1.C
Represent a list or string using a variable. [Skill 3.A]

  • AAP-1.C.1 A list is an ordered sequence of elements. For example,

    [value1, value2, value3, ...]

    describes a list where value1 is the first element, value2 is the second element, value3 is the third element, and so on.

  • AAP-1.C.2 An element is an individual value in a list that is assigned a unique index.

  • AAP-1.C.3 An index is a common method for referencing the elements in a list or string using natural numbers.

  • AAP-1.C.4 A string is an ordered sequence of characters.

AAP-1.D
For data abstraction:
a. Develop data abstraction using lists to store multiple elements. [Skill 3.B]
b. Explain how the use of data abstraction manages complexity in program code. [Skill 3.C]

  • AAP-1.D.1 Data abstraction provides a separation between the abstract properties of a data type and the concrete details of its representation.

  • AAP-1.D.2 Data abstractions manage complexity in programs by giving a collection of data a name without referencing the specific details of the representation.

  • AAP-1.D.3 Data abstractions can be created using lists.

  • AAP-1.D.4 Developing a data abstraction to implement in a program can result in a program that is easier to develop and maintain.

  • AAP-1.D.5 Data abstractions often contain different types of elements.

  • AAP-1.D.6 The use of lists allows multiple related items to be treated as a single value. Lists are referred to by different names, such as array, depending on the programming language.

    • Exclusion statement (EK AAP-1.D.6): The use of linked lists is outside the scope of this course and the AP Exam.

  • AAP-1.D.7 The exam reference sheet provides the notation

    [value1, value2, value3, ...]

    to create a list with those values as the first, second, third, and so on items. For example,

    • Text:

      aList ← [value1, value2, value3, ...]

      Block:

      aList ← value1, value2, value3

      creates a new list that contains the values value1, value2, value3, and ... at indices 1, 2, 3, and ... respectively and assigns it to aList.

    • Text:

      aList ← []

      Block:

      aList ← (empty)

      creates a new empty list and assigns it to aList.

    • Text:

      aList ← bList

      Block:

      aList ← bList

      assigns a copy of the list bList to the list aList. For example, if bList contains [20, 40, 60], then aList will also contain [20, 40, 60] after the assignment.

  • AAP-1.D.8 The exam reference sheet describes a list structure whose index values are 1 through the number of elements in the list, inclusive. For all list operations, if a list index is less than 1 or greater than the length of the list, an error message is produced and the program will terminate.

来源:美国大学理事会 AP 课程与考试说明

数据抽象(data abstraction)让你通过给一个数据搜集一个单一的名字来管理复杂性——例如,一个列表而不是几十个分开的变量。它隐藏细节:你使用命名的搜集而不担心它如何被存储。列表(下面)是课程的主要数据抽象。

词汇表 训练
英文 中文 拼音
Data abstraction 数据抽象 shù jù chōu xiàng
abstraction 抽象 chōu xiàng
练习卷
3.3

数学表达式
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.A
Express an algorithm that uses sequencing without using a programming language. [Skill 2.A]

  • AAP-2.A.1 An algorithm is a finite set of instructions that accomplish a specific task.
  • AAP-2.A.2 Beyond visual and textual programming languages, algorithms can be expressed in a variety of ways, such as natural language, diagrams, and pseudocode.
  • AAP-2.A.3 Algorithms executed by programs are implemented using programming languages.
  • AAP-2.A.4 Every algorithm can be constructed using combinations of sequencing, selection, and iteration.

AAP-2.B
Represent a step-by-step algorithmic process using sequential code statements. [Skill 2.B]

  • AAP-2.B.1 Sequencing is the application of each step of an algorithm in the order in which the code statements are given.
  • AAP-2.B.2 A code statement is a part of program code that expresses an action to be carried out.
  • AAP-2.B.3 An expression can consist of a value, a variable, an operator, or a procedure call that returns a value.
  • AAP-2.B.4 Expressions are evaluated to produce a single value.
  • AAP-2.B.5 The evaluation of expressions follows a set order of operations defined by the programming language.
  • AAP-2.B.6 Sequential statements execute in the order they appear in the code segment.
  • AAP-2.B.7 Clarity and readability are important considerations when expressing an algorithm in a programming language.

AAP-2.C
Evaluate expressions that use arithmetic operators. [Skill 4.B]

  • AAP-2.C.1 Arithmetic operators are part of most programming languages and include addition, subtraction, multiplication, division, and modulus operators.

  • AAP-2.C.2 The exam reference sheet provides a MOD b, which evaluates to the remainder when a is divided by b. Assume that a is an integer greater than or equal to 0 and b is an integer greater than 0. For example, 17 MOD 5 evaluates to 2.

  • AAP-2.C.3 The exam reference sheet provides the arithmetic operators +, -, *, /, and MOD.

    Text and Block:

    • a + b
    • a - b
    • a * b
    • a / b
    • a MOD b

    These are used to perform arithmetic on a and b. For example, 17 / 5 evaluates to 3.4.

  • AAP-2.C.4 The order of operations used in mathematics applies when evaluating expressions. The MOD operator has the same precedence as the * and / operators.

来源:美国大学理事会 AP 课程与考试说明

程序用运算符 +、-、*、/ 和 MOD(一次除法的余数(remainder),例如 17 MOD 5 是 2)计算。表达式遵循通常的运算顺序。MOD 对测试可除性(n MOD 2 = 0 意味着 n 是偶数)和把值环绕一个范围尤其有用。

探索

Evaluate an expression step by step

An expression is evaluated with order of operations: multiplication and division happen before addition and subtraction, left to right.

词汇表 训练
英文 中文 拼音
remainder 余数 yú shù
练习卷
3.4

字符串
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.D
Evaluate expressions that manipulate strings. [Skill 4.B]

  • AAP-2.D.1 String concatenation joins together two or more strings end-to-end to make a new string.
  • AAP-2.D.2 A substring is part of an existing string.

来源:美国大学理事会 AP 课程与考试说明

一个字符串(string)是一个有序的字符序列,像 "hello"。程序连接字符串(拼接(concatenation))并找它们的长度。字符串表示文本——名字、消息、序列——而且是一个常见的程序输入和输出。

词汇表 训练
英文 中文 拼音
string 字符串 zì fú chuàn
concatenation 拼接 pīn jiē
练习卷
3.5

布尔表达式
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.E
For relationships between two variables, expressions, or values:
a. Write expressions using relational operators. [Skill 2.B]
b. Evaluate expressions that use relational operators. [Skill 4.B]

  • AAP-2.E.1 A Boolean value is either true or false.

  • AAP-2.E.2 The exam reference sheet provides the following relational operators: =, ≠, >, <, ≥, and ≤.

    Text and Block:

    • a = b
    • a ≠ b
    • a > b
    • a < b
    • a ≥ b
    • a ≤ b

    These are used to test the relationship between two variables, expressions, or values. A comparison using a relational operator evaluates to a Boolean value. For example, a = b evaluates to true if a and b are equal; otherwise, it evaluates to false.

AAP-2.F
For relationships between Boolean values:
a. Write expressions using logical operators. [Skill 2.B]
b. Evaluate expressions that use logic operators. [Skill 4.B]

  • AAP-2.F.1 The exam reference sheet provides the logical operators NOT, AND, and OR, which evaluate to a Boolean value.

  • AAP-2.F.2 The exam reference sheet provides

    Text:

    NOT condition

    Block:

    NOT condition

    which evaluates to true if condition is false; otherwise it evaluates to false.

  • AAP-2.F.3 The exam reference sheet provides

    Text:

    condition1 AND condition2

    Block:

    condition1 AND condition2

    which evaluates to true if both condition1 and condition2 are true; otherwise it evaluates to false.

  • AAP-2.F.4 The exam reference sheet provides

    Text:

    condition1 OR condition2

    Block:

    condition1 OR condition2

    which evaluates to true if condition1 is true or if condition2 is true or if both condition1 and condition2 are true; otherwise it evaluates to false.

  • AAP-2.F.5 The operand for a logical operator is either a Boolean expression or a single Boolean value.

来源:美国大学理事会 AP 课程与考试说明

一个布尔表达式(Boolean expression)求值为 true 或 false。它使用关系运算符(=、≠、<、>、≤、≥)和逻辑运算符 NOT、AND、OR:

三个运算符家族:算术、关系和逻辑
三个运算符家族:算术、关系和逻辑
  • NOT 反转一个值,
  • AND 只在两侧都真时为真,
  • OR 在至少一侧为真时为真。

这些条件驱动每个决定和循环。

探索

Try the OR truth table

A Boolean expression is either true (1) or false (0). OR is true when at least one input is true; flip the inputs to see every case.

词汇表 训练
英文 中文 拼音
Boolean expression 布尔表达式 bù ěr biǎo dá shì
练习卷
3.6

条件语句
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.G
Express an algorithm that uses selection without using a programming language. [Skill 2.A]

  • AAP-2.G.1 Selection determines which parts of an algorithm are executed based on a condition being true or false.

AAP-2.H
For selection:
a. Write conditional statements. [Skill 2.B]
b. Determine the result of conditional statements. [Skill 4.B]

  • AAP-2.H.1 Conditional statements, or "if-statements," affect the sequential flow of control by executing different statements based on the value of a Boolean expression.

  • AAP-2.H.2 The exam reference sheet provides

    Text:

    IF(condition) { <block of statements> }

    Block:

    IF condition block of statements

    in which the code in block of statements is executed if the Boolean expression condition evaluates to true; no action is taken if condition evaluates to false.

  • AAP-2.H.3 The exam reference sheet provides

    Text:

    IF(condition) { <first block of statements> } ELSE { <second block of statements> }

    Block:

    IF condition first block of statements ELSE second block of statements

    in which the code in first block of statements is executed if the Boolean expression condition evaluates to true; otherwise, the code in second block of statements is executed.

来源:美国大学理事会 AP 课程与考试说明

一个条件语句(选择)(conditional (selection))选择运行哪段代码。IF 只在它的条件为真时运行一个块;ELSE 给出一个替代:

选择基于一个条件在路径之间选择
选择基于一个条件在路径之间选择
IF (score ≥ 60)
{
    DISPLAY("Pass")
}
ELSE
{
    DISPLAY("Fail")
}
探索

Follow an if / else decision

A conditional runs one branch or another depending on whether its condition is true. Slide the value across the threshold and watch which branch is taken.

词汇表 训练
英文 中文 拼音
conditional (selection) 条件语句 tiáo jiàn yǔ jù
练习卷
3.7

嵌套条件语句
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.I
For nested selection:
a. Write nested conditional statements. [Skill 2.B]
b. Determine the result of nested conditional statements. [Skill 4.B]

  • AAP-2.I.1 Nested conditional statements consist of conditional statements within conditional statements.

来源:美国大学理事会 AP 课程与考试说明

一个嵌套条件(nested conditional)把一个 IF 放进另一个里面(或链接 ELSE IF)以在多于两条路径中选择。只有第一个匹配的分支运行:

IF (g ≥ 90)      { grade ← "A" }
ELSE IF (g ≥ 80) { grade ← "B" }
ELSE             { grade ← "C" }
词汇表 训练
英文 中文 拼音
nested conditional 嵌套条件 qiàn tào tiáo jiàn
练习卷
3.8

迭代
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.J
Express an algorithm that uses iteration without using a programming language. [Skill 2.A]

  • AAP-2.J.1 Iteration is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.

AAP-2.K
For iteration:
a. Write iteration statements. [Skill 2.B]
b. Determine the result or side effect of iteration statements. [Skill 4.B]

  • AAP-2.K.1 Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met.

  • AAP-2.K.2 The exam reference sheet provides

    Text:

    REPEAT n TIMES { <block of statements> }

    Block:

    REPEAT n TIMES block of statements

    in which the block of statements is executed n times.

  • AAP-2.K.3 The exam reference sheet provides

    Text:

    REPEAT UNTIL(condition) { <block of statements> }

    Block:

    REPEAT UNTIL condition block of statements

    in which the code in block of statements is repeated until the Boolean expression condition evaluates to true.

  • AAP-2.K.4 In REPEAT UNTIL(condition) iteration, an infinite loop occurs when the ending condition will never evaluate to true.

  • AAP-2.K.5 In REPEAT UNTIL(condition) iteration, if the conditional evaluates to true initially, the loop body is not executed at all, due to the condition being checked before the loop.

来源:美国大学理事会 AP 课程与考试说明

迭代(一个循环)(iteration (a loop))重复指令。AP 伪代码有两种形式:

一个前置条件(WHILE)循环在主体之前测试,所以它可能运行零次
一个前置条件(WHILE)循环在主体之前测试,所以它可能运行零次
REPEAT 5 TIMES        // a fixed count
{
    DISPLAY("hi")
}

REPEAT UNTIL (found)  // until a condition becomes true
{
    ...
}

一个从不满足它停止条件的循环是一个无限循环(infinite loop)。

探索

Trace a loop one pass at a time

A loop repeats a block while its counter runs through a range. Step through to watch the counter and the running total update each pass.

词汇表 训练
英文 中文 拼音
Iteration (a loop) 迭代 dié dài
infinite loop 无限循环 wú xiàn xún huán
练习卷
3.9

开发算法
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.L
Compare multiple algorithms to determine if they yield the same side effect or result. [Skill 1.D]

  • AAP-2.L.1 Algorithms can be written in different ways and still accomplish the same tasks.
  • AAP-2.L.2 Algorithms that appear similar can yield different side effects or results.
  • AAP-2.L.3 Some conditional statements can be written as equivalent Boolean expressions.
  • AAP-2.L.4 Some Boolean expressions can be written as equivalent conditional statements.
  • AAP-2.L.5 Different algorithms can be developed or used to solve the same problem.

AAP-2.M
For algorithms:
a. Create algorithms. [Skill 2.A]
b. Combine and modify existing algorithms. [Skill 2.B]

  • AAP-2.M.1 Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms.
  • AAP-2.M.2 Knowledge of existing algorithms can help in constructing new ones. Some existing algorithms include:
    • determining the maximum or minimum value of two or more numbers
    • computing the sum or average of two or more numbers
    • identifying if an integer is or is not evenly divisible by another integer
    • determining a robot's path through a maze
  • AAP-2.M.3 Using existing correct algorithms as building blocks for constructing another algorithm has benefits such as reducing development time, reducing testing, and simplifying the identification of errors.

来源:美国大学理事会 AP 课程与考试说明

一个算法(algorithm)是解决一个问题的一个有限的步骤序列,由顺序(sequencing)、选择(selection)和迭代(iteration)构建。不同的算法能解决同一个问题,而你应当能够组合和修改现有的算法(例如,数一个列表里满足一个条件的值,或找最大的)。手工跟踪一个算法以检查它正确。

一个流程图用标准符号布置一个算法
一个流程图用标准符号布置一个算法
词汇表 训练
英文 中文 拼音
algorithm 算法 suàn fǎ
练习卷
3.10

列表
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.N
For list operations:
a. Write expressions that use list indexing and list procedures. [Skill 2.B]
b. Evaluate expressions that use list indexing and list procedures. [Skill 4.B]

  • AAP-2.N.1 The exam reference sheet provides basic operations on lists, including:

    • accessing an element by index

      Text:

      aList[i]

      Block:

      aList i

      accesses the element of aList at index i. The first element of aList is at index 1 and is accessed using the notation aList[1].

    • assigning a value of an element of a list to a variable

      Text:

      x ← aList[i]

      Block:

      x ← aList i

      assigns the value of aList[i] to the variable x.

    • assigning a value to an element of a list

      Text:

      aList[i] ← x

      Block:

      aList i ← x

      assigns the value of x to aList[i].

      Text:

      aList[i] ← aList[j]

      Block:

      aList i ← aList j

      assigns the value of aList[j] to aList[i].

    • inserting elements at a given index

      Text:

      INSERT(aList, i, value)

      Block:

      INSERT aList, i, value

      shifts to the right any values in aList at indices greater than or equal to i. The length of the list is increased by 1, and value is placed at index i in aList.

    • adding elements to the end of the list

      Text:

      APPEND(aList, value)

      Block:

      APPEND aList, value

      increases the length of aList by 1, and value is placed at the end of aList.

    • removing elements

      Text:

      REMOVE(aList, i)

      Block:

      REMOVE aList, i

      removes the item at index i in aList and shifts to the left any values at indices greater than i. The length of aList is decreased by 1.

    • determining the length of a list

      Text:

      LENGTH(aList)

      Block:

      LENGTH aList

      evaluates to the number of elements currently in aList.

  • AAP-2.N.2 List procedures are implemented in accordance with the syntax rules of the programming language.

AAP-2.O
For algorithms involving elements of a list:
a. Write iteration statements to traverse a list. [Skill 2.B]
b. Determine the result of an algorithm that includes list traversals. [Skill 4.B]

  • AAP-2.O.1 Traversing a list can be a complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed.

    • Exclusion statement (EK AAP-2.O.1): Traversing multiple lists at the same time using the same index for both (parallel traversals) is outside the scope of this course and the AP Exam.

  • AAP-2.O.2 Iteration statements can be used to traverse a list.

  • AAP-2.O.3 The exam reference sheet provides

    Text:

    FOR EACH item IN aList { <block of statements> }

    Block:

    FOR EACH item IN aList block of statements

    The variable item is assigned the value of each element of aList sequentially, in order, from the first element to the last element. The code in block of statements is executed once for each assignment of item.

  • AAP-2.O.4 Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are often used with lists include:

    • determining a minimum or maximum value in a list
    • computing a sum or average of a list of numbers

  • AAP-2.O.5 Linear search or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.

来源:美国大学理事会 AP 课程与考试说明

一个列表(list)是一个名字下的一个有序的值搜集,课程的关键数据抽象。AP 伪代码从 1 索引:

一个列表在一个变量里持有许多值,每个由它的索引找到
一个列表在一个变量里持有许多值,每个由它的索引找到
scores ← [88, 74, 95]
DISPLAY(scores[1])          // 88
scores[2] ← 80              // replace the 2nd value
APPEND(scores, 60)          // add to the end
INSERT(scores, 1, 100)      // insert at index 1
REMOVE(scores, 3)           // delete the 3rd element
LENGTH(scores)              // how many elements

用一个循环遍历一个列表以求和、计数、搜索,或找一个最大值:

FOR EACH x IN scores
{
    total ← total + x
}
词汇表 训练
英文 中文 拼音
list 列表 liè biǎo
练习卷
3.11

二分查找
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-2
The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

AAP-2.P
For binary search algorithms:
a. Determine the number of iterations required to find a value in a data set. [Skill 1.D]
b. Explain the requirements necessary to complete a binary search. [Skill 1.A]

  • AAP-2.P.1 The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated.
    • Exclusion statement (EK AAP-2.P.1): Specific implementations of the binary search are outside the scope of the course and the AP Exam.
  • AAP-2.P.2 Data must be in sorted order to use the binary search algorithm.
  • AAP-2.P.3 Binary search is often more efficient than sequential/linear search when applied to sorted data.

来源:美国大学理事会 AP 课程与考试说明

二分搜索(binary search)在一个排序的列表里比检查每个元素快得多地找到一个值。它看中间的元素,然后丢弃不能包含目标的那一半,重复直到找到。每一步把搜索空间减半,所以一个 $n$ 个项的列表取约 $\log_2 n$ 步。它需要数据先被排序。

二分搜索在每一步把范围减半(列表必须被排序)
二分搜索在每一步把范围减半(列表必须被排序)

Worked example. 搜索一个 $8$ 个项的排序列表,二分搜索每一步把范围减半:$8\rightarrow4\rightarrow2\rightarrow1$,最多 $3$ 次比较($\log_2 8=3$),而一个线性搜索可能取多达 $8$。优势爆炸式增长:约 $1{,}000$ 个项只需要 $\approx10$ 个二分搜索步(但多达 $1{,}000$ 个线性的),而 $1{,}000{,}000$ 个项只需要 $\approx20$。减半是使它成为一个合理时间算法的东西。

词汇表 训练
英文 中文 拼音
Binary search 二分搜索 èr fēn sōu suǒ
练习卷
3.12

调用过程
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-3
Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.

AAP-3.A
For procedure calls:
a. Write statements to call procedures. [Skill 3.B]
b. Determine the result or effect of a procedure call. [Skill 4.B]

  • AAP-3.A.1 A procedure is a named group of programming instructions that may have parameters and return values.

  • AAP-3.A.2 Procedures are referred to by different names, such as method or function, depending on the programming language.

  • AAP-3.A.3 Parameters are input variables of a procedure. Arguments specify the values of the parameters when a procedure is called.

  • AAP-3.A.4 A procedure call interrupts the sequential execution of statements, causing the program to execute the statements within the procedure before continuing. Once the last statement in the procedure (or a return statement) has executed, flow of control is returned to the point immediately following where the procedure was called.

  • AAP-3.A.5 The exam reference sheet provides

    procName(arg1, arg2, ...)

    as a way to call

    Text:

    PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> }

    Block:

    PROCEDURE procName parameter1, parameter2,... block of statements

    which takes zero or more arguments; arg1 is assigned to parameter1, arg2 is assigned to parameter2, and so on.

  • AAP-3.A.6 The exam reference sheet provides the procedure

    Text:

    DISPLAY(expression)

    Block:

    DISPLAY expression

    to display the value of expression, followed by a space.

  • AAP-3.A.7 The exam reference sheet provides the

    Text:

    RETURN(expression)

    Block:

    RETURN expression

    statement, which is used to return the flow of control to the point where the procedure was called and to return the value of expression.

  • AAP-3.A.8 The exam reference sheet provides

    result ← procName(arg1, arg2, ...)

    to assign to result the "value of the procedure" being returned by calling

    Text:

    PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> RETURN(expression) }

    Block:

    PROCEDURE procName parameter1, parameter2,... block of statements RETURN expression

  • AAP-3.A.9 The exam reference sheet provides procedure

    Text:

    INPUT()

    Block:

    INPUT

    which accepts a value from the user and returns the input value.

来源:美国大学理事会 AP 课程与考试说明

一个过程(函数)(procedure (function))是一个命名的、可重用的代码块。调用它以你提供的实参(arguments)运行它的代码,而它可能返回一个值:

sum ← Add(3, 4)      // call, passing 3 and 4

过程让你使用代码而不知道它的内部工作——过程抽象(procedural abstraction)。

词汇表 训练
英文 中文 拼音
procedure (function) 过程 guò chéng
procedural abstraction 过程抽象 guò chéng chōu xiàng
练习卷
3.13

开发过程
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-3
Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.

AAP-3.B
Explain how the use of procedural abstraction manages complexity in a program. [Skill 3.C]

  • AAP-3.B.1 One common type of abstraction is procedural abstraction, which provides a name for a process and allows a procedure to be used only knowing what it does, not how it does it.
  • AAP-3.B.2 Procedural abstraction allows a solution to a large problem to be based on the solutions of smaller subproblems. This is accomplished by creating procedures to solve each of the subproblems.
  • AAP-3.B.3 The subdivision of a computer program into separate subprograms is called modularity.
  • AAP-3.B.4 A procedural abstraction may extract shared features to generalize functionality instead of duplicating code. This allows for program code reuse, which helps manage complexity.
  • AAP-3.B.5 Using parameters allows procedures to be generalized, enabling the procedures to be reused with a range of input values or arguments.
  • AAP-3.B.6 Using procedural abstraction helps improve code readability.
  • AAP-3.B.7 Using procedural abstraction in a program allows programmers to change the internals of the procedure (to make it faster, more efficient, use less storage, etc.) without needing to notify users of the change as long as what the procedure does is preserved.

AAP-3.C
Develop procedural abstractions to manage complexity in a program by writing procedures. [Skill 3.B]

  • AAP-3.C.1 The exam reference sheet provides

    Text:

    PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> }

    Block:

    PROCEDURE procName parameter1, parameter2,... block of statements

    which is used to define a procedure that takes zero or more arguments. The procedure contains block of statements.

  • AAP-3.C.2 The exam reference sheet provides

    Text:

    PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> RETURN(expression) }

    Block:

    PROCEDURE procName parameter1, parameter2,... block of statements RETURN expression

    which is used to define a procedure that takes zero or more arguments. The procedure contains block of statements and returns the value of expression. The RETURN statement may appear at any point inside the procedure and causes an immediate return from the procedure back to the calling statement.

来源:美国大学理事会 AP 课程与考试说明

你用一个名字、参数(parameters)(输入)和一个主体定义一个过程,并可选地 RETURN 一个结果:

把一个程序分解成过程和子过程
把一个程序分解成过程和子过程
PROCEDURE Add(a, b)
{
    RETURN(a + b)
}

写你自己的过程减少重复、把一个大问题分解成命名的片段,并使程序可读且更容易测试——抽象(abstraction)的本质。

练习卷
3.14

库
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-3
Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.

AAP-3.D
Select appropriate libraries or existing code segments to use in creating new programs. [Skill 2.B]

  • AAP-3.D.1 A software library contains procedures that may be used in creating new programs.
  • AAP-3.D.2 Existing code segments can come from internal or external sources, such as libraries or previously written code.
  • AAP-3.D.3 The use of libraries simplifies the task of creating complex programs.
  • AAP-3.D.4 Application program interfaces (APIs) are specifications for how the procedures in a library behave and can be used.
  • AAP-3.D.5 Documentation for an API/library is necessary in understanding the behaviors provided by the API/library and how to use them.

来源:美国大学理事会 AP 课程与考试说明

一个库(library)是一个其他人能重用的现成过程的搜集。一个 API(应用程序接口,Application Program Interface)记录每个过程做什么、它的参数,和它的结果——所以你能使用它而不看它的代码。库节省时间并让你能建立在现有的、经过测试的工作之上。

词汇表 训练
英文 中文 拼音
library 库 kù
Interface 应用程序接口 yìng yòng chéng xù jiē kǒu
练习卷
3.15

随机值
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-3
Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.

AAP-3.E
For generating random values:
a. Write expressions to generate possible values. [Skill 2.B]
b. Evaluate expressions to determine the possible results. [Skill 4.B]

  • AAP-3.E.1 The exam reference sheet provides

    Text:

    RANDOM(a, b)

    Block:

    RANDOM a, b

    which generates and returns a random integer from a to b, inclusive. Each result is equally likely to occur. For example, RANDOM(1, 3) could return 1, 2, or 3.

  • AAP-3.E.2 Using random number generation in a program means each execution may produce a different result.

来源:美国大学理事会 AP 课程与考试说明

RANDOM(a, b) 返回一个从 a 到 b(含)的随机整数,让一个程序产生不可预测的结果——用于游戏、抽样,或模拟。每个调用可能给出一个不同的值,所以一个使用随机性的程序每次运行行为不同。

练习卷
3.16

模拟
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-3
Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.

AAP-3.F
For simulations:
a. Explain how computers can be used to represent real-world phenomena or outcomes. [Skill 1.A]
b. Compare simulations with real-world contexts. [Skill 1.D]

  • AAP-3.F.1 Simulations are abstractions of more complex objects or phenomena for a specific purpose.
  • AAP-3.F.2 A simulation is a representation that uses varying sets of values to reflect the changing state of a phenomenon.
  • AAP-3.F.3 Simulations often mimic real-world events with the purpose of drawing inferences, allowing investigation of a phenomenon without the constraints of the real world.
  • AAP-3.F.4 The process of developing an abstract simulation involves removing specific details or simplifying functionality.
  • AAP-3.F.5 Simulations can contain bias derived from the choices of real-world elements that were included or excluded.
  • AAP-3.F.6 Simulations are most useful when real-world events are impractical for experiments (e.g., too big, too small, too fast, too slow, too expensive, or too dangerous).
  • AAP-3.F.7 Simulations facilitate the formulation and refinement of hypotheses related to the objects or phenomena under consideration.
  • AAP-3.F.8 Random number generators can be used to simulate the variability that exists in the real world.

来源:美国大学理事会 AP 课程与考试说明

一个模拟(simulation)是一个为一个现实世界过程建模以安全而廉价地研究它的程序。模拟简化现实(它们省略细节)并常常用随机性来模仿偶然事件。它们让你测试在现实生活里会太昂贵、缓慢或危险的场景——但它们的结果只与它们的假设一样好。

词汇表 训练
英文 中文 拼音
simulation 模拟 mó nǐ
练习卷
3.17

算法效率
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-4
There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.

AAP-4.A
For determining the efficiency of an algorithm:
a. Explain the difference between algorithms that run in reasonable time and those that do not. [Skill 1.D]
b. Identify situations where a heuristic solution may be more appropriate. [Skill 1.D]

  • AAP-4.A.1 A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.
  • AAP-4.A.2 A decision problem is a problem with a yes/no answer (e.g., is there a path from A to B?). An optimization problem is a problem with the goal of finding the "best" solution among many (e.g., what is the shortest path from A to B?).
  • AAP-4.A.3 Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input.
    • Exclusion statement (EK AAP-4.A.3): Formal analysis of algorithms (Big-O) and formal reasoning using mathematical formulas are outside the scope of this course and the AP Exam.
  • AAP-4.A.4 An algorithm's efficiency is determined through formal or mathematical reasoning.
  • AAP-4.A.5 An algorithm's efficiency can be informally measured by determining the number of times a statement or group of statements executes.
  • AAP-4.A.6 Different correct algorithms for the same problem can have different efficiencies.
  • AAP-4.A.7 Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
  • AAP-4.A.8 Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.
  • AAP-4.A.9 A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.
    • Exclusion statement (AAP-4.A.9): Specific heuristic solutions are outside the scope of this course and the AP Exam.

来源:美国大学理事会 AP 课程与考试说明

效率(efficiency)是一个算法随着它的输入增长需要多少时间(或内存)。一个合理时间(reasonable-time)算法的工作像输入大小的一个多项式那样增长(例如线性或二次);一个不合理时间(unreasonable-time)算法增长得远快(例如每加一个项就加倍),对大输入变得不切实际。一个更快的算法能使一个先前不可能的问题可解。有时一个精确答案取太久,所以一个启发式(heuristic)——一个快速找到一个足够好答案的方法——被改用。

一个算法的运行时间如何随输入大小 n 增长
一个算法的运行时间如何随输入大小 n 增长
词汇表 训练
英文 中文 拼音
Efficiency 效率 xiào lǜ
heuristic 启发式 qǐ fā shì
练习卷
3.18

不可判定问题
大纲
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-4
There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.

AAP-4.B
Explain the existence of undecidable problems in computer science. [Skill 1.A]

  • AAP-4.B.1 A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., "Is the number even?").
  • AAP-4.B.2 An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.
    • Exclusion statement (EK AAP-4.B.2): Determining whether a given problem is undecidable is outside the scope of this course and the AP Exam.
  • AAP-4.B.3 An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.

来源:美国大学理事会 AP 课程与考试说明

一些问题是不可判定(undecidable)的:没有算法能用一个正确的是/否答案解决它们的每个情况。这是计算的一个根本限制——不是需要一台更快计算机的问题,而是没有这样的算法能存在的一个证明。

考试技能: 能够通过跟踪确定一个代码段的结果、比较两个算法的效率(合理 vs 不合理时间),并在一个程序里辨认过程和数据抽象。

词汇表 训练
英文 中文 拼音
undecidable 不可判定 bù kě pàn dìng
练习卷
3.18

考试技巧
  • 知道一个变量是一个值的命名存储并逐步跟踪赋值如何更新它。
  • 仔细读 AP 伪代码——a <- expression 赋值,而列表在考试参考表上是1 索引的。
  • 把一个变量与一个列表(一个由索引访问的搜集)区分开并正确地使用列表操作。
  • 用正确的优先级和布尔逻辑(AND、OR、NOT)求表达式的值。
  • 挑选清晰的、有意义的变量名——书面任务奖励可读的代码。

本主题的互动课程

逐步学习,并即时检测练习。

AP 计算机科学原理历年真题

AP 计算机科学原理的更多主题

登录或创建账号

IGCSE, A-Level & AP