Algorithm design and problem-solving

The program development life cycle 程序开发生命周期 is the set of stages used to make a program. There are four stages.

Software is written by programmers, who follow the development life cycle

The four stages of program development; testing feeds back to fix and refine the design

A program flowchart sets out the steps and decisions of a program during the design stage

Analysis

In analysis you understand the problem. Two key skills help:

• abstraction 抽象 — keep only the important details and ignore the rest;
• decomposition 分解 — break a big problem into smaller, easier parts.

Design

In design you plan the solution, often using decomposition. You can show the parts as sub-systems 子系统 in a structure diagram 结构图 (a chart that splits a system into smaller boxes).

Coding and testing

In coding you write the program code. You use iterative testing 迭代测试 — test small parts again and again as you build them. In testing you run the whole program with test data 测试数据 to check it works.

You can plan a solution in three main ways.

• a structure diagram — shows the parts of a system and how they fit together;
• a flowchart 流程图 — a diagram using boxes and arrows to show the steps in order;
• pseudocode 伪代码 — steps written in simple, code-like English (not a real language).

A flowchart for the sum algorithm, using the standard symbols (start/end, input/output, process, decision)

An algorithm 算法 is a set of steps, in the right order, that solves a problem. Every algorithm can be split into three parts:

• input 输入 — the data that goes in;
• processing 处理 — the work done on the data;
• output 输出 — the result that comes out.

This is called decomposition into inputs, processes and outputs. For example, for "find the average of three marks": the inputs are the three marks; the processing is adding them and dividing by 3; the output is the average.

Every algorithm decomposes into input, processing and output — here, finding the average of three marks

When data is entered, you check it to reduce mistakes.

Validation 验证 checks that the data is sensible and follows the rules. It cannot check that the data is true, only that it is allowed.

Verification 核实 checks that data was copied or entered correctly (no mistakes while typing it in). Two methods:

• visual check 目视检查 — a person compares the typed data with the original;
• double entry 双重输入 — the data is entered twice and the two copies are compared.

A trace table 追踪表 records the value of each variable as an algorithm runs, step by step. It helps you:

A trace table records each variable's value as the program runs

• check that an algorithm works correctly;
• work out what an algorithm does by following it with given data.

Example: trace this algorithm with the input 5.

INPUT n
total ← 0
FOR i ← 1 TO n
    total ← total + i
NEXT i
OUTPUT total

The trace shows the algorithm adds up 1 to n. With input 5 the output is 15.

Worked example. Trace this algorithm and give the output.

x ← 20
count ← 0
WHILE x > 1
    x ← x DIV 2
    count ← count + 1
ENDWHILE
OUTPUT count

DIV gives only the whole-number part of a division. Take one row per pass: x becomes 10 (count 1), then 5 (count 2), then 2 (count 3), then 1 (count 4). Now x > 1 is false, so the loop stops and the output is 4. Two habits protect these marks: test the condition before each pass rather than after, and write a new row for every pass - trying to hold the values in your head is what makes traces go wrong.

Test data is data you use to test a program. There are four types you must know.

You must know these common algorithms.

Linear search

A linear search 线性查找 checks each item in a list, one by one, until it finds the value it wants or reaches the end.

found ← FALSE
FOR i ← 0 TO 9
    IF list[i] = searchValue THEN
        found ← TRUE
    ENDIF
NEXT i
OUTPUT found

Linear search checks each item in turn from the start until it finds the value

Bubble sort

A bubble sort 冒泡排序 puts a list in order. It compares each pair of side-by-side items and swaps them if they are in the wrong order. It repeats this until no more swaps are needed.

FOR i ← 0 TO 8
    IF list[i] > list[i + 1] THEN
        temp ← list[i]
        list[i] ← list[i + 1]
        list[i + 1] ← temp
    ENDIF
NEXT i

Bubble sort compares each side-by-side pair and swaps them if they are out of order, repeating until sorted

Totalling and counting

• totalling 求和 — keep adding values to a running total (total ← total + value).
• counting 计数 — add 1 to a counter each time something happens (count ← count + 1).

Maximum, minimum and average

• to find the maximum 最大值: keep the largest value seen so far.
• to find the minimum 最小值: keep the smallest value seen so far.
• to find the average 平均值: divide the total by how many values there are.

total ← 0
FOR i ← 0 TO 9
    total ← total + list[i]
NEXT i
average ← total / 10
OUTPUT average

• Learn the four life-cycle stages: analysis → design → coding → testing. Abstraction keeps only the important details; decomposition breaks a problem into smaller parts.
• Validation checks data is sensible (range, length, type, presence, format checks); verification checks it was copied correctly (a visual check or double entry).
• Learn the four test-data types: normal (accepted), abnormal (rejected), extreme (the largest/smallest still allowed), boundary (the values either side of a limit).
• To work out what an algorithm does, fill in a trace table — write down every variable's value at each step.
• Know the standard algorithms: linear search (check each item in turn) and bubble sort (swap side-by-side pairs until no swaps are needed).