算法导论-2021fa-回忆版

算法导论 2021年秋季学期的回忆版真题，来源于计算机速通之家 | QQ 群号：468081841。

本文连载于算法导论-2021fa-回忆版| HeZzz.

🙇‍♂️🙇‍♂️🙇‍♂️时间仓促，有不足之处烦请及时告知。邮箱hez2z@foxmail.com 或者在速通之家群里 @9¾。

第一题(10分)

题目描述

给出了一个大整数乘法算法的描述，对于 $n$ 位乘法，仅作 $3$ 次 $n/2$ 位的乘法和 $1$ 次 $n$ 位的加法即可。

根据题意写出递归公式(5分)
求算法复杂度(5分)

解答

分治法 - 大整数乘法（Karatsuba算法）:

设两个 $n$ 位数为 $X$ 和 $Y$ ，将它们分成两半：

X = A \times 10^{n/2} + B

Y = C \times 10^{n/2} + D

传统方法需要 4 次乘法： $AC$ , $AD$ , $BC$ , $BD$

Karatsuba算法只需 3 次乘法：

$P_1 = A \times C$
$P_2 = B \times D$
$P_3 = (A + B) \times (C + D)$

则：

X \times Y = P_1 \times 10^n + (P_3 - P_1 - P_2) \times 10^{n/2} + P_2

1. 递归公式：

T(n) = 3T(n/2) + O(n)

其中 $3T(n/2)$ 表示 3 次 $n/2$ 位的乘法， $O(n)$ 表示加法和移位操作。

2. 算法复杂度：

根据主定理（Master Theorem）： $T(n) = aT(n/b) + f(n)$

这里 $a = 3$ , $b = 2$ , $f(n) = O(n)$

比较 $n^{\log_b a} = n^{\log_2 3} \approx n^{1.585}$ 与 $f(n) = O(n)$

因为 $n^{\log_2 3} > n$ ，满足主定理第一种情况，所以：

T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})

第二题(10分)

题目描述

现有程序设计比赛公示名单，已经按照学号非降序排列好了，现在插入学号为 $x$ 的学生。

写出算法描述，如何找到 $x$ 之前的学生的最大序号 $i$ 和 $x$ 之后的学生的最小序号 $j$ （5分）
最坏情况下的算法复杂度（5分）

解答

分治法 - 二分搜索:

1. 算法描述：

使用二分搜索在有序数组中找到插入位置：

算法：BinarySearchInsertPosition(A, n, x)
输入：有序数组A[1..n]，待插入值x
输出：x之前的最大序号i和之后的最小序号j

begin
    left = 1, right = n
    
    while left <= right do
        mid = (left + right) / 2
        
        if A[mid] < x then
            left = mid + 1
        else if A[mid] > x then
            right = mid - 1
        else  // A[mid] == x，找到相等元素
            i = mid - 1
            j = mid + 1
            return (i, j)
        end if
    end while
    
    // 未找到相等元素，left是插入位置
    i = left - 1
    j = left
    return (i, j)
end

说明：

当 $A[mid] < x$ 时，在右半部分搜索
当 $A[mid] > x$ 时，在左半部分搜索
当 $A[mid] = x$ 时（非降序可能有重复）， $i = mid-1$ ， $j = mid+1$
最终 $i$ 是 $x$ 之前的最大序号， $j$ 是 $x$ 之后的最小序号

2. 时间复杂度：

二分搜索每次将搜索范围减半，递归公式为：

T(n) = T(n/2) + O(1)

根据主定理，时间复杂度为：

T(n) = O(\log n)

第三题(10分)

题目描述

开了个小卖部，给出 1-12 月各月的盈利，含负数（负数表示亏损），求连续月份的最大盈利和。

写出算法描述（5分）
最坏时间复杂度分析（5分）

解答

动态规划 - 最大子段和（Maximum Subarray）:

1. 算法描述：

算法：MaxSubarraySum(profit, n)
输入：盈利数组profit[1..n]，n=12（月份数）
输出：连续月份的最大盈利和

begin
    maxSum = profit[1]     // 全局最大值
    currentSum = profit[1] // 当前子段和
    
    for i = 2 to n do
        // 状态转移：要么加入当前元素，要么从当前元素重新开始
        currentSum = max(profit[i], currentSum + profit[i])
        // 更新全局最大值
        maxSum = max(maxSum, currentSum)
    end for
    
    return maxSum
end

动态规划思路：

定义 $dp[i]$ 为以第 $i$ 个月结尾的最大连续盈利和，则状态转移方程为：

dp[i] = \max(profit[i], dp[i-1] + profit[i])

最终答案为：

\max_{1 \leq i \leq n} dp[i]

2. 时间复杂度：

算法只需遍历一次数组，每次进行常数时间的比较和更新操作，因此时间复杂度为：

T(n) = O(n)

空间复杂度可优化到 $O(1)$ （使用两个变量代替数组）。

代码实现：

{% tabs algo-21fa-1 %}

def max_profit(profits):
    n = len(profits)
    if n == 0:
        return 0
    
    max_sum = current_sum = profits[0]
    
    for i in range(1, n):
        current_sum = max(profits[i], current_sum + profits[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

# 示例
profits = [5, -3, 4, -2, 6, -1, 2, -8, 3, 7, -4, 2]
print(max_profit(profits))  # 输出最大连续盈利和

{% endtabs %}

第四题(20分)

题目描述

体育馆预约，给出十个人预约的开始时间与结束时间，现在进行安排。

写出算法描述（10分）
能安排多少人（5分）
能安排哪些人（5分）

解答

贪心算法 - 活动安排问题（Activity Selection Problem）:

1. 算法描述：

算法：ActivitySelection(activities, n)
输入：n个活动，每个活动有开始时间start[i]和结束时间end[i]
输出：最多可安排的活动数量及活动列表

begin
    // 步骤1：按结束时间升序排序
    Sort activities by end time in ascending order
    
    // 步骤2：贪心选择
    selected = [1]  // 选择第一个活动
    lastEnd = end[1]  // 记录最后选择的活动的结束时间
    
    for i = 2 to n do
        // 如果当前活动的开始时间 >= 上一个活动的结束时间
        if start[i] >= lastEnd then
            selected.append(i)  // 选择该活动
            lastEnd = end[i]    // 更新结束时间
        end if
    end for
    
    return (selected.length, selected)
end

贪心策略： 总是选择结束时间最早的活动，这样能为后续活动留出更多时间。

正确性证明： 通过数学归纳法可证明，选择结束时间最早的活动不会影响最优解。

2 & 3. 具体计算示例：

假设十个人的预约时间如下（编号，开始时间，结束时间）：

编号	开始时间	结束时间
1	1	4
2	3	5
3	0	6
4	5	7
5	3	9
6	5	9
7	6	10
8	8	11
9	8	12
10	2	14

排序后（按结束时间）： 1(1,4), 2(3,5), 3(0,6), 4(5,7), 5(3,9), 6(5,9), 7(6,10), 8(8,11), 9(8,12), 10(2,14)

贪心选择过程：

选择活动1：结束时间4
检查活动2：开始时间3 < 4，跳过
检查活动3：开始时间0 < 4，跳过
检查活动4：开始时间5 >= 4，选择，结束时间7
检查活动5-7：开始时间均 < 7，跳过
检查活动8：开始时间8 >= 7，选择，结束时间11
检查活动9：开始时间8 < 11，跳过
检查活动10：开始时间2 < 11，跳过

答案：

最多安排 4 人（或其他数量，根据实际数据）
安排的人：活动1, 4, 8（或其他组合，根据实际数据）

代码实现：

def activity_selection(activities):
    # activities: [(id, start, end), ...]
    # 按结束时间排序
    activities.sort(key=lambda x: x[2])
    
    selected = [activities[0][0]]  # 选择第一个活动的ID
    last_end = activities[0][2]
    
    for i in range(1, len(activities)):
        activity_id, start, end = activities[i]
        if start >= last_end:
            selected.append(activity_id)
            last_end = end
    
    return len(selected), selected

# 示例
activities = [
    (1, 1, 4), (2, 3, 5), (3, 0, 6), (4, 5, 7), (5, 3, 9),
    (6, 5, 9), (7, 6, 10), (8, 8, 11), (9, 8, 12), (10, 2, 14)
]

count, selected_ids = activity_selection(activities)
print(f"最多安排 {count} 人")
print(f"安排的人：{selected_ids}")

第五题(20分)

题目描述

有五堆石子，数量已知。

只能取两个相邻石子合并，这一次合并的代价是两堆石子数量之和，求合并成一堆的最小代价（10分）
可以取任意两堆石子合并，这一次合并的代价是两堆石子数量之和，求合并成一堆的最小代价（10分）

解答

1. 相邻石子合并 - 动态规划

参考OJ题目：沙子的质量

算法描述：

定义 $dp[i][j]$ 为合并第 $i$ 到第 $j$ 堆石子的最小代价。

状态转移方程：

dp[i][j] = \min_{i \leq k < j} \{dp[i][k] + dp[k+1][j] + sum[i][j]\}

其中 $sum[i][j]$ 表示第 $i$ 到第 $j$ 堆石子的总数量。

边界条件：

dp[i][i] = 0 \quad (单堆石子无需合并)

代码实现：

def min_merge_cost_adjacent(stones):
    n = len(stones)
    
    # 预计算前缀和
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + stones[i]
    
    def get_sum(i, j):
        return prefix_sum[j + 1] - prefix_sum[i]
    
    # dp[i][j] 表示合并区间[i, j]的最小代价
    dp = [[0] * n for _ in range(n)]
    
    # 枚举区间长度
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            # 枚举分割点k
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + get_sum(i, j)
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n - 1]

# 示例：五堆石子
stones = [1, 3, 5, 2, 4]
print(f"最小代价: {min_merge_cost_adjacent(stones)}")

示例计算： 石子数量 [1, 3, 5, 2, 4]

先合并(3,5)→8，代价8，剩余[1,8,2,4]
再合并(2,4)→6，代价6，剩余[1,8,6]
再合并(1,8)→9，代价9，剩余[9,6]
最后合并(9,6)→15，代价15
总代价：8+6+9+15=38（具体最小值需通过DP计算）

2. 任意石子合并 - 贪心算法（哈夫曼）

参考OJ题目：锯木棒、哈夫曼编码

算法描述：

使用哈夫曼算法（Huffman）的思想：每次选择最小的两堆合并。

算法：MinMergeCostAny(stones, n)
输入：n堆石子的数量数组
输出：最小合并代价

begin
    使用最小堆存储所有石子堆
    totalCost = 0
    
    while 堆中元素个数 > 1 do
        取出最小的两堆 a 和 b
        cost = a + b
        totalCost += cost
        将 cost 放回堆中
    end while
    
    return totalCost
end

贪心策略： 总是合并最小的两堆，使得代价较大的合并次数更少。

代码实现：

import heapq

def min_merge_cost_any(stones):
    # 使用最小堆
    heap = list(stones)
    heapq.heapify(heap)
    
    total_cost = 0
    
    while len(heap) > 1:
        # 取出最小的两堆
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        
        # 合并代价
        cost = first + second
        total_cost += cost
        
        # 将合并后的结果放回堆中
        heapq.heappush(heap, cost)
    
    return total_cost

# 示例：五堆石子
stones = [1, 3, 5, 2, 4]
print(f"最小代价: {min_merge_cost_any(stones)}")

示例计算： 石子数量 [1, 3, 5, 2, 4]

合并(1,2)→3，代价3，剩余[3,3,4,5]
合并(3,3)→6，代价6，剩余[4,5,6]
合并(4,5)→9，代价9，剩余[6,9]
合并(6,9)→15，代价15
总代价：3+6+9+15=33

第六题(15分)

题目描述

打算法比赛，还有五个小时，还有五个题目没做，给出题目价值和预计AC题目时间，利用回溯法求最优解。

什么集合类型（5分）
剪枝函数（5分）
画出解空间树（5分）

解答

回溯法 - 0-1背包问题:

参考OJ题目：Homework（试卷选择问题，本质是0-1背包）

问题建模：

背包容量：5小时
物品：5个题目
每个题目有价值 $v_i$ 和所需时间 $t_i$
目标：在时间限制内最大化价值

1. 集合类型：

子集树 - 每个题目有两种选择：做或不做

对于 $n$ 个题目，解空间是一个 $2^n$ 节点的完全二叉树：

深度为 $n+1$ （根节点深度为0）
第 $i$ 层表示对第 $i$ 个题目的选择
左子树：选择该题目
右子树：不选择该题目

2. 剪枝函数：

(1) 约束函数（分支剪枝）：

cw + w_i \leq C

其中：

$cw$ ：当前已用时间
$w_i$ ：第 $i$ 个题目所需时间
$C$ ：总时间限制（5小时）

含义： 如果选择当前题目会超时，则不进入左子树。

(2) 限界函数（限界剪枝）：

cp + rp \leq bestp

其中：

$cp$ ：当前已获得价值
$rp$ ：剩余题目的总价值上界
$bestp$ ：当前已找到的最优解价值

含义： 如果当前路径的价值上界都不如已找到的最优解，则不进入右子树。

更精确的上界估计：

rp = \sum_{j=i+1}^{n} v_j \quad (假设剩余时间足够)

或使用贪心策略估计上界（按性价比排序后的部分背包解）。

3. 解空间树示例：

假设有3个题目（简化示例）：

题目1：价值10，时间2小时
题目2：价值15，时间3小时
题目3：价值8，时间2小时
总时间限制：5小时

                    根节点(0,0)
                   /          \
              选题1(10,2)    不选题1(0,0)
              /      \          /       \
        选题2(25,5) 不选题2   选题2(15,3) 不选题2(0,0)
         [剪枝]    (10,2)      /    \       /      \
                   /   \    选题3  不选题3  选题3   不选题3
                  ...  ... (23,5) (15,3)  (8,2)   (0,0)
                            [最优]

遍历过程：

根节点：cw=0, cp=0
选题1：cw=2, cp=10，继续
选题1且选题2：cw=5, cp=25，到达叶子
选题1不选题2：cw=2, cp=10，选题3：cw=4, cp=18
不选题1选题2：cw=3, cp=15，选题3：cw=5, cp=23 ✓ 最优
…

代码实现：

{% tabs algo-21fa-2 %}

class KnapsackBacktracking:
    def __init__(self, capacity, weights, values):
        self.capacity = capacity  # 背包容量
        self.weights = weights    # 物品重量
        self.values = values      # 物品价值
        self.n = len(weights)     # 物品数量
        self.best_value = 0       # 最优解价值
        self.best_solution = []   # 最优解方案
    
    def backtrack(self, i, cw, cv, solution):
        """
        i: 当前考虑第i个物品
        cw: 当前重量
        cv: 当前价值
        solution: 当前方案
        """
        if i == self.n:
            # 到达叶子节点
            if cv > self.best_value:
                self.best_value = cv
                self.best_solution = solution[:]
            return
        
        # 计算剩余物品的总价值（上界）
        remaining_value = sum(self.values[j] for j in range(i, self.n))
        
        # 限界剪枝：当前价值+剩余价值上界 <= 最优解，剪枝
        if cv + remaining_value <= self.best_value:
            return
        
        # 尝试选择第i个物品（左子树）
        if cw + self.weights[i] <= self.capacity:
            solution.append(i)
            self.backtrack(i + 1, cw + self.weights[i], cv + self.values[i], solution)
            solution.pop()
        
        # 尝试不选择第i个物品（右子树）
        self.backtrack(i + 1, cw, cv, solution)
    
    def solve(self):
        self.backtrack(0, 0, 0, [])
        return self.best_value, self.best_solution

# 示例：5个题目，5小时
times = [2, 3, 2, 1, 4]     # 所需时间
values = [10, 15, 8, 5, 20] # 题目价值
capacity = 5                 # 时间限制

kb = KnapsackBacktracking(capacity, times, values)
max_value, selected = kb.solve()
print(f"最大价值: {max_value}")
print(f"选择的题目: {[i+1 for i in selected]}")

{% endtabs %}

第七题(15分)

题目描述

给出一个图，点是学生，边表示学生之间存在闺蜜关系，求最大闺蜜团，要求利用分支限界法，使用优先队列。

什么集合类型（5分）
剪枝函数（5分）
画出解空间树（5分）

Clique

解答

分支限界法 - 最大团问题（Maximum Clique Problem）:

问题定义：

团（Clique）：图中的一个顶点子集，其中任意两个顶点之间都有边相连
最大团：顶点数最多的团

1. 集合类型：

子集树 - 每个顶点有两种选择：加入团或不加入团

对于 $n$ 个顶点，解空间是一个 $2^n$ 节点的完全二叉树：

第 $i$ 层表示对第 $i$ 个顶点的选择
左子树：将该顶点加入团
右子树：不将该顶点加入团

2. 剪枝函数：

(1) 约束函数（分支剪枝）：

加入顶点 $v_i$ 的条件：

\forall v_j \in \text{CurrentClique}, \quad (v_i, v_j) \in E

含义： 当前顶点必须与已在团中的所有顶点都有边相连，否则不能进入左子树。

(2) 限界函数（限界剪枝）：

num = cn + rn \leq bestn

其中：

$cn$ ：当前团的顶点数
$rn$ ：剩余可选顶点数
$bestn$ ：当前已找到的最大团的顶点数

含义： 如果当前团大小加上剩余顶点数的上界都不超过已知最优解，则剪枝。

(3) 优先级（优先队列式分支限界）：

使用 $num = cn + rn$ 作为优先级：

$num$ 越大，优先级越高
优先扩展最有希望的节点
使用最大堆实现优先队列

3. 解空间树示例：

假设有4个学生，邻接关系如下：

图的邻接矩阵：
    1  2  3  4
1 [ 0  1  1  0 ]
2 [ 1  0  1  1 ]
3 [ 1  1  0  1 ]
4 [ 0  1  1  0 ]

边集：{(1,2), (1,3), (2,3), (2,4), (3,4)}

                      根节点
                    ([], rn=4)
                    num=4
                   /          \
              选v1([1],3)    不选v1([],3)
              num=4          num=3
              /      \          /       \
        选v2(剪枝)  不选v2   选v2([2],2) 不选v2([],2)
        v1-v2无边   ([1],2)   num=4      num=2
                    num=3      /    \       /      \
                    /    \   选v3  不选v3  选v3   不选v3
                 选v3  不选v3 ([2,3],1) ...
              ([1,3],1) ...
               num=2
                 /  \
              选v4  不选v4
             (剪枝) ([1,3],0)
             v1-v4  cn=2 ✓
             无边

优先队列遍历顺序（按num降序）：

根节点(num=4)
选v1(num=4)或不选v1(num=3) → 优先选v1
选v1不选v2(num=3)或选v2([2],num=4) → 优先选v2
继续扩展…

最终找到最大团：{2, 3, 4} 或 {1, 2, 3}（大小为3）

代码实现：

{% tabs algo-21fa-3 %}

import heapq

class MaxCliqueNode:
    def __init__(self, current_clique, remaining, cn, rn):
        self.current_clique = current_clique  # 当前团
        self.remaining = remaining            # 剩余顶点
        self.cn = cn                          # 当前团大小
        self.rn = rn                          # 剩余顶点数
        self.num = cn + rn                    # 优先级
    
    def __lt__(self, other):
        # 最大堆：num越大优先级越高
        return self.num > other.num

class MaxCliqueBranchBound:
    def __init__(self, graph):
        self.graph = graph        # 邻接矩阵
        self.n = len(graph)       # 顶点数
        self.best_clique = []     # 最优解
        self.best_size = 0        # 最优解大小
    
    def is_connected_to_all(self, vertex, clique):
        """检查vertex是否与clique中所有顶点相连"""
        for v in clique:
            if not self.graph[vertex][v]:
                return False
        return True
    
    def solve(self):
        # 初始化优先队列
        pq = []
        initial_node = MaxCliqueNode([], list(range(self.n)), 0, self.n)
        heapq.heappush(pq, initial_node)
        
        while pq:
            node = heapq.heappop(pq)
            
            # 限界剪枝
            if node.num <= self.best_size:
                continue
            
            # 到达叶子节点
            if not node.remaining:
                if node.cn > self.best_size:
                    self.best_size = node.cn
                    self.best_clique = node.current_clique[:]
                continue
            
            # 选择第一个剩余顶点
            v = node.remaining[0]
            remaining = node.remaining[1:]
            
            # 尝试加入顶点v（左子树）
            if self.is_connected_to_all(v, node.current_clique):
                left_node = MaxCliqueNode(
                    node.current_clique + [v],
                    remaining,
                    node.cn + 1,
                    len(remaining)
                )
                heapq.heappush(pq, left_node)
            
            # 不加入顶点v（右子树）
            right_node = MaxCliqueNode(
                node.current_clique,
                remaining,
                node.cn,
                len(remaining)
            )
            heapq.heappush(pq, right_node)
        
        return self.best_size, self.best_clique

# 示例图
graph = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
]

mc = MaxCliqueBranchBound(graph)
max_size, max_clique = mc.solve()
print(f"最大团大小: {max_size}")
print(f"最大团顶点: {[v+1 for v in max_clique]}")

{% endtabs %}

算法复杂度：

最坏情况： $O(2^n)$ （遍历整个解空间树）

通过剪枝可大幅减少实际搜索节点数。