# 技术部论文复现组——Python测试题

## 一、测试题说明

技术部分为两个学习组，其中论文复现组学习节奏更快，对自学能力与逻辑思维有一定要求。本测试题用于帮助大家自我评估能力，以便在后续填写分组意愿问卷时，判断是否适合加入论文复现组。

### 题目构成

题目分为 **Level 1（基础）、Level 2（进阶）、Level 3（挑战）** 三个等级，分别包含 4 道、3 道、3道题目，测试者可任选题练习。

### 核心建议

编程学习的核心是“解决未知问题的能力”，题目可能无法直接通过现有知识快速解答，建议多思考、多尝试自主排查问题（如查阅文档、调试代码），这也是论文复现组必备的核心能力。

## 二、提交要求

1. **题目注释声明**：测试者需要在代码文件第一行填写注释  `姓名_等级_题号` 来表示当前完成的题目序号（例如：`# 张三_1_1`，等级用数字1/2/3表示，题号用数字1/2/...表示）。
2. **提交方式**：在论文复现组网站的提交处上传代码，或者直接访问提交链接：[论文复现组提交处](https://f.wps.cn/g/ep5IgqHt/)，本次任务上传代号为001。
3. **多题提交规则**：若测试者完成了多道题目，可以一次性提交所有题目的代码文件，或者打包为zip上传。

## 三、题目正文

### Level 1（基础级）

#### 1. 文件夹里有多少图片？

**需求**：编写代码计算指定文件夹下的图片总数（仅统计 `png` 和 `jpg` 两种格式），需**确保子文件夹中的图片不被遗漏**。

#### 2. 步入 OOP 的殿堂

**需求**：OOP(面向对象编程)是我们编程解决问题的一个重要思想。根据以下使用示例及输出内容，编写一个类 Dog：

```python
# 1. 初始化对象，传入名字
dogQ = Dog("Q")
# 2. 访问对象的 name 属性
print(dogQ.name)  # 输出：Q

# 3. 两个狗对象互动
dogX = Dog("X")
dogX.play_with(dogQ)  # 输出：X is playing with Q

# 4.  bark（叫）与 is_barking（是否在叫）状态管理
print(dogQ.is_barking())  # 初始状态：False
dogQ.bark()  # 输出：Q is barking!
print(dogQ.is_barking())  # 叫之后状态：True

# 5. get_food（喂食）后， bark 状态重置
dogQ.get_food()
print(dogQ.is_barking())  # 喂食后状态：False
```

#### 3. 二维向量类

**需求**：实现 `Vector2d` 类表示二维向量，支持以下核心功能：

- 向量加减法
- 求向量模长
- 求反向量
- 判断两向量是否垂直
- 判断两向量是否共线

**使用示例**（向量加法支持两种形式，实现任意一种即可）：

```python
# 初始化两个向量（x坐标，y坐标）
vec_a = Vector2d(3, 5)
vec_b = Vector2d(1, 2)

# 形式1：通过运算符重载实现加法
print(vec_a + vec_b)  # 输出：(4, 7)
# 形式2：通过成员方法 add 实现加法
print(vec_a.add(vec_b))  # 输出：(4, 7)
```

#### 4. 电动车没电了！

**背景**：你骑着电动车出去跟朋友一起玩，然而路途遥远，返程时电动车 没 电 了！最后辛辛苦苦回到了家，为了避免这种情况再次发生，你决定要用计算机帮忙计算电动车能走的路程！

**需求**：实现 `EBicycle` 类，满足以下功能：

1. **初始化**：创建对象时传入 `总电量` 和 `最大速度` 两个参数。
2. **续航判断**：给定当前行驶速度 `v` 和目标路程 `s`，判断能否到达：
   - 若电量不足：输出 `无法以该速度到达目的地！`
   - 若电量充足：更新当前电量，并输出更新后的电量。
3. **充电功能**：调用充电方法后，当前电量重置为“总电量”。

**核心公式**（电动车续航与电量消耗计算）：

- 最大里程数：$S = \frac{v\eta C}{P + mv + nv^2}$
- 已知路程求消耗电量：可通过上述公式变形推导（$C$ 为当前电量）
- 固定参数：$\eta=0.7$（效率）、$P=2$（基础功率）、$m=0.1$（线性阻力系数）、$n=0.02$（二次阻力系数）

> tips：本题目的情景改编自论文复现组上任部长真实经历，他说推一个小时电动车真的很累！

### Level 2（进阶级）

#### 1. 再看 OOP

**需求**：实现 `Math` 类，通过**静态方法**封装以下数学工具功能（可以无需实例化，直接通过类调用）：

- 求算术平方根（sqrt）
- 求绝对值（abs）
- 上取整（ceil）
- 下取整（floor）
- 四舍五入取整（round）
- 幂运算（fastpow，要求使用快速幂算法实现，而不是使用编程语言自带或库中的的pow()函数，只需要实现正整数的快速幂运算即可）

**使用示例**（需严格保证以下调用格式可正确输出）：

```python
print(Math.sqrt(4))   # 输出：2.0（或2，允许浮点数微小误差）
print(Math.abs(-2))   # 输出：2
print(Math.fastpow(3, 10))  # 输出：59049
```

**说明**：平方根运算可能因浮点数精度产生微小误差，属于正常情况。

**快速幂算法说明**：

快速幂是一种巧妙的计算方法，可以更快地计算 $a^n$（比如 $3^{10}$）。

> 贴士：快速幂算法实际上涉及到二进制运算和算法时间复杂度等计算机科学的重要概念。为了让同学更容易理解，我们在下面用更通俗的方式来讲解这个算法的核心思想。

**核心思想**：不需要把 $a$ 连续乘 $n$ 次，而是利用"指数可以拆分"的特点来减少计算次数。

**举个例子**：计算 $3^{10}$

- 普通方法：$3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3$（需要做9次乘法）
- 快速幂方法：
  - 我们注意到 $10 = 8 + 2$
  - 所以 $3^{10} = 3^8 \times 3^2$
  - 而 $3^8 = (3^4)^2$，$3^4 = (3^2)^2$，$3^2 = 3 \times 3$
  - 这样只需要做4次乘法就能得到结果！

**实现思路**：

1. 从指数 $n$ 开始，如果 $n$ 是偶数，可以把 $a^n$ 转化为 $(a^2)^{n/2}$
2. 如果 $n$ 是奇数，先提取一个 $a$ 出来，变成 $a \times a^{n-1}$，然后继续处理 $a^{n-1}$
3. 重复上述过程，直到指数变为0

> 提示：判断一个数是奇数还是偶数，可以用 `n % 2` 来判断（余数为1则为奇数）

#### 2. 阅读理解 - MLP计算

**背景**：MLP(多层感知机)是深度学习中最简单的一种神经网络，尝试实现 以下 MLP 模型：

![mlp](https://github.com/3030Scar/mdg_papergroup/blob/main/img/mlp_struct.png?raw=true)

> 图中使用圆形代表神经元，表示一个变量

**模型结构**（共两层映射）：

- 输入层（第1列）：3个神经元（记为 $x[1,1], x[1,2], x[1,3]$）
- 隐藏层（第2列）：4个神经元（记为 $x[2,1], x[2,2], x[2,3], x[2,4]$）
- 输出层（第3列）：2个神经元（记为 $x[3,1], x[3,2]$）

**计算规则**：
对于第 $a$ 列（$a \geq 2$）的第 $b$ 个神经元，其值为前一列（$a-1$ 列）所有神经元与对应权重的乘积之和：$x[a, b] = \sum_{c=1}^{m} x[a-1, c] \times w[a-1, c, b]$其中：

- $m$ 为第 $a-1$ 列的神经元个数（如计算 $x[2,b]$ 时，$m=3$；计算 $x[3,b]$ 时，$m=4$）
- $w[i, j, k]$ 表示第 $i$ 层（对应第 $i$ 列到第 $i+1$ 列）中，左侧第 $j$ 个神经元到右侧第 $k$ 个神经元的权重（共 $3×4 + 4×2 = 20$ 个权重）

**需求**：

1. 自由设定或者读取用户输入数据（$x[1,1], x[1,2], x[1,3]$）和所有权重 $w$（权重也可以通过随机数生成）。
2. 计算并输出输出层（第3列）两个神经元的最终结果。
3. 建议：将 MLP 封装为类实现（非强制，但推荐）。

> tips：题目对专业概念并没有硬性要求，主要考察通过阅读来理解计算方法并复现的能力。另外希望同学知道实际的MLP除了w（权重）还有b（偏置），但此处省略。

#### 3. 爬楼梯

**题目来源**：LeetCode 70. 爬楼梯（[https://leetcode-cn.com/problems/climbing-stairs/](https://leetcode-cn.com/problems/climbing-stairs/)）

**需求**：输入一个整数 $n$（表示楼梯的台阶数），输出一个整数（表示爬到楼顶的不同方法数）。

**规则**：每次只能爬 1 级或 2 级台阶，且只剩 1 级台阶时，不能爬 2 级。

**要求**：需在 LeetCode 上通过所有测试用例后，再按提交要求上传代码。

### Level 3（挑战级）

#### 1. 数字华容道游戏

**背景**：数字华容道是经典滑块游戏，在 $N×N$ 方格中排列数字 1~N²-1（留有一个空白格），通过移动滑块使数字按顺序排列。

**示例**（4×4 华容道复原目标）：

混乱状态
[ 3] [ 8] [ 5] [ 2]
[ 1] [ 7][14][10]
[12][ 9][11]
[ 4][13] [ 6][15]
复原为
[ 1] [ 2] [ 3] [ 4]
[ 5] [ 6] [ 7] [ 8]
[ 9] [10] [11] [12]
[13] [14] [15]

**核心需求**：

1. 生成有解的 $N×N$ 华容道初始状态（建议从复原状态开始随机打乱，确保有解）。
2. 实现滑块移动逻辑（如通过输入方向键/指令移动空白格周边的数字）。
3. 无需制作 UI 界面，输出控制台格式的方格即可（参考下图）：
   ![参考示例图](https://github.com/3030Scar/mdg_papergroup/blob/main/img/%E7%BB%88%E7%AB%AF%E7%A4%BA%E4%BE%8B%E5%9B%BE.png?raw=true)

**扩展功能**（可选）：

- 用文件记录当前游戏的最少步数。
- 实现“输入移动方向后无需按回车”的即时操作。

#### 2. 大学生勇闯洛谷

需在洛谷上通过所有测试用例后，再按提交要求上传代码。

##### 2.1洛谷 P4995 小跳蛙的跳跃

**题目链接**：[https://www.luogu.com.cn/problem/P4995](https://www.luogu.com.cn/problem/P4995)

**题目描述**：
小跳蛙要跳到每块石头上各一次（最终停在任意一块石头上），地面高度 $h_0=0$。从第 $i$ 块石头跳到第 $j$ 块石头的体力消耗为 $(h_i - h_j)^2$，从地面跳到第 $i$ 块石头的体力消耗为 $h_i^2$。要求计算消耗的**最大体力值**。

**输入格式**：

1. 第一行：正整数 $n$（石头个数）。
2. 第二行：$n$ 个正整数（分别表示第 1~n 块石头的高度 $h_i$，所有 $h_i$ 互不相同）。

**输出格式**：一行正整数（最大体力值）。

**示例**：

| 输入样例1 | 输出样例1 |
| --------- | --------- |
| 2         | 21        |
| 5         |           |

| 输入样例2 | 输出样例2 |
| --------- | --------- |
| 3         | 635       |
| 4 9 5     |           |

##### 2.2洛谷 P1004 方格取数

**题目链接**：[https://www.luogu.com.cn/problem/P1004](https://www.luogu.com.cn/problem/P1004)（建议有信息竞赛基础的同学尝试）

**题目描述**：
在 $N×N$ 的方格图中（$N \leq 9$），部分方格有正整数，其余为 0。从左上角 A 点出发，只能向下或向右走，到达右下角 B 点，共走两次。走过的方格中的数会被取走（取走后变为 0），求两次取数的**最大总和**。
![示例图](https://github.com/3030Scar/mdg/blob/main/img/others1.png?raw=true)

**输入格式**：

1. 第一行：整数 $N$（方格图大小）。
2. 接下来若干行：每行三个整数（前两个为方格位置 $(x,y)$，第三个为该方格的数），一行单独的 `0 0 0` 表示输入结束。

**输出格式**：一行整数（两次取数的最大总和）。

**示例**：

| 输入样例1 | 输出样例1 |
| --------- | --------- |
| 8         | 67        |
| 2 3 13    |           |
| 2 6 6     |           |
| 3 5 7     |           |
| 4 4 14    |           |
| 5 2 21    |           |
| 5 6 4     |           |
| 6 3 15    |           |
| 7 2 14    |           |
| 0 0 0     |           |