C语言笔记：鞍点问题

港控/mmm° 2023-06-07 12:16 9阅读 0赞

问题描述：  
有一个m\*n（1<n和m<=10）的矩阵，矩阵中每行只有一个最大值，每列只有一个最小值，要求找出该矩阵的鞍点。什么是鞍点？即矩阵中的一个元素，即是所在行的最大值，又是所在列的最小值。要求如果有鞍点输出它的坐标和值，如果没有鞍点则输出“无鞍点”

解决思路：

*  首先做一个外层循环，行号row从1开始，查找row行中最大元素a\[row\]\[col\]，col为第row行最大元素所在列下标号
 *  然后再依次查看col列中各个元素是否有比a\[row\]\[col\]小的
 *  接着根据找到或者没找到进一步判断

代码：

#include <stdio.h>
    const int N=11;
    int AnDian(int a[N][N],int n,int m,int *r,int *c);//在n*m数组中找鞍点，如果找到用*r,*c存放鞍点行号、列号，返回1；否则返回0 
    int main(void)
    { 
     int a[N][N],r,c;//r,c分别存放鞍点的行号和列号 
     int n,m;
     printf("输入n m：\n");
     scanf("%d %d",&n,&m);
     printf("接着输入n*m个矩阵元素：\n");
     for(int i=1;i<=n;i++)
     { 
      for(int j=1;j<=m;j++)
      { 
       scanf("%d",&a[i][j]);
      }
     }
     int res=AnDian(a,n,m,&r,&c);
     if(res)
     { 
      printf("鞍点元素下标，以及元素值为：");
      printf("（%d，%d） %d\n",r,c,a[r][c]);
     }
     else
     { 
      printf("not found!\n");
     }
     return 0;
    }
    int AnDian(int a[N][N],int n,int m,int *r,int *c)
    { 
     int flag=0;//0表示没找到，1表示找到，初始化未找到 
     for(int row=1;row<=n;row++)//该层循环用于控制指向矩阵的行数 
     { 
      int col=1;//假设row行的第1列元素是row行的最大元素 
      int j;//①用于控制第一个内层for循环次数 以及 ②判断是否完全循环完第二个内层for循环次数
      for(j=2;j<=m;j++)//用于找出row行的最大元素的col下标，col随着元素的增大不断更新 
      { 
       if(a[row][j]>a[row][col])
       { 
        col=j;
       }
      }
      for(j=1;j<=n;j++)//将该col下标元素与其上下行元素比较，看是否是第col列最小元素 
      { 
       if(a[j][col]<a[row][col])
       { 
        break;//若没有提前退出当前循环（此时j==n+1），则a[row][col]是第col最小元素 
       }
      }
      if(j==n+1)
      { 
       flag=1;
       *r=row;
       *c=col; 
       break;
      }
     } 
     return flag; 
    }

输出：  
![在这里插入图片描述][20191015103701887.png]  
本人在做的时候发现程序只能返回第一个找到的鞍点以及其下标，但仔细想了几个矩阵（矩阵有以及多个重复元素），发现只能有一个鞍点要不就一个也没有这两种情况，有大神看到能讲解一下吗？还是说一个矩阵可以有多个鞍点只不过我没想到。头疼！

[20191015103701887.png]: /images/20230601/d192359efb5b421cb496a1066c31dda1.png