何荣 / 项目档案

Appearance

HJ28 素数伴侣 ​

本节目标：理解“HJ28 素数伴侣”的核心思路，并能把它用于实际开发或面试表达。

说明：原 OneNote 中有图片引用，但图片未包含在导出目录中；本页保留了可用的文字与代码内容。 描述 题目描述 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。 输入: 有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。 输出: 输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。 数据范围：

输入描述： 输入说明 1 输入一个正偶数 n 2 输入 n 个整数 输出描述： 求得的“最佳方案”组成“素数伴侣”的对数。 示例1 输入： 42 5 6 13 ==复制== 输出： 2 ==复制== 示例2 输入： 23 6 ==复制== 输出： 0

这个问题可以通过图论中的最大匹配来解决，尤其是在二分图中。这个问题的核心是将整数分为两个部分，一部分全是偶数，另一部分全是奇数，然后在两部分之间建立边，边的条件是两个数的和为素数。问题转化为在这样的图中找到最大匹配的数量。

首先，需要一个函数来判断一个数是否为素数。其次，需要实现匈牙利算法（或其他图论算法）来找到最大匹配。

定义函数判断一个数是否为素数 ​

def is_prime(n): if n <= 1: # 素数定义为大于1的自然数 return False for i in range(2, int(n**0.5) + 1): # 只需检查到sqrt(n)即可 if n % i == 0: # 如果n能被任何数整除，则不是素数 return False return True # 如果以上都不满足，则n是素数

实现最大匹配算法 ​

以下是使用匈牙利算法寻找最大匹配的简单实现。这个算法尝试为图的一部分的每个节点找到一个匹配。如果找到了，匹配的数量就增加。 def dfs(u, match, used, graph, n): for v in range(n): # 遍历每个节点 if graph[u][v] and not used[v]: # 如果u和v之间有边且v未被访问过 used[v] = True # 标记v为已访问 if match[v] == -1 or dfs(match[v], match, used, graph, n): # 如果v未匹配或者找到增广路径 match[v] = u # 匹配u和v return True return False # 如果找不到增广路径，返回False

这个 dfs 函数是实现匈牙利算法的核心部分，用于寻找增广路径（augmenting path）。增广路径是从未匹配节点出发，通过交替的未匹配边和已匹配边结束于另一个未匹配节点的路径。找到这样的路径意味着可以通过“反转”路径上的匹配状态（将未匹配边改为已匹配，已匹配边改为未匹配），从而增加匹配的数量。下面是dfs函数的逐步解释：

参数说明 ​

  • u: 当前尝试寻找增广路径的起始节点（一个未匹配的节点）。
  • match: 记录当前的匹配情况，match[v]表示与节点v匹配的节点。如果match[v] == -1，则表示v未被匹配。
  • used: 标记数组，用于记录在当前搜索过程中节点是否被访问过，防止循环。
  • graph: 表示节点间是否有边的邻接矩阵。
  • n: 节点总数。

步骤解释 ​

  1. 遍历每个节点：对于节点u，函数尝试找到一个能与之配对的节点v（for v in range(n)）。这意味着要查看所有可能与u配对的节点。

  2. 检查是否存在边且未访问：对于每个v，如果u和v之间有边（graph[u][v]为真）且v在当前的搜索中还未被访问过（not used[v]），则进一步处理。

  3. 标记为已访问：一旦找到这样的v，就将其标记为已访问（used[v] = True），以防在这次搜索中重复访问。

  4. 尝试寻找或增广匹配：

  • 如果v未匹配（match[v] == -1），这意味着找到了一条增广路径，可以直接将u与v配对。
  • 如果v已经有匹配match[v]，则尝试为v的当前匹配找到另一个配对（dfs(match[v], match, used, graph, n)）。这一步是尝试“解锁”v，使之可以与u配对，同时不减少总匹配数。

  1. 匹配成功：如果上述任一条件满足，即意味着找到了一条增广路径，更新match[v]为u，返回True表示成功找到并增加了一个匹配。

  2. 无法找到增广路径：如果对于u无法找到任何增广路径，函数返回False。

总结 ​

这个dfs函数通过深度优先搜索尝试为每个未匹配节点找到一条增广路径。每次成功找到一条增广路径时，匹配的总数就增加了一。通过递归地尝试调整匹配配对，算法最终达到无法增加更多匹配为止，这时就找到了最大匹配。

def bipartite_matching(graph):

match数组用于记录每个女孩当前的舞伴是谁，初始时都没有舞伴，所以都是-1。 ​

used数组用于标记在当前DFS过程中某个女孩是否已被尝试匹配，以避免重复尝试。 ​

match = [-1] * len(graph[0]) result = 0 for i in range(len(graph)): used = [False] * len(graph[0]) if dfs(i, match, used, graph): result += 1 return result

读取输入 ​

n = int(input()) numbers = list(map(int, input().split()))

构建图 ​

graph = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): if is_prime(numbers[i] + numbers[j]): graph[i][j] = 1

执行最大匹配算法 ​

print(bipartite_matching(graph) // 2)

### 注意
- 这个实现将所有数字视为图的节点，并在满足素数伴侣条件的两个数字之间建立边。这意味着图不一定是二分图。正确的做法应该是先将数字分为偶数和奇数两个集合，然后只在两个集合之间建立边。你可能需要根据这个逻辑调整上面的图构建过程。
- 匈牙利算法的核心是尝试为每个节点找到一个匹配，如果当前节点已经匹配，就尝试为当前节点的匹配找到另一个匹配，这样递归进行。
- 由于这里的图可能不是严格意义上的二分图，所以上面的代码可能需要调整以确保它能正确处理所有情况。
这个问题是经典的图论问题，在解决实际问题时常常需要调整和优化以适应特定的约束和条件。

本站总访问 — 次