Algorithm Essentials for IB & CCEA Mathematics | IB CCEA 数学：算法 考点精讲

📚 Algorithm Essentials for IB & CCEA Mathematics | IB CCEA 数学：算法 考点精讲

Algorithms lie at the heart of modern mathematics and computer science. In the IB and CCEA mathematics syllabi, understanding algorithmic thinking is not only about coding; it is about logical, step‑by‑step procedures to solve problems – from finding greatest common divisors to ordering lists and approximating roots. This revision guide unpacks the key algorithms you are expected to master, details their inner workings, traces them through tables, and highlights common pitfalls. By the end, you will be equipped to apply, trace, and compare algorithms with confidence.

算法是现代数学和计算机科学的核心。在 IB 和 CCEA 数学课程体系中，理解算法思维并非仅仅关于编程，而是用逻辑、逐步执行的流程解决问题——从求最大公约数到给列表排序、再到逼近方程的根。这份考点精讲将逐一拆解你需掌握的关键算法，详解其内在机制，通过表格追溯执行过程，并点出常见易错点。学完本文，你将能够自信地应用、追踪和比较各种算法。

1. What is an Algorithm? | 什么是算法？

An algorithm is a finite sequence of well‑defined, unambiguous instructions designed to solve a specific problem or perform a computation. It must terminate after a finite number of steps, produce a correct output for every valid input, and each step must be feasible – something a human or machine can carry out.

算法是一个由明确定义且无歧义的指令构成的有穷序列，旨在解决特定问题或执行某种计算。它必须在有限步后终止，对于每个有效输入都要产生正确的输出，且每一步都必须是可执行的——人或机器都能完成。

In mathematics, we encounter algorithms in many guises: the Euclidean algorithm, bubble sort, binary search, Newton–Raphson iteration, and more. The IB and CCEA exams expect you to trace an algorithm on a given set of data, modify an existing algorithm, and evaluate its efficiency.

在数学中，算法以多种面貌出现：欧几里得算法、冒泡排序、二分查找、牛顿‑拉弗森迭代等等。IB 和 CCEA 考试要求考生能在给定数据集上追踪算法、修改已有算法并评估其效率。

---

2. Representing Algorithms: Flowcharts and Pseudocode | 算法的表示：流程图与伪代码

Algorithms are usually expressed in pseudocode or as flowcharts. Pseudocode uses structured English that resembles programming code but omits language‑specific syntax. Flowcharts use standard symbols: ovals for start/end, rectangles for processes, diamonds for decisions, and arrows for flow of control.

算法通常用伪代码或流程图表示。伪代码使用结构化的英语，类似编程代码但省去了特定语言语法。流程图使用标准符号：椭圆形表示开始/结束，矩形表示处理，菱形表示判断，箭头表示控制流。

A classic example is finding the maximum of three numbers. In pseudocode:


INPUT a, b, c
max ← a
IF b > max THEN max ← b
IF c > max THEN max ← c
OUTPUT max

一个经典例子是求三个数的最大值。伪代码如下：


输入 a, b, c
max ← a
如果 b > max 则 max ← b
如果 c > max 则 max ← c
输出 max

Tracing tools, such as trace tables, record variable values step‑by‑step. They are essential for scoring full marks on written algorithm questions.

追踪工具（如追踪表）会逐步记录变量值。它们在算法笔试中对于拿到满分至关重要。

---

3. The Euclidean Algorithm for GCD | 求最大公约数的欧几里得算法

The Euclidean algorithm is one of the oldest and most efficient methods for finding the greatest common divisor (gcd) of two positive integers. It is based on the property: gcd(a, b) = gcd(b, a mod b), repeating until the remainder becomes zero; the last non‑zero remainder is the gcd.

欧几里得算法是求两个正整数最大公约数（gcd）最古老且最高效的方法之一。它基于性质：gcd(a, b) = gcd(b, a mod b)，不断重复直至余数为零；最后一个非零余数即为 gcd。

Pseudocode:

INPUT m, n
WHILE n ≠ 0
r ← m mod n
m ← n
n ← r
END WHILE
OUTPUT m

伪代码：

输入 m, n
当 n ≠ 0
r ← m mod n
m ← n
n ← r
结束循环
输出 m

Trace example: find gcd(48, 18)

追踪示例：求 gcd(48, 18)

Step	m	n	r = m mod n
1	48	18	12
2	18	12	6
3	12	6	0

After step 3, n=0, loop ends. Output m=6, so gcd(48,18)=6.

步骤3后 n=0，循环结束。输出 m=6，所以 gcd(48,18)=6。

The extended Euclidean algorithm also finds integers x, y such that ax + by = gcd(a,b), which is vital for solving linear Diophantine equations and modular inverses.

扩展欧几里得算法还能求出整数 x, y 使 ax + by = gcd(a,b)，这对解线性丢番图方程和求模逆至关重要。

---

4. Bubble Sort Algorithm | 冒泡排序算法

Bubble sort repeatedly steps through a list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating the list is sorted.

冒泡排序反复遍历列表，比较相邻元素，若顺序错误则交换。这一遍历过程不断重复，直至无需交换，表明列表已排好序。

Pseudocode for an array A[1…n]:

FOR i ← 1 TO n‑1
FOR j ← 1 TO n‑i
IF A[j] > A[j+1] THEN
SWAP A[j] and A[j+1]
END IF
END FOR
END FOR

数组 A[1…n] 的伪代码：

FOR i ← 1 TO n‑1
FOR j ← 1 TO n‑i
若 A[j] > A[j+1] 则
交换 A[j] 和 A[j+1]
结束条件
结束内循环
结束外循环

Trace table for sorting [5, 3, 8, 1] with bubble sort:

冒泡排序追踪表：对 [5, 3, 8, 1] 排序

Pass i	j	Comparison	Array after step
1	1	5>3? yes, swap	[3,5,8,1]
	2	5>8? no	[3,5,8,1]
	3	8>1? yes, swap	[3,5,1,8]
2	1	3>5? no	[3,5,1,8]
	2	5>1? yes, swap	[3,1,5,8]
3	1	3>1? yes, swap	[1,3,5,8]

After pass 3, array is sorted. Bubble sort has worst‑case time complexity O(n²).

第3遍后数组有序。冒泡排序最坏情况下时间复杂度为 O(n²)。

---

5. Binary Search Algorithm | 二分查找算法

Binary search locates a target value within a sorted array by repeatedly dividing the search interval in half. It begins with the whole array; if the target is less than the middle element, search left half; otherwise right half. This reduces time complexity to O(log n).

二分查找通过不断将搜索区间对半分，在有序数组中定位目标值。从整个数组开始；若目标小于中间元素，则搜左半部；否则搜右半部。这使时间复杂度降至 O(log n)。

Pseudocode:

INPUT sorted array A[1…n], target T
low ← 1, high ← n
WHILE low ≤ high
mid ← floor((low+high)/2)
IF A[mid] = T THEN
OUTPUT mid
STOP
ELSE IF A[mid] < T THEN
low ← mid+1
ELSE
high ← mid‑1
END IF
END WHILE
OUTPUT “Not found”

伪代码：

输入 有序数组 A[1…n], 目标 T
low ← 1, high ← n
当 low ≤ high
mid ← floor((low+high)/2)
若 A[mid] = T 则
输出 mid
停止
否则 若 A[mid] < T 则
low ← mid+1
否则
high ← mid‑1
结束条件
结束循环
输出 “未找到”

Trace searching for 10 in [2, 5, 8, 10, 13, 17]:

追踪在 [2, 5, 8, 10, 13, 17] 中查找 10：

Iteration	low	high	mid	A[mid]	Decision
1	1	6	3	8	8<10, so low=4
2	4	6	5	13	13>10, so high=4
3	4	4	4	10	Found at position 4

Binary search requires a pre‑sorted list, a condition often assessed in exam questions.

二分查找要求列表已预先排序，这一条件是考试题中常考的点。

---

6. Newton–Raphson Method for Root Finding | 牛顿‑拉弗森求根法

The Newton–Raphson method iteratively approximates a root of the equation f(x)=0 using the formula:

xₙ₊₁ = xₙ − f(xₙ) / f ‘(xₙ)

牛顿‑拉弗森法使用迭代公式逐步逼近方程 f(x)=0 的根：

xₙ₊₁ = xₙ − f(xₙ) / f ‘(xₙ)

Algorithm:

INPUT initial guess x₀, tolerance ε, max iterations N
FOR i ← 1 TO N
x₁ ← x₀ − f(x₀)/f ‘(x₀)
IF |x₁ − x₀| < ε THEN
OUTPUT x₁
STOP
END IF
x₀ ← x₁
END FOR
OUTPUT “Did not converge”

算法：

输入 初始猜测值 x₀, 容差 ε, 最大迭代次数 N
FOR i ← 1 TO N
x₁ ← x₀ − f(x₀)/f ‘(x₀)
若 |x₁ − x₀| < ε 则
输出 x₁
停止
结束条件
x₀ ← x₁
结束循环
输出 “未收敛”

Example: find √2 by solving f(x)=x²−2=0, f ‘(x)=2x, starting with x₀=1.5.

示例：求 √2，解 f(x)=x²−2=0，f ‘(x)=2x，从 x₀=1.5 开始。

i	x₀	f(x₀)	f ‘(x₀)	x₁
1	1.5	0.25	3	1.41667
2	1.41667	0.00695	2.83333	1.41422
3	1.41422	0.00004	2.82843	1.41421

After 3 iterations, x₁ ≈ 1.41421, converging rapidly. The method requires a differentiable function and a sensible initial guess; otherwise it may diverge.

3次迭代后 x₁ ≈ 1.41421，快速收敛。该方法要求函数可导且初始猜测值合理；否则可能发散。

---

7. Trapezium Rule for Numerical Integration | 梯形法则与数值积分

The trapezium rule approximates ∫ₐᵇ f(x)dx by dividing the interval into n equal strips of width h = (b−a)/n and summing the areas of trapezia. The formula:

∫ₐᵇ f(x)dx ≈ h/2 [y₀ + 2(y₁ + y₂ + … + yₙ₋₁) + yₙ]

梯形法则将区间 [a,b] 等分成 n 份，宽 h = (b−a)/n，求梯形面积之和来近似 ∫ₐᵇ f(x)dx。公式：

∫ₐᵇ f(x)dx ≈ h/2 [y₀ + 2(y₁ + y₂ + … + yₙ₋₁) + yₙ]

Algorithm:

INPUT a, b, n (n must be positive integer)
h ← (b−a)/n
sum ← f(a) + f(b)
FOR i ← 1 TO n−1
sum ← sum + 2×f(a + i×h)
END FOR
Area ← (h/2) × sum
OUTPUT Area

算法：

输入 a, b, n (n 为正整数)
h ← (b−a)/n
sum ← f(a) + f(b)
FOR i ← 1 TO n−1
sum ← sum + 2×f(a + i×h)
结束循环
面积 ← (h/2) × sum
输出 面积

Trace for ∫₁² (1/x) dx with n=4, h=0.25:
x₀=1 y₀=1; x₁=1.25 y₁=0.8; x₂=1.5 y₂≈0.6667; x₃=1.75 y₃≈0.5714; x₄=2 y₄=0.5.
Approximation = 0.25/2 × [1 + 2(0.8+0.6667+0.5714) + 0.5] = 0.125 × (1+4.0762+0.5) = 0.125×5.5762 ≈ 0.6970. The exact value is ln2 ≈ 0.6931.

追踪 ∫₁² (1/x) dx，n=4, h=0.25：x₀=1 y₀=1; x₁=1.25 y₁=0.8; x₂=1.5 y₂≈0.6667; x₃=1.75 y₃≈0.5714; x₄=2 y₄=0.5。近似值 = 0.25/2 × [1 + 2(0.8+0.6667+0.5714) + 0.5] = 0.6970。精确值为 ln2 ≈ 0.6931。

Increasing n improves accuracy, a typical exam discussion point.

增加 n 可提高精度，这是典型的考试讨论点。

---

8. Standard Algorithm Complexity and Big‑O Notation | 标准算法复杂度与大O记号

The efficiency of an algorithm is measured by its time complexity – how the runtime grows with input size n. Big‑O notation expresses the upper bound. Key families:

Complexity	Notation	Example algorithms
Constant	O(1)	Accessing array element
Logarithmic	O(log n)	Binary search
Linear	O(n)	Linear search, traverse list
Linearithmic	O(n log n)	Merge sort, quicksort (average)
Quadratic	O(n²)	Bubble sort, insertion sort
Exponential	O(2ⁿ)	Brute‑force combinatorial problems

算法的效率由其时间复杂度衡量——程序运行时间如何随输入规模 n 增长。大O记号表示上界。主要类别：

复杂度	记号	示例算法
常数	O(1)	访问数组元素
对数	O(log n)	二分查找
线性	O(n)	线性查找、遍历列表
线性对数	O(n log n)	归并排序、快速排序（平均）
平方	O(n²)	冒泡排序、插入排序
指数	O(2ⁿ)	暴力组合问题

Understanding complexity helps you choose the right algorithm for large inputs. For IB and CCEA, you should be able to estimate the number of steps for a given n, for instance, a bubble sort on n=1000 requires roughly 1,000,000 comparisons in the worst case.

理解复杂度能帮助你在面对大规模输入时选择合适的算法。对于 IB 和 CCEA，你应能估算给定 n 时的步数，例如当 n=1000 时，冒泡排序最坏需要约 1,000,000 次比较。

---

9. Algorithmic Thinking: Decomposition and Pattern Recognition | 算法思维：分解与模式识别

Algorithmic thinking involves breaking down a problem into smaller, manageable parts (decomposition) and identifying recurring patterns to design efficient solutions. In exam scenarios, you might be given a novel problem and asked to draft an algorithm using familiar building blocks – loops, conditionals, variables.

算法思维包括将问题分解为更小、更易管理的部分（分解），并识别重复出现的模式以设计高效解决方案。在考试情境下，你可能会遇到一个新问题，要求使用熟悉的积木——循环、条件、变量——草拟一个算法。

For example, designing an algorithm to check if a number is prime: use a FOR loop from 2 to √n, testing divisibility. This combines decomposition (separating the primality test from main program) and pattern recognition (all even numbers except 2 are not prime).

例如，设计一个检查某数是否为质数的算法：用 FOR 循环从 2 到 √n 测试整除性。这结合了分解（将质数测试与主程序分离）和模式识别（除 2 外所有偶数均非质数）。

Pseudocode prime test:

INPUT n
IF n < 2 THEN OUTPUT "Not prime"
ELSE IF n = 2 THEN OUTPUT “Prime”
ELSE IF n mod 2 = 0 THEN OUTPUT “Not prime”
ELSE
FOR i ← 3 TO floor(√n) STEP 2
IF n mod i = 0 THEN
OUTPUT “Not prime”
STOP
END IF
END FOR
OUTPUT “Prime”
END IF

伪代码质数测试：

输入 n
若 n < 2 输出 "不是质数"
否则 若 n = 2 输出 “质数”
否则 若 n mod 2 = 0 输出 “不是质数”
否则
FOR i ← 3 TO floor(√n) 步长 2
若 n mod i = 0 则
输出 “不是质数”
停止
结束条件
结束循环
输出 “质数”
结束条件

---

10. Tracing and Debugging Algorithms | 追踪与排错

A significant number of marks hinge on tracing given algorithms. Create a trace table with columns for each variable; update row by row as the algorithm runs. Watch for common bugs: off‑by‑one errors in loops, incorrect initialisation, infinite loops due to missing updates, and wrong termination conditions.

很大一部分分数取决于对既定算法的追踪。创建一个追踪表，为每个变量设列；随着算法运行逐行更新。注意常见错误：循环中的差一错误、初始化不正确、因缺少更新导致的无限循环以及错误的终止条件。

Exam tip: when asked to complete a trace table, only fill the cells that are explicitly required – some algorithms demand tracing only specific variables or values that change. Always double‑check that the final output makes sense with the given data.

考试技巧：当被要求完成追踪表时，只填写明确要求的单元格——有些算法只要求追踪特定变量或发生变化的值。始终再次检查最终输出是否与给定数据相符。

For example, tracing a bad algorithm for summing from 1 to n:

INPUT n
sum ← 0
WHILE n > 0
sum ← sum + n
END WHILE

Without decreasing n, the loop runs forever. A correct version requires n ← n‑1 inside the loop.

例如，追踪一个求 1 到 n 之和的错误算法：

输入 n
sum ← 0
当 n > 0 时
sum ← sum + n
结束循环

若不减少 n，循环会永远运行。正确版本需在循环内加入 n ← n‑1。

---

11. Comparing Algorithms: When to Use Which? | 算法比较：何时用哪个？

Different sorting and searching algorithms suit different situations. Bubble sort is simple but slow; it is educational, not used for large datasets. Merge sort guarantees O(n log n) but uses extra memory. Binary search is unbeatable on sorted arrays, but if your list is unordered, linear search is the only option without pre‑sorting. For root‑finding, Newton–Raphson is fast but needs a derivative; the bisection method is slower but always converges if the interval brackets a root.

不同的排序和搜索算法适合不同情况。冒泡排序简单但速度慢；它只用于教学，不用于大数据集。归并排序稳定 O(n log n) 但需要额外内存。二分查找在有序数组上无敌，但如果列表无序，不预先排序就只能线性查找。在求根中，牛顿‑拉弗森收敛快但需要导数；二分法较慢，但若区间包含根则总能收敛。

Exam questions often ask you to recommend an algorithm, justifying your choice

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）