Notations, stepwise refinement and logic
| English | Chinese | Pinyin |
|---|---|---|
| notation | 记法 | jì fǎ |
| structured English | 结构化英语 | jié gòu huà yīng yǔ |
| pseudocode | 伪代码 | wěi dài mǎ |
| flowchart | 流程图 | liú chéng tú |
| stepwise refinement | 逐步求精 | zhú bù qiú jīng |
| logic statement | 逻辑语句 | luó jí yǔ jù |
| Boolean | 布尔 | bù ěr |
| precedence | 优先级 | yōu xiān jí |
| De Morgan's law | 德摩根定律 | dé mó gēn dìng lǜ |
The first algorithm had no language to be written in
- In 1843 Ada Lovelace published the steps for computing Bernoulli numbers on Babbage's Analytical Engine, a machine that was never built.
- There was no programming language, so she wrote the algorithm as a numbered table of operations: a notation 记法 of her own.
- Every algorithm still starts that way. You write it down in some notation, check it, and only then turn it into code.
- This lesson is about the three notations the exam uses, how to move between them, and how to write the conditions inside them.
Three notations
- Structured English 结构化英语: ordinary sentences, indented, with a few fixed words such as
IF,FOR EACH,REPEAT. Good for a first outline. - Pseudocode 伪代码: the keyword notation (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), closest to real code and marked against Cambridge's guide. - Flowchart 流程图: a diagram of standard shapes. Rounded rectangle for
START/STOP, parallelogram for input and output, rectangle for a process, diamond for a decision, arrows for the flow.
A flowchart for averaging a list of numbers, drawn with the standard shapes
In a flowchart, which shape represents a decision?
A diamond is a decision; rounded rectangle = start/stop, parallelogram = input/output, rectangle = process.
Match each flowchart shape to its meaning.
Parallelogram = I/O, rectangle = process, rounded rectangle = start/stop, diamond = decision.
Match each notation to its description.
All three describe the same algorithm at different distances from the code.
Worked example: structured English to pseudocode
- Structured English: Set the total to zero. For each of the N numbers, add it to the total. Divide the total by N and output the result.
- Each sentence becomes one construct: an assignment, a
FORloop with an assignment inside it, then an assignment and an output.
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- The order of the sentences is the order of the statements. Nothing is added and nothing is left out.
In the averaging algorithm, the FOR loop that adds each number to the total is an example of the ____ construct.
Repeating a block for each number is iteration. The assignment inside it stores the running total.
Worked example: pseudocode to flowchart
- Take the same algorithm.
STARTgoes in a rounded rectangle,Total ← 0andIndex ← 1in rectangles. - The
FORloop becomes a diamond askingIndex <= N?. The Yes exit leads to the rectangleTotal ← Total + Number[Index], thenIndex ← Index + 1, and an arrow back up to the diamond. - The No exit continues to
Average ← Total / N, an output parallelogram, andSTOP. - Label both exits of every diamond. A diamond with one unlabelled exit is not a decision.
Stepwise refinement
- Stepwise refinement 逐步求精 means writing an algorithm as a short outline, then expanding each step into more detailed sub-steps, and repeating until every step can be coded directly.
- Each level keeps the structure of the level above and adds detail. The outline is not thrown away: it becomes the structure of the program.
- The design stops when a step is one line of pseudocode or one module you already have.
Stepwise refinement expands each step until it can be coded
Stepwise refinement is the technique of:
You refine a high-level outline level by level, adding detail while keeping the structure.
Worked example: three levels
- Level 1: Process the exam results.
- Level 2: Input each mark. Calculate the mean. Count how many passed. Output the report.
- Level 3, refining "count how many passed":
Passes ← 0, thenFOReach mark,IF Mark >= 40 THEN Passes ← Passes + 1. - Asked to "describe stepwise refinement", give the three ideas: start from an outline, expand each step into smaller steps, stop when each step can be programmed.
Stepwise refinement: outline to code
Step down the levels. You start with the whole task in one line and keep expanding each step into smaller ones — until every step is simple enough to code directly.
In stepwise refinement, each new level replaces the level above it, so the original outline is thrown away.
Each level keeps the structure of the one above and adds detail. The outline becomes the shape of the finished program.
Logic statements
- A logic statement 逻辑语句 is a Boolean 布尔 condition: it is either
TRUEorFALSE, and it controls anIF, aWHILEor anUNTIL. - It is built from comparisons (
=,<>,<,>,<=,>=) joined byAND,ORandNOT. Mark >= 0 AND Mark <= 100is true only for marks in range.Age < 12 OR Age >= 65is true for children and pensioners.
Comparisons joined by AND, OR and NOT make one condition
Precedence and brackets
- Operators are applied in a fixed order of precedence 优先级:
NOTfirst, thenAND, thenOR. - So
A OR B AND CmeansA OR (B AND C), not(A OR B) AND C. WithA = TRUE,B = FALSE,C = FALSEthe first isTRUEand the second isFALSE. - Use brackets whenever a condition mixes
ANDandOR. They cost nothing and remove the ambiguity.
Put the logic operators in order of precedence, highest (evaluated first) to lowest.
NOT binds tightest, then AND, then OR — use brackets when in doubt.
With no brackets, what does A OR B AND C mean?
AND has higher precedence than OR, so it is evaluated first. Bracket the condition anyway, so nobody has to remember.
De Morgan's laws
- De Morgan's law 德摩根定律:
NOT (A AND B)is the same as(NOT A) OR (NOT B), andNOT (A OR B)is the same as(NOT A) AND (NOT B). - In words: "not (registered and paid)" means "not registered, or not paid".
- Use it to simplify a condition, or to check one: pick values for
AandB, work out both sides, and they must agree in every case.
By De Morgan's law, NOT (A AND B) is the same as (NOT A) OR (NOT B).
NOT distributes over the bracket and flips AND↔OR; likewise NOT (A OR B) = (NOT A) AND (NOT B).
Worked example: a condition from words
- Rule: a student may sit the exam if they are registered and have either paid or hold a bursary, but not if they are suspended.
- Name the Boolean variables:
Registered,Paid,Bursary,Suspended. - Statement:
Registered AND (Paid OR Bursary) AND NOT Suspended. - The brackets around
Paid OR Bursaryare essential. Without them,ANDbinds first and a student with a bursary but no registration would get in.
Which conditions are equivalent to NOT (Registered AND Paid)? Select all that apply.
De Morgan turns NOT of an AND into an OR of the NOTs. The AND version is too strict: a student who is registered but has not paid should make the original condition TRUE, and it makes the AND version FALSE.
Marks that slip away
a = 1 OR 2is not a condition. Writea = 1 OR a = 2: each side ofORmust be a complete comparison.NOTapplies only to what follows it.NOT A AND Bmeans(NOT A) AND B.- A diamond needs two labelled exits, and a loop needs an arrow that goes back up. A flowchart with no arrow returning is not a loop.
- Structured English is still precise. "Deal with the marks" is not a step; "add the mark to the total" is.
To test whether a is 1 or 2, the correct condition is:
Each side of OR must be a full comparison: a = 1 OR a = 2. Writing a = 1 OR 2 is a common error.
You've got it
- three notations for one algorithm: structured English, pseudocode, flowchart (diamond = decision, back-arrow = loop)
- stepwise refinement: outline → expand each step → stop when a step can be coded
- a logic statement is a Boolean condition; precedence NOT → AND → OR, so bracket anything that mixes them
- De Morgan:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B