### 蓝桥杯研究生Python编程竞赛涉及的算法 #### 枚举 枚举是一种通过遍历所有可能情况来解决问题的方法。这种方法适用于解空间较小的情况，在蓝桥杯比赛中常用于简单问题求解。 ```python for i in range(possible_values): if condition(i): # 如果满足条件 result.append(i) # 将其加入结果列表 ``` #### 排序 排序是将一组数据按照特定顺序排列的过程。常见的排序方法有冒泡排序、快速排序等，其中快速排序因其高效而被广泛采用[^1]。 ```python def quick_sort(arr): if len(arr) <= 1: return arr else: pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) ``` #### 搜索 搜索分为广度优先搜索(BFS)和深度优先搜索(DFS)，这两种方式分别适合不同类型的路径探索问题。BFS通常用来寻找最短路径；DFS则更擅长处理连通性和回溯类问题。 ```python from collections import deque def bfs(graph, start_node): visited = set() queue = deque([start_node]) while queue: node = queue.popleft() if node not in visited: visited.add(node) for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor) ``` #### 动态规划 动态规划(DP)利用子问题之间的重叠性质优化计算过程。它特别适用于具有最优子结构性质的问题，如最长公共子序列(LCS)等问题。 ```python def lcs_length(X, Y): m = len(X) n = len(Y) dp_table = [[0]*(n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if X[i-1] == Y[j-1]: dp_table[i][j] = dp_table[i-1][j-1]+1 else: dp_table[i][j] = max(dp_table[i-1][j], dp_table[i][j-1]) return dp_table[m][n] ``` #### 图论 图论涵盖了多种经典模型及其应用，比如最小生成树(MST)、最短路(Floyd-Warshall/Dijkstra/Bellman-Ford)以及网络流最大流等重要概念。 ```python import heapq def dijkstra(graph, source): distances = {node: float('infinity') for node in graph} distances[source] = 0 priority_queue = [(0, source)] while priority_queue: current_distance, u = heapq.heappop(priority_queue) if current_distance > distances[u]: continue for v, weight in graph[u].items(): distance = current_distance + weight if distance < distances[v]: distances[v] = distance heapq.heappush(priority_queue, (distance, v)) return distances ``` 除了上述提到的基础知识点外，还涉及到其他高级主题，例如数论中的素数筛法、组合数学里的排列组合技巧、字符串匹配KMP算法等等。