若矩阵中的某个元素是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵,试编写算法求出矩阵中的所有马鞍点。
时间: 2023-06-02 07:04:29 浏览: 141
鞍点问题 数据结构实验
4星 · 用户满意度95%
好的,关于矩阵中的马鞍点,我可以为您提供一个解决方案。具体做法是:先找出每一行的最小值,然后再找出每一列的最大值,如果某个元素既是行的最小值又是列的最大值,那么它就是一个马鞍点。
以下是该算法的实现代码(假设矩阵是一个二维数组 mat,行数为 m,列数为 n):
```python
saddle_points = []
for i in range(m):
# 找出第 i 行的最小值
min_val = min(mat[i])
for j in range(n):
# 如果 mat[i][j] 不是第 i 行的最小值,跳过
if mat[i][j] != min_val:
continue
# 找出第 j 列的最大值
max_val = max([mat[k][j] for k in range(m)])
# 如果 mat[i][j] 既是第 i 行的最小值又是第 j 列的最大值,它就是一个马鞍点
if mat[i][j] == max_val:
saddle_points.append((i, j))
```
该算法会把所有的马鞍点存储在一个列表 saddle_points 中,每个马鞍点用一个二元组 (i, j) 表示。如果矩阵中没有马鞍点,saddle_points 将为空列表。
阅读全文