算法应用主题赛 · Python · 共 14 题（5单选+5多选+4编程）· 满分 100 分
pixels 存储图像数据。若图像有 m 行 n 列，要获取第 i 行第 j 列的像素值，正确的访问方式是？f(1) = 10，f(n) = f(n-1) + n * 3（n > 1）。则 f(4) 的值是？capacity 件。以下使用贪心策略的代码要实现"用最少的箱子装完所有货物"，应在横线处填入？items = [5, 3, 8, 2, 6]
capacity = 10
boxes = 0
current = 0
for item in items:
if current + item > capacity:
boxes += 1
current = _____
current += itemcount 的最终值是？count = 0
for i in range(3):
for j in range(3):
if i != j:
for k in range(3):
if k != i and k != j:
count += 1
print(count)def routes(n):
if n <= 1:
return 1
return routes(n - 1) + routes(n - 2)
print(routes(5))matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]题目描述：
丝绸之路上的商人需要在不同城市之间贩运商品。商品在每个城市的买入价和卖出价不同。商人从城市A出发，经过若干个城市到达终点，共经过 n 个城市。在每个城市，他可以选择买入商品，然后在之后经过的任何一个城市卖出。每笔交易只能买卖一次（必须先买后卖）。
已知每个城市的商品价格（整数，单位：文），请你编写程序，帮商人计算在整条路线中能获得的最大利润。如果无法获得利润（价格一直在下跌），则输出 0。
输入格式：
第一行：一个正整数 n，表示经过的城市数量。
第二行：n 个正整数，以空格分隔，依次表示每个城市的商品价格。
输出格式：
一行，输出一个整数，表示最大利润。
示例输入1：
6
7 1 5 3 6 4
示例输出1：
5
（解释：在第2个城市买入（价格为1），在第5个城市卖出（价格为6），利润为 6-1=5。）
示例输入2：
4
7 6 4 3
示例输出2：
0
（解释：价格一直下跌，无法获利。）
示例输入：
示例输出：
n = int(input())
prices = list(map(int, input().split()))
min_price = prices[0]
max_profit = 0
for i in range(1, n):
profit = prices[i] - min_price
if profit > max_profit:
max_profit = profit
if prices[i] < min_price:
min_price = prices[i]
print(max_profit)
题目描述：
驼队从起点出发前往终点，总路程为 distance 里。沿途有 n 个驿站，每个驿站距离起点的里程已知（整数，单位：里）。驼队每天最多只能行进 max_per_day 里，且必须在驿站处停靠过夜（不能在驿站之外的地方露营）。
请你使用贪心算法编写程序，计算驼队最少需要多少天才能到达终点。如果驼队无法在限制条件下到达终点（即存在两个相邻停靠点之间的距离超过了每日最大行程），则输出 -1。
输入格式：
第一行：三个正整数 n、distance、max_per_day，以空格分隔。
第二行：n 个正整数，以空格分隔，依次表示每个驿站距离起点的里程（已按升序排列）。
输出格式：
一行，输出最少需要的天数；如果无法到达终点，输出 -1。
示例输入1：
4 100 30
10 30 60 80
示例输出1：
4
（解释：起点0→第1天到30（驿站2），走30里→第2天到60（驿站3），走30里→第3天到80（驿站4），走20里→第4天到100（终点），走20里。共4天。）
示例输入2：
2 100 20
15 50
示例输出2：
-1
（解释：从驿站1(15)到驿站2(50)距离为35里，超过每日最大行程20里，无法到达。）
示例输入：
示例输出：
n, distance, max_per_day = map(int, input().split())
stations = list(map(int, input().split()))
# 所有停靠点：起点(0) + 驿站 + 终点(distance)
points = [0] + stations + [distance]
days = 0
pos = 0
can_reach = True
while pos < len(points) - 1:
next_pos = pos
for j in range(pos + 1, len(points)):
if points[j] - points[pos] <= max_per_day:
next_pos = j
else:
break
if next_pos == pos:
can_reach = False
break
pos = next_pos
days += 1
if can_reach:
print(days)
else:
print(-1)
题目描述：
考古学家在丝绸之路遗址中发现了一批破碎的竹简，每片竹简上刻有一个汉字。现在需要将这些竹简拼接起来复原原文。竹简已经被编上了从 1 到 n 的序号，考古学家知道每片竹简连接的下一个竹简的编号（如果没有下一片，则编号为 0）。
请你使用递推或递归方法，从第一片竹简（编号为1）开始，依次输出完整的原文。
输入保证：竹简从编号1开始，连接关系构成一条单向链表，不会形成环。
输入格式：
第一行：一个正整数 n，表示竹简的数量。
接下来 n 行，每行包含一个汉字和一个整数，以空格分隔，分别表示该竹简上的文字和下一片竹简的编号。
输出格式：
一行，输出拼接后的完整原文（汉字之间无空格）。
示例输入：
示例输出：
n = int(input())
# 用字典存储每片竹简的信息
chars = {} # 竹简编号 → 文字
next_id = {} # 竹简编号 → 下一个竹简编号
for i in range(1, n + 1):
line = input().split()
chars[i] = line[0]
next_id[i] = int(line[1])
# 从1号竹简开始递推拼接
result = ""
current = 1
while current != 0:
result += chars[current]
current = next_id[current]
print(result)
题目描述：
丝绸之路的商人规划了一条经过 n 个城市的贸易路线，城市编号为 1 到 n。商人从城市 1 出发，必须到达城市 n。城市之间的道路信息存储在一个二维列表（邻接矩阵）中：roads[i][j] 表示从城市 i 直接到城市 j 的贸易利润（正数表示盈利，0表示无直接道路）。每个城市只需访问一次，题目保证不会出现导致无限递归的环路。
请你使用深度优先搜索（DFS）编写程序，找出从城市1到城市n的所有可能路径中，总利润最大的那条路径的总利润值。题目保证城市n一定可达。
输入格式：
第一行：一个正整数 n（2 <= n <= 10），表示城市数量。
接下来 n 行，每行 n 个整数（以空格分隔），表示邻接矩阵。roads[i][j] 表示城市 i+1 到城市 j+1 的利润。
输出格式：
一行，一个整数，表示从城市1到城市n的最大总利润。
示例输入：
示例输出：
n = int(input())
roads = []
for _ in range(n):
row = list(map(int, input().split()))
roads.append(row)
max_profit = -10 ** 9
def dfs(current, profit, visited):
global max_profit
if current == n - 1: # 到达城市n（索引为n-1）
if profit > max_profit:
max_profit = profit
return
for next_city in range(n):
if roads[current][next_city] != 0 and not visited[next_city]:
visited[next_city] = True
dfs(next_city, profit + roads[current][next_city], visited)
visited[next_city] = False # 回溯
visited = [False] * n
visited[0] = True # 标记城市1已访问
dfs(0, 0, visited)
print(max_profit)