今天这篇编程五级总复习宝典，会用最通俗的比喻、最清晰的代码，把所有重点难点拆解透彻。看完这篇，你不仅能轻松应对考试，还能写出比以前快几十上百倍的高效代码！
第一关：初等数论基础——算法的数学密码
所有高级算法都离不开数学，而初等数论就是算法中最常用的数学工具。
1.1 整除、因数与倍数
- 整除如果整数
b除以整数a（a≠0），商是整数且没有余数，我们就说b能整除a，记作b | a - 因数
- 倍数
示例：12的因数有1、2、3、4、6、12；12是1、2、3、4、6、12的倍数
1.2 辗转相除法（欧几里得算法）⭐⭐⭐⭐⭐
核心思想：两个数的最大公约数（GCD），等于其中较小的数和两数相除余数的最大公约数。 公式：gcd(a, b) = gcd(b, a % b)，直到余数为0，此时的除数就是最大公约数。
代码实现（递归版，考试推荐）：
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
# 测试
print(gcd(12, 18)) # 输出：6
print(gcd(100, 25)) # 输出：25
拓展：最小公倍数（LCM） 两个数的最小公倍数 = 两数乘积 ÷ 最大公约数
def lcm(a, b):
return a * b // gcd(a, b)
print(lcm(12, 18)) # 输出：36
易错点提醒：
- 辗转相除法不要求
a > b，如果a < b，第一次递归会自动交换顺序
第二关：素数筛选——快速找出所有素数
素数（质数）是指大于1的自然数中，除了1和它本身以外不再有其他因数的数。
2.1 朴素素数判断
def is_prime(n):
if n < 2:
return False
# 只需检查到√n即可，因为如果n有大于√n的因数，必然有一个对应的小于√n的因数
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
2.2 埃氏筛法（埃拉托斯特尼筛法）⭐⭐⭐⭐
核心思想：先假设所有数都是素数，然后从2开始，把每个素数的所有倍数都标记为合数。
代码实现：
def sieve_of_eratosthenes(n):
# 初始化一个布尔数组，prime[i]表示i是否是素数
prime = [True] * (n + 1)
prime[0] = prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if prime[i]:
# 把i的所有倍数标记为合数，从i²开始可以优化
for j in range(i * i, n + 1, i):
prime[j] = False
# 返回所有素数
return [i for i in range(n + 1) if prime[i]]
# 找出100以内的所有素数
primes = sieve_of_eratosthenes(100)
print(primes)
2.3 线性筛法（欧拉筛法）⭐⭐⭐⭐⭐
核心思想：埃氏筛法会重复标记一些合数（比如12会被2和3都标记），线性筛法保证每个合数只会被它的最小质因数标记一次，时间复杂度达到O(n)。
代码实现：
def sieve_of_euler(n):
prime = []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
prime.append(i)
# 遍历当前已找到的所有素数
for p in prime:
if i * p > n:
break
is_prime[i * p] = False
# 关键：如果i是p的倍数，说明p是i的最小质因数，此时停止
if i % p == 0:
break
return prime
# 找出1000以内的所有素数
primes = sieve_of_euler(1000)
print(len(primes)) # 输出：168
第三关：二分查找——最快的搜索算法⭐⭐⭐⭐⭐
如果说有一个算法能让你的程序速度提升1000倍，那一定是二分查找！
3.1 二分查找的核心思想
在有序数组中查找一个元素时，每次取中间元素和目标值比较：
每次查找都能排除一半的元素，时间复杂度是O(log n)（比如在100万个数中查找，最多只需要20次！）
3.2 标准二分查找代码
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
# 等价于 (left + right) // 2，但避免了整数溢出
mid = left + (right - left) // 2
if arr[mid] == target:
return mid # 找到目标，返回索引
elif arr[mid] > target:
right = mid - 1 # 目标在左半部分
else:
left = mid + 1 # 目标在右半部分
return -1 # 没有找到
# 测试
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7)) # 输出：3
print(binary_search(arr, 4)) # 输出：-1
3.3 二分答案——二分查找的进阶应用
适用场景：求"最大值的最小值"或"最小值的最大值"这类问题。 核心思想：在可能的答案范围内进行二分查找，每次判断中间值是否满足条件，然后缩小范围。
示例：分巧克力问题
有n块巧克力，每块的长度是a[i]。要把它们分给k个小朋友，每个小朋友只能得到一块完整的巧克力，或者把一块巧克力切成几块，但不能把多块巧克力拼在一起。问每个小朋友最多能得到多长的巧克力？
def max_chocolate_length(a, k):
left = 1
right = max(a)
ans = 0
while left <= right:
mid = left + (right - left) // 2
# 计算按mid长度分，能分给多少个小朋友
count = sum(x // mid for x in a)
if count >= k:
# 能分给k个小朋友，尝试更大的长度
ans = mid
left = mid + 1
else:
# 不能分给k个小朋友，尝试更小的长度
right = mid - 1
return ans
# 测试
a = [5, 6, 7, 8]
k = 5
print(max_chocolate_length(a, k)) # 输出：4
易错点提醒：
- 循环条件是
left <= right，不是left < right - 计算mid时用
left + (right - left) // 2，避免溢出
第四关：递归函数——自己调用自己的魔法⭐⭐⭐⭐⭐
递归是算法中最强大也最容易出错的工具，很多高级算法（分治、回溯、动态规划）都建立在递归的基础上。
4.1 递归的两个必要条件
- 终止条件：递归必须有一个明确的结束条件，否则会无限递归导致栈溢出
- 递归公式
4.2 经典递归示例
示例1：计算阶乘
def factorial(n):
# 终止条件：0! = 1，1! = 1
if n == 0 or n == 1:
return 1
# 递归公式：n! = n × (n-1)!
return n * factorial(n - 1)
print(factorial(5)) # 输出：120
示例2：斐波那契数列
def fibonacci(n):
# 终止条件：F(0)=0，F(1)=1
if n == 0:
return 0
elif n == 1:
return 1
# 递归公式：F(n) = F(n-1) + F(n-2)
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(10)) # 输出：55
易错点提醒：
- 递归深度不要太大（Python默认递归深度限制是1000）
第五关：分治算法——分而治之的智慧⭐⭐⭐⭐⭐
分治算法的核心思想是：把一个复杂的大问题，拆分成若干个规模较小的相同问题，递归解决这些小问题，然后把结果合并起来得到原问题的解。
5.1 归并排序
步骤：
代码实现：
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 拆分
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 合并
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 把剩下的元素加进去
result.extend(left[i:])
result.extend(right[j:])
return result
# 测试
arr = [5, 2, 9, 1, 5, 6, 3]
print(merge_sort(arr)) # 输出：[1, 2, 3, 5, 5, 6, 9]
5.2 快速排序
步骤：
- 分区：把数组分成两部分，左边的元素都小于等于基准，右边的元素都大于等于基准
代码实现：
def quick_sort(arr):
if len(arr) <= 1:
return arr
# 选第一个元素作为基准
pivot = arr[0]
# 分区
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
# 递归排序并合并
return quick_sort(left) + [pivot] + quick_sort(right)
# 测试
arr = [5, 2, 9, 1, 5, 6, 3]
print(quick_sort(arr)) # 输出：[1, 2, 3, 5, 5, 6, 9]
两种排序算法对比：
第六关：贪心算法——每一步都选最好的
贪心算法的核心思想是：在每一步都做出当前看起来最好的选择，希望通过局部最优解得到全局最优解。
6.1 贪心算法的适用条件
不是所有问题都能用贪心算法解决，必须满足两个条件：
- 贪心选择性质
- 最优子结构
6.2 经典示例：活动选择问题
有n个活动，每个活动有开始时间s[i]和结束时间e[i]。你最多能参加多少个不重叠的活动？
贪心策略：每次选择结束时间最早的活动，这样能留出最多的时间参加后面的活动。
代码实现：
def activity_selection(activities):
# 按结束时间排序
activities.sort(key=lambda x: x[1])
count = 1
last_end = activities[0][1]
for i in range(1, len(activities)):
start, end = activities[i]
if start >= last_end:
count += 1
last_end = end
return count
# 测试：每个活动是(开始时间, 结束时间)
activities = [(1, 3), (2, 4), (3, 5), (4, 6), (5, 7)]
print(activity_selection(activities)) # 输出：3
易错点提醒：
- 贪心算法不是万能的！比如硬币找零问题，如果硬币系统是[1, 3, 4]，要找6元，贪心会选4+1+1=3枚，但最优解是3+3=2枚
第七关：算法复杂度进阶——对数级别的威力
五级我们重点掌握对数级复杂度O(log n)，这是效率非常高的复杂度。
常见的O(log n)算法：
复杂度对比：
可以看到，当n很大时，O(log n)和O(n)、O(n²)的差距是天壤之别！这就是为什么我们要学习高效算法的原因。
🎯 考前必做综合练习
现在来检验一下你的学习成果吧！这些题目覆盖了五级所有核心考点，一定要亲手敲一遍代码！
练习1：最大公约数与最小公倍数
编写一个程序，输入两个正整数，输出它们的最大公约数和最小公倍数。
练习2：素数筛选
用线性筛法找出10000以内的所有素数，并统计个数。
练习3：二分查找
给定一个有序数组和一个目标值，用二分查找找出目标值在数组中的第一个出现位置和最后一个出现位置。
练习4：递归求幂
用递归实现快速幂算法，计算a^b mod m（a的b次方除以m的余数）。
练习5：归并排序
用归并排序对一个包含1000个随机数的数组进行排序。
练习6：贪心算法
有n个物品，每个物品有重量w[i]和价值v[i]。你有一个能装重量为W的背包，每个物品只能拿一次，问最多能拿多少价值的物品？（注意：这是01背包问题，不能用贪心！请思考为什么？）
📝 参考答案
练习1：最大公约数与最小公倍数
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def lcm(a, b):
return a * b // gcd(a, b)
a = int(input("请输入第一个数："))
b = int(input("请输入第二个数："))
print(f"最大公约数：{gcd(a, b)}")
print(f"最小公倍数：{lcm(a, b)}")
练习2：素数筛选
def sieve_of_euler(n):
prime = []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
prime.append(i)
for p in prime:
if i * p > n:
break
is_prime[i * p] = False
if i % p == 0:
break
return prime
primes = sieve_of_euler(10000)
print(f"10000以内的素数个数：{len(primes)}")
练习3：二分查找找左右边界
def find_first(arr, target):
left = 0
right = len(arr) - 1
res = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
res = mid
right = mid - 1 # 继续向左找
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return res
def find_last(arr, target):
left = 0
right = len(arr) - 1
res = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
res = mid
left = mid + 1 # 继续向右找
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return res
arr = [1, 2, 2, 2, 3, 4, 4, 5]
target = 2
print(f"第一个出现位置：{find_first(arr, target)}")
print(f"最后一个出现位置：{find_last(arr, target)}")
练习4：快速幂
def fast_pow(a, b, m):
if b == 0:
return 1 % m
res = fast_pow(a, b // 2, m)
res = res * res % m
if b % 2 == 1:
res = res * a % m
return res
print(fast_pow(2, 10, 1000)) # 输出：24
练习5：归并排序
import random
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 生成1000个随机数
arr = [random.randint(1, 10000) for _ in range(1000)]
sorted_arr = merge_sort(arr)
print(sorted_arr[:10]) # 输出前10个元素
练习6：思考
01背包问题不能用贪心算法，因为贪心选择单位重量价值最高的物品，不一定能得到全局最优解。比如：
贪心会选物品1，总价值6；但最优解是选物品2和物品3，总价值6？不对，换个例子：
贪心选物品1，总价值5；最优解是选物品2和物品3，总价值6。这就说明贪心不能得到最优解。
🎉 写在最后
太棒了！你已经看完了这篇编程五级总复习文章。现在的你，已经正式踏入了算法的大门，掌握了所有高级算法的基础。
五级的知识点确实有难度，特别是递归和分治，刚开始可能会觉得很抽象。但请记住：算法是练出来的，不是看出来的。把上面的每个示例都亲手敲一遍，把练习题都做会，你会发现自己的逻辑思维能力有了质的飞跃。
通过五级只是你算法之路的开始。接下来还有更精彩的知识等着你——动态规划、图论、搜索算法……这些都是算法竞赛和未来人工智能的核心。
加油，未来的算法大师们！你们已经站在了一个新的起点，继续在代码的世界里探索吧！🚀
10个月宝宝每天需要喝多少奶粉？
