本简介汇集了哈尔滨工业大学2024年春季学期《算法设计与分析》课程期末考试题目，旨在为学习者提供复习和备考的参考。
### 哈工大2024春算法设计与分析期末考试题回忆版知识点解析
#### 一、最长公共子序列问题（动态规划方法）
**题目背景：**
本题考查了如何使用动态规划方法求解两个字符串的最长公共子序列(Longest Common Subsequence, LCS)。
**知识点解析：**
1. **定义：**
- 最长公共子序列是指在两个序列中找出一个最长的共同部分。
- 子序列是从原序列中删除若干元素后剩下的序列。
2. **动态规划方法：**
- **状态定义**：设两个序列为`X = `和`Y = `，记`C[i][j]`为`X[1..i]`和`Y[1..j]`的LCS长度。
- **递推公式**：
- 如果 `xi = yj`, 那么 `C[i][j] = C[i-1][j-1] + 1`.
- 否则，如果 `xi ≠ yj`, 则 `C[i][j] = max(C[i-1][j], C[i][j-1])`。
- **边界条件**：当 `i = 0` 或者 `j = 0`时, `C[i][j]=0`.
3. **算法伪代码：**
```plaintext
function LCS_Length(X[1..m], Y[1..n])
for i from 0 to m do
C[i][0] := 0
for j from 0 to n do
C[0][j] := 0
for i from 1 to m do
for j from 1 to n do
if X[i] == Y[j]
C[i][j] := C[i-1][j-1] + 1
else
C[i][j] := max(C[i-1][j], C[i][j-1])
return C[m][n]
```
4. **构建代价矩阵**：根据上述伪代码，可以构造出一个矩阵`C`, 其中 `C[i][j]` 表示序列`X[1..i]`与`Y[1..j]`的LCS长度。
#### 二、合并两个有序数组后的中位数
**题目背景：**
本题考查了如何求解两个有序数组合并后的新数组中的中位数值，特别地，题目强调这两个数组个数相同且均为偶数的情况。
**知识点解析：**
1. **计算过程**：
- 将两个已排序的数组合并成一个新的有序数组。
- 找到新数组中间位置的两个元素，并取它们平均值作为中位数值。
2. **伪代码：**
```plaintext
function MedianOfTwoSortedArrays(A, B)
m := length(A)
n := length(B)
totalLength := m + n
midIndex := (totalLength // 2) - 1 # 对于偶数个元素的中位数值计算
i := 0
j := 0
count := 0
prevMid := 0
currentMid := 0
while (count <= midIndex)
if (i < m and (j >= n or A[i] < B[j]))
prevMid = currentMid;
currentMid = A[i];
i++;
else
prevMid = currentMid;
currentMid = B[j];
j++;
count++
return (prevMid + currentMid) // 2
```
3. **时间复杂度分析**：
- 最坏情况下，需要遍历两个数组中的所有元素, 时间复杂度为 O(m+n).
- 通过优化可以减少不必要的比较次数，实现更高效的时间复杂度O(log(min(m, n))).
#### 三、农田灌溉问题
**题目背景：**
本题考查的是如何设计搜索算法来解决农田灌溉的问题。目标是确保所有的庄稼都得到灌溉并且所有水龙头的水量都被用完。
**知识点解析：**
1. **问题描述**：
- 给定一个大小为`m×n`的农田，其中有k个水龙头。
- 每个水龙头可以朝东南西北四个方向沿直线喷洒水分且每种水源量不同。
- 目标是设计一种灌溉方案, 使得每个位置上的庄稼恰好由一个水龙头进行灌溉。
2. **算法设计**：
- 可以考虑使用回溯法来解决这个问题。
- 首先确定每个水龙头
5星
