算法应用主题赛 · Python · 共 14 题（5单选+5多选+4编程）· 满分 100 分
knowledge(4) 的输出结果是多少？def knowledge(n):
if n == 1:
return 1
else:
return 2 * knowledge(n - 1)
print(knowledge(4))knowledge(1)=1, knowledge(2)=2, knowledge(3)=4, knowledge(4)=8pattern = [
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0]
]
print(pattern[2][4])pattern[2] 是第3行（索引从0开始），即 [1,1,1,1,1]，其中索引4的值为 1total = 0
def produce(n):
global total
total += n
return total
print(produce(10))
print(produce(20))
print(total)global 关键字——声明 global total 后，函数内部对 total 的修改会直接影响全局变量result 中存储的是什么？paper_cut = {"张三", "李四", "王五", "赵六"}
embroidery = {"李四", "赵六", "孙七", "周八"}
result = paper_cut & embroidery
print(result)& 是交集运算符，返回两个集合共有的元素题目描述：
中国传统剪纸艺术讲究对称之美，艺人常常将纸张对折后剪裁，展开即得左右对称的精美图案。现在用一个 n x n 的二维列表来表示一幅剪纸图案，其中 1 表示有剪纸的部分，0 表示空白。请编写程序判断该图案是否关于垂直中轴线左右对称。
假设 n 为奇数（即存在一条明确的垂直中轴线，位于正中间一列）。
输入格式：
- 第一行：一个奇数 n（1 <= n <= 99），表示图案的行数和列数
- 接下来 n 行：每行 n 个整数（0或1），空格分隔
输出格式：
- 如果图案关于垂直中轴线左右对称，输出 左右对称
- 否则输出 不对称
示例输入1：
5
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
示例输出1：
左右对称
示例输入2：
3
1 0 0
0 1 0
0 0 1
示例输出2：
不对称
示例输入：
示例输出：
n = int(input())
# 读取二维图案
pattern = []
for i in range(n):
row = list(map(int, input().split()))
pattern.append(row)
# 垂直中轴线的列索引
mid = n // 2
# 检测左右是否对称
symmetric = True
for i in range(n):
for j in range(mid):
# 比较左边第j列和右边对应列 (n-1-j)
if pattern[i][j] != pattern[i][n - 1 - j]:
symmetric = False
break
if not symmetric:
break
if symmetric:
print("左右对称")
else:
print("不对称")
题目描述：
某非遗文化节计划举办多场手工体验活动（如剪纸教学、泥塑体验、蜡染展示等）。每场活动有固定的开始时间和结束时间（用24小时制的 HH:MM 格式表示）。由于场地有限，同一时间只能进行一场活动。请编写程序，使用贪心算法计算：
1. 最多能安排多少场活动
2. 按顺序输出被选中的活动编号
输入格式：
- 第一行：一个整数 n，表示活动的总数量
- 接下来 n 行：每行两个字符串，分别表示活动的开始时间和结束时间（格式为 HH:MM），活动按输入顺序编号为 1, 2, ..., n
输出格式：
- 第一行：一个整数，表示最多可安排的活动数量
- 第二行：被选中活动的编号，空格分隔
示例输入：
示例输出：
n = int(input())
# 读取活动信息，将时间转换为分钟数便于比较
activities = []
for i in range(n):
start, end = input().split()
# 将 HH:MM 转换为从0点开始的分钟数
start_min = int(start[:2]) * 60 + int(start[3:])
end_min = int(end[:2]) * 60 + int(end[3:])
# 存储：(开始分钟, 结束分钟, 原始编号)
activities.append((start_min, end_min, i + 1))
# 贪心策略：按结束时间从小到大排序
activities.sort(key=lambda x: x[1])
selected = [] # 被选中活动的编号
last_end = -1 # 上一个选中活动的结束时间
for act in activities:
start_min, end_min, idx = act
# 如果当前活动的开始时间不早于上一个活动的结束时间
if start_min >= last_end:
selected.append(idx)
last_end = end_min
# 输出结果
print(len(selected))
print(' '.join(map(str, selected)))
题目描述：
刺绣中有一种具有自相似特征的图案——分形图案。这类图案在不同的尺度上呈现出相似的结构。请编写程序，使用递归的方式生成一个分形图案。
图案定义规则如下：
- level = 1（基础图案）：一个 3x3 的网格，中心位置为空格，其余8个位置为字符 "*"
- level = n（n > 1）：将 level = n-1 的图案作为基础单元，按照 3x3 的方式排列，中心单元为全空白的区域（大小等同于一个基础单元），其余8个单元各自放置一个 level = n-1 的图案
输入格式：
输出格式：
示例输入1：
1
示例输出1：
***
* *
***
示例输入2：
2
示例输出2：
*****
* *
*****
* *
* * * *
* *
*****
* *
*****
示例输入：
示例输出：
def draw(level):
"""递归生成level级分形图案，返回字符串列表（每行一个字符串）"""
# 基准情况：level=1的3x3图案
if level == 1:
return ["***", "* *", "***"]
# 递归获取level-1的图案
smaller = draw(level - 1)
size = len(smaller) # level-1图案的边长
# 构建level图案，边长 = size * 3
result = []
# 空白区域：全为空格，大小与smaller相同
empty_row = " " * size
# 上部三行（3行 small图案横向拼接）
for row in smaller:
result.append(row * 3)
# 中部三行（左: small图案, 中: 空白, 右: small图案）
for row in smaller:
result.append(row + empty_row + row)
# 下部三行（3行 small图案横向拼接）
for row in smaller:
result.append(row * 3)
return result
# 主程序
level = int(input())
pattern = draw(level)
# 输出图案
for line in pattern:
print(line)
题目描述：
风筝是中国传统手工艺品的杰出代表，放飞风筝是一项深受人们喜爱的户外活动。在一个 n 行 m 列的场地中，有若干障碍物（如树木、建筑物等），风筝手需要找到一条从起点（左上角位置 (0, 0)）到终点（右下角位置 (n-1, m-1)）的路径。风筝每次可以向上、下、左、右四个方向之一移动一格，但不能移出场地边界，也不能穿过障碍物。
请编写程序，使用广度优先搜索（BFS）判断是否存在可行路径，若存在则输出最短路径经过的格子数（含起点和终点）。
输入格式：
- 第一行：两个整数 n 和 m（1 <= n, m <= 50），表示场地的行数和列数
- 接下来 n 行：每行 m 个整数（0 或 1），空格分隔。0 表示空地（可通行），1 表示障碍物（不可通行）
输出格式：
- 如果存在路径：
- 第一行输出 YES
- 第二行输出最短路径经过的格子数（整数）
- 如果不存在路径：
- 输出 NO
示例输入1：
3 3
0 0 0
0 1 0
0 0 0
示例输出1：
YES
5
样例1解释：
最短路径为：(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)，共经过5个格子。
示例输入2：
3 3
0 1 0
1 1 1
0 1 0
示例输出2：
NO
样例2解释：
起点(0,0)被障碍物包围（右、下均为障碍物），无法到达终点(2,2)。
算法提示：
使用广度优先搜索（BFS）逐层扩展访问可通行的格子。用一个队列存储待访问位置及其步数，用一个 visited 二维布尔列表标记已访问的格子，避免重复访问。当队列弹出终点坐标时，返回当前步数即为最短路径长度。
示例输入：
示例输出：
from collections import deque
def find_shortest_path(grid, n, m):
"""BFS搜索从(0,0)到(n-1,m-1)的最短路径长度"""
# 如果起点或终点是障碍物，直接返回不可达
if grid[0][0] == 1 or grid[n - 1][m - 1] == 1:
return None
# BFS队列，元素为 (行, 列, 步数)
queue = deque()
queue.append((0, 0, 1))
# 标记已访问的格子
visited = [[False] * m for _ in range(n)]
visited[0][0] = True
# 四个方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
r, c, steps = queue.popleft()
# 到达终点
if r == n - 1 and c == m - 1:
return steps
# 探索四个方向
for dr, dc in directions:
nr, nc = r + dr, c + dc
# 检查边界、是否可通行、是否未访问
if 0 <= nr < n and 0 <= nc < m:
if not visited[nr][nc] and grid[nr][nc] == 0:
visited[nr][nc] = True
queue.append((nr, nc, steps + 1))
# 队列为空仍未到达终点，说明不可达
return None
# 主程序
n, m = map(int, input().split())
grid = []
for i in range(n):
row = list(map(int, input().split()))
grid.append(row)
result = find_shortest_path(grid, n, m)
if result is not None:
print("YES")
print(result)
else:
print("NO")