算法应用主题赛 · Python · 共 14 题（5单选+5多选+4编程）· 满分 100 分
for j循环总共执行了多少次比较？scores = [85, 92, 78, 95, 88]
n = len(scores)
for i in range(n - 1):
for j in range(n - 1 - i):
if scores[j] < scores[j + 1]:
scores[j], scores[j + 1] = scores[j + 1], scores[j]题目描述：
红军情报站将情报按编号从小到大的顺序存储在列表中。现需要快速查找某个情报编号是否存在，以及它在列表中的位置（索引）。请你编写程序，使用二分查找算法在已排序的情报编号列表中查找目标编号。如果找到，输出其位置（索引从0开始）；如果未找到，输出"未找到该情报"。
要求：必须使用二分查找算法实现，否则不得分。
输入格式：
第一行一个正整数 n（1 ≤ n ≤ 1000）和一个目标编号 target，用空格分隔。
第二行 n 个严格递增的整数，用空格分隔，表示已排序的情报编号列表。
输出格式：
如果找到，输出"情报编号X位于索引Y"（Y从0开始）。
如果未找到，输出"未找到该情报"。
示例输入1：
6 300
100 150 200 300 450 600
示例输出1：
情报编号300位于索引3
示例输入2：
5 250
100 150 200 300 450
示例输出2：
未找到该情报
示例输入：
示例输出：
# 输入 n 和目标编号
line = input().split()
n = int(line[0])
target = int(line[1])
# 输入已排序的情报编号列表
arr = list(map(int, input().split()))
# 二分查找
left = 0
right = n - 1
found = False
index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
found = True
index = mid
break
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
if found:
print("情报编号" + str(target) + "位于索引" + str(index))
else:
print("未找到该情报")
题目描述：
红军运输队需要从仓库中选取若干件物资运往前线。每件物资有固定的重量和价值（战略重要度）。运输队的最大承载重量为W。请你编写程序，计算在不超过载重限制的情况下，能够装载的物资最大总价值是多少。
提示：本题是经典的0-1背包问题，可使用动态规划或枚举法解决。设 dp[i][w] 表示前 i 件物资在载重 w 下的最大价值。
输入格式：
第一行两个整数 n 和 W（1 ≤ n ≤ 20，1 ≤ W ≤ 200），分别表示物资件数和最大载重。
接下来 n 行，每行两个整数：物资重量和价值，用空格分隔。
输出格式：
一个整数，表示最大总价值。
示例输入1：
4 10
2 6
3 8
4 10
5 12
示例输出1：
22
说明：选择第2件(重量3,价值8)、第3件(重量4,价值10)、第4件(重量5,价值12)时总重量=12>10，不行。选择第1件(2,6)、第2件(3,8)、第3件(4,10)时总重量=9≤10，总价值=24，但9+2=11>10。选择第1件和第4件：重量2+5=7≤10，价值6+12=18。选择第2件和第4件：重量3+5=8≤10，价值8+12=20。选择第3件和第4件：重量4+5=9≤10，价值10+12=22。最大为22。
示例输入2：
3 5
2 3
3 4
4 5
示例输出2：
7
示例输入：
示例输出：
# 0-1背包问题 —— 动态规划解法
line = input().split()
n = int(line[0])
W = int(line[1])
weights = []
values = []
for i in range(n):
w, v = map(int, input().split())
weights.append(w)
values.append(v)
# dp[i][w] 表示前i件物品在容量w下的最大价值
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
# 不选第i件物品
dp[i][w] = dp[i - 1][w]
# 如果能选第i件物品，比较选与不选的价值
if w >= weights[i - 1]:
new_value = dp[i - 1][w - weights[i - 1]] + values[i - 1]
if new_value > dp[i][w]:
dp[i][w] = new_value
print(dp[n][W])
题目描述：
红军截获了一段敌军密码，密码由若干字符组成，但不知道这些字符的排列顺序。情报员需要生成密码中所有字符的所有可能排列，并按字典序输出。请你编写程序，输入一个字符串（所有字符不重复），输出该字符串所有字符的全排列（每个排列占一行），按字典序升序排列。
提示：可以使用递归（回溯法）或 Python 的 itertools.permutations。
输入格式：
一行字符串，长度不超过6，所有字符互不相同。
输出格式：
按字典序升序输出所有排列，每行一个排列。
示例输入：
示例输出：
s = input().strip()
n = len(s)
# 使用递归（回溯法）生成全排列
used = [False] * n
result = []
def dfs(path):
if len(path) == n:
result.append("".join(path))
return
for i in range(n):
if not used[i]:
used[i] = True
path.append(s[i])
dfs(path)
path.pop()
used[i] = False
# 确保按字典序输出：先对原字符串排序
sorted_s = sorted(s)
s = "".join(sorted_s)
dfs([])
for perm in result:
print(perm)
题目描述：
红军需要在敌占区找到一条从起点到终点的最短突破路径。战场地图是一个n行m列的网格，其中0表示可通行的空地，1表示障碍物（不可通行）。起点为左上角(0, 0)，终点为右下角(n-1, m-1)。部队每次可以向上下左右四个方向移动一格（不能斜着走，不能穿过障碍物）。请你编写程序，使用广度优先搜索（BFS）计算从起点到终点的最短路径步数。如果无法到达终点，输出-1。
输入格式：
第一行两个正整数 n 和 m（1 ≤ n, m ≤ 50），表示地图的行数和列数。
接下来 n 行，每行 m 个整数（0或1），用空格分隔。
输出格式：
一个整数，表示最短路径的步数。如果无法到达，输出-1。
示例输入1：
4 5
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
0 0 1 0 0
示例输出1：
7
说明：从(0,0)到(3,4)的最短路径经过 (0,0)→(1,0)→(2,0)→(2,1)→(2,2)→(2,3)→(3,3)→(3,4)，共7步。
示例输入2：
3 3
0 1 0
0 1 0
0 1 0
示例输出2：
-1
说明：中间一列全是障碍物，无法从左边到达右边。
示例输入：
示例输出：
# BFS 最短路径
line = input().split()
n = int(line[0])
m = int(line[1])
grid = []
for i in range(n):
row = list(map(int, input().split()))
grid.append(row)
# 方向数组：上下左右
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 距离数组，-1表示未访问
dist = [[-1] * m for _ in range(n)]
# 起点
queue = []
if grid[0][0] == 0:
queue.append((0, 0))
dist[0][0] = 0
head = 0 # 用列表+索引模拟队列
while head < len(queue):
x, y = queue[head]
head += 1
# 到达终点
if x == n - 1 and y == m - 1:
break
# 探索四个方向
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 检查边界、障碍物、是否已访问
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if grid[nx][ny] == 1:
continue
if dist[nx][ny] != -1:
continue
dist[nx][ny] = dist[x][y] + 1
queue.append((nx, ny))
print(dist[n - 1][m - 1])