算法与编程

A variable 变量 is a named place that holds a value. The assignment 赋值 operator stores the value on the right into the variable on the left:

a ← 5
b ← a + 3      // b is now 8

A variable holds one value at a time; assigning again replaces it. Variables let a program store input, remember results, and reuse them.

Worked example (a failed swap). What is displayed?

a ← 3
b ← 7
a ← b
b ← a
DISPLAY(a)
DISPLAY(b)

It displays 7 7: the old value of a was replaced before it was copied. A swap needs a third variable: temp ← a, a ← b, b ← temp.

Data abstraction 数据抽象 lets you manage complexity by giving a single name to a collection of data – for example, a list rather than dozens of separate variables. It hides detail: you use the named collection without worrying about how it is stored. Lists (below) are the course's main data abstraction.

Programs compute with the operators +, -, *, /, and MOD (the remainder 余数 of a division, e.g. 17 MOD 5 is 2). Expressions follow the usual order of operations. MOD is especially useful for testing divisibility (n MOD 2 = 0 means n is even) and for wrapping values around a range.

Worked example. MOD has the same priority as * and /, so it is done before + and -:

The last two rows show the wrap-around: day numbers 0 to 6 never go past 6. Note that / in AP pseudocode is ordinary division, so 7 / 2 is 3.5.

A string 字符串 is an ordered sequence of characters, like "hello". Programs join strings (concatenation 拼接) and find their length. Strings represent text – names, messages, sequences – and are a common program input and output.

The exam reference sheet has no string procedures, so a question defines the ones it uses, for example concat(str1, str2), which joins two strings, and substring(str, start, length), which returns length characters of str starting at position start.

Worked example. With those definitions and word ← "computer":

1. substring(word, 4, 3) starts at character 4, p, and takes 3 characters: "put".
2. substring(word, 1, 1) is "c".
3. concat(substring(word, 1, 3), "et") is concat("com", "et"), which is "comet".

Positions start at 1, so the last character of a string s is at position LENGTH(s); but always read the question's own definition first.

A Boolean expression 布尔表达式 evaluates to true or false. It uses relational operators (=, ≠, <, >, ≤, ≥) and logical operators NOT, AND, OR:

• NOT reverses a value,
• AND is true only when both sides are true,
• OR is true when at least one side is true.

These conditions drive every decision and loop.

Worked example. With age ← 15 and member ← false, evaluate (age ≥ 13 AND age ≤ 19) AND NOT member:

1. age ≥ 13 is true; age ≤ 19 is true; so the bracket is true.
2. NOT member is NOT false, true.
3. true AND true is true.

The opposite of x > 5 is x ≤ 5, not x < 5: the value 5 itself belongs to the opposite.

A conditional (selection) 条件语句 chooses which code to run. IF runs a block only when its condition is true; ELSE gives an alternative:

IF (score ≥ 60)
{
    DISPLAY("Pass")
}
ELSE
{
    DISPLAY("Fail")
}

Worked example. Two separate IFs are not the same as IF … ELSE. For n ← 12:

IF (n > 10)
{
    n ← n - 5
}
IF (n < 10)
{
    n ← n * 2
}
DISPLAY(n)

The first test is true, so n becomes 7; the second IF then tests the new value, 7 < 10, which is true, so n becomes 14. Written with ELSE, only the first branch would run and the program would display 7.

A nested conditional 嵌套条件 places one IF inside another (or chains ELSE IF) to choose among more than two paths. Only the first matching branch runs:

IF (g ≥ 90)      { grade ← "A" }
ELSE IF (g ≥ 80) { grade ← "B" }
ELSE             { grade ← "C" }

Iteration (a loop) 迭代 repeats instructions. AP pseudocode has two forms:

REPEAT 5 TIMES        // a fixed count
{
    DISPLAY("hi")
}

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

A loop that never meets its stopping condition is an infinite loop 无限循环.

REPEAT UNTIL (condition) checks the condition before each pass and stops as soon as it is true; if it is already true at the start, the body runs zero times.

Worked example. What is displayed, and how many times does the body run?

n ← 1
REPEAT UNTIL (n > 20)
{
    n ← n * 2
}
DISPLAY(n)

After pass 5, n > 20 is true, so the loop stops: the body ran 5 times and the program displays 32. If the body were n ← n * 1, n would stay 1 and the loop would never end.

An algorithm is not the same thing as code. Beyond visual and textual programming languages, an algorithm can be expressed in a variety of ways: in natural language (ordinary sentences), as a diagram such as a flowchart, or in pseudocode. Those forms are for people — they let you check the logic and agree on it before any language is chosen, and the same algorithm can then be written in any language.

When you do write it in a programming language, clarity and readability are important considerations, not decoration: meaningful variable names, consistent indentation and comments explaining why rather than what. The program has to be read and modified later by someone — often you — and an algorithm nobody can follow cannot be maintained or debugged.

An algorithm 算法 is a finite sequence of steps that solves a problem, built from sequencing, selection, and iteration. Different algorithms can solve the same problem, and you should be able to combine and modify existing algorithms (for example, count the values in a list that meet a condition, or find the largest). Trace an algorithm by hand to check it is correct.

A list 列表 is an ordered collection of values under one name, the course's key data abstraction. AP pseudocode indexes from 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

Traverse a list with a loop to sum, count, search, or find a maximum:

FOR EACH x IN scores
{
    total ← total + x
}

Worked example (tracing a list traversal). This procedure should count the scores of at least 80:

count ← 0
FOR EACH x IN [88, 74, 95, 80]
{
    IF (x ≥ 80)
    {
        count ← count + 1
    }
}
DISPLAY(count)

It displays 3. Two traps the exam sets: delete count ← 0 and count has no starting value, so the result is undefined; write x > 80 and the last score is missed, so it displays 2. Trace the boundary value every time.

Binary search 二分搜索 finds a value in a sorted list far faster than checking each element. It looks at the middle element, then discards the half that cannot contain the target, repeating until found. Each step halves the search space, so a list of $n$ items takes about $\log_2 n$ steps. It requires the data to be sorted first.

Worked example. Searching a sorted list of $8$ items, binary search halves the range each step: $8\rightarrow4\rightarrow2\rightarrow1$ in three halvings, and the one item left must still be checked, so at most $4$ comparisons ($\log_2 8+1$), whereas a linear search could take up to $8$. The advantage grows explosively: about $1{,}000$ items need only $\approx10$ binary-search steps (but up to $1{,}000$ linear ones), and $1{,}000{,}000$ items need just $\approx20$. Halving is what makes it a reasonable-time algorithm.

A procedure (function) 过程 is a named, reusable block of code. Calling it runs its code with the arguments you supply, and it may return a value:

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

Procedures let you use code without knowing its inner workings – procedural abstraction 过程抽象.

Worked example. What is displayed?

PROCEDURE Mystery(x, y)
{
    IF (x > y)
    {
        RETURN(x - y)
    }
    RETURN(y - x)
}
DISPLAY(Mystery(3, 10))
DISPLAY(Mystery(Mystery(9, 4), 2))

1. Mystery(3, 10): 3 > 10 is false, so it returns 10 - 3, which is 7.
2. The inner call Mystery(9, 4) returns 5; then Mystery(5, 2) returns 3.

It displays 7 3. The procedure returns the distance between two numbers. RETURN ends the procedure at once, so the second RETURN runs only when the IF was false.

You define a procedure with a name, parameters (inputs), and a body, and optionally RETURN a result:

PROCEDURE Add(a, b)
{
    RETURN(a + b)
}

Worked example. Write a procedure CountAbove(list, limit) that returns how many values in list are greater than limit.

PROCEDURE CountAbove(list, limit)
{
    count ← 0
    FOR EACH item IN list
    {
        IF (item > limit)
        {
            count ← count + 1
        }
    }
    RETURN(count)
}

CountAbove([4, 9, 12, 7], 6) returns 3. The parameters make it general: the same procedure works for any list and any limit, which is the point of a procedure. Displaying count inside the loop, or forgetting RETURN, are the usual mistakes.

Writing your own procedures reduces repetition, breaks a big problem into named pieces, and makes programs readable and easier to test – the essence of abstraction 抽象.

A library 库 is a collection of ready-made procedures that others can reuse. An API (Application Program Interface) 应用程序接口 documents what each procedure does, its parameters, and its result – so you can use it without seeing its code. Libraries save time and let you build on existing, tested work.

The documentation is part of the library. Documentation for an API or library is necessary in order to understand the behaviours it provides and how to use them — what each procedure expects as parameters, what it returns, and what it does at the edges. Without it you would have to read the source, which defeats the point of abstraction; with it you can use a procedure correctly without knowing how it works inside.

RANDOM(a, b) returns a random integer from a to b (inclusive), letting a program produce unpredictable results – for games, sampling, or simulations. Each call may give a different value, so a program using randomness behaves differently each run.

Worked example. A game gives a prize 30% of the time:

IF (RANDOM(1, 10) ≤ 3)
{
    DISPLAY("Prize!")
}

RANDOM(1, 10) has 10 equally likely values; 1, 2 and 3 are 3 of them, so the chance is $\frac{3}{10} = 30\%$. RANDOM(0, 10) ≤ 3 would be wrong: it has 11 values, 4 of them at most 3. To list every possible output of a program with RANDOM, try the smallest and largest values the call can return.

A simulation 模拟 is a program that models a real-world process to study it safely and cheaply. Simulations simplify reality (they leave out detail) and often use randomness to imitate chance events. They let you test scenarios that would be too costly, slow, or dangerous in real life – but their results are only as good as their assumptions.

A simulation is a way of doing science, not just a picture. Because it can be run many times, cheaply and with one variable changed at a time, a simulation facilitates the formulation and refinement of hypotheses about the object or phenomenon under consideration: you propose an explanation, run the model, compare the result with reality, and adjust either the hypothesis or the model. That is why a simulation's simplifications matter — a result only supports a hypothesis about the real world to the extent that what was left out does not matter.

Efficiency 效率 is how much time (or memory) an algorithm needs as its input grows. A reasonable-time algorithm's work grows like a polynomial of the input size (e.g. linear or quadratic); an unreasonable-time algorithm grows far faster (e.g. doubling with each added item), becoming impractical for large inputs. A faster algorithm can make a previously impossible problem solvable. Sometimes an exact answer takes too long, so a heuristic 启发式 – an approach that finds a good-enough answer quickly – is used instead.

Some problems are undecidable 不可判定: no algorithm can solve every case of them with a correct yes/no answer. This is a fundamental limit of computing – not a matter of needing a faster computer, but a proof that no such algorithm can exist.

The best-known example is the halting problem 停机问题: deciding, for any program and its input, whether the program will eventually stop or run for ever. A tool can answer this for many programs, but it has been proved that no algorithm answers it correctly for all of them. An undecidable problem may still be solved for particular cases; what is impossible is one algorithm for every case.

Exam skill: be able to determine a code segment's result by tracing it, compare two algorithms' efficiency (reasonable vs unreasonable time), and recognize procedural and data abstraction in a program.

• Know a variable is a named store for a value and trace how assignment updates it step by step.
• Read the AP pseudocode carefully — a <- expression assigns, and lists are 1-indexed on the exam reference sheet.
• Distinguish a variable from a list (a collection accessed by index) and use list operations correctly.
• Evaluate expressions with the right precedence and boolean logic (AND, OR, NOT).
• Pick clear, meaningful variable names — the written tasks reward readable code.