鞍点的定义:如果某位置上的元素在该行上最大,在该列上最小,则称这个位置为鞍点
两组测试数据:
为了方便输入,程序应能处理任意行数和列数的数组,理论上数组的大小必须是一个常量,但在C99标准里,有一个变长数组,这种数组的大小是可以定义成变量的,但不可以初始化。并不是所有的编译器都支持C99标准的,例如vs2022就不支持,牛客网的编译系统就支持。如果你还没有学习过动态内存的话,我们可以通过这种方法来实现动态数组的功能。
首先定义一个大小较大的数组,再通过输入两个变量来控制行和列,之后如果要使用行和列,就用你定义的两个变量,这样一来就间接实现了动态数组,但这种方法也存在着缺陷,就是原来数组的大小不能定义的太大,否则会出现这种情况:
通过鞍点的定义,我们可以有两个解决问题的思路:
思路一:先找到行的最大值,再与该列的元素比较,看是否是最小值;
思路二:先找到列的最小值,再与该行的元素比较,看是否是最大值;
我们这里以思路一为例。
下面是前半部分的代码,由于很简单,数组的定义前面也讲过了,在这里就不再赘述了
int arr[20][20];
int n = 0, m = 0;
printf("请输入行和列:>");
scanf("%d %d", &n, &m);
int i = 0, j = 0;
for (i = 0; i < n; i++) //对数组进行初始化
{
for (j = 0; j < m; j++)
{
scanf("%d", &arr[i][j]);
}
}
下面就是重要的部分了。
显然对于多组数据的处理,我们需要使用循环结构,由于是以思路一为例,所以我们的循环次数就是输入的行数,进入循环内部第一步就是要查找该行的最大值max,然后再与该列的元素比较,如果有一个元素大于max,那这个位置就不是鞍点,同时为了提高效率,可以直接break,进行下一次循环。下面是具体代码:
int tmp1 = 0,tmp2=0,flag=0; //循环中会用到行和列,所以定义一个tmp1来代替行控制循环的作用
while (tmp1 < n) //行控制循环的次数
{
flag = 0; //不可以忘记
int max = arr[i][0];
for (j = 0; j < m; j++) //寻找行上的最大值
{
if (arr[tmp1][j] > max)
{
max = arr[tmp1][j];
tmp2 = j; //tmp2用于记录最大元素的位置
}
}
//将行上的最大值与该列比较,看是否是最小值
for (i = 0; i < n; i++)
{
if (arr[i][tmp2] < max)
{
flag = 1;
break;
}
}
if (flag == 0)
{
printf("有鞍点\n");
break;
}
tmp1++; //控制循环次数
}
if(flag!=0)
printf("无鞍点\n");
这里的flag的变化很重要,是用来确定鞍点有无的关键,当我们跳出for循环时,这个flag就用来判断鞍点.当我们走完一遍循环后,如果上一次的循环使flag=1,再次循环不将flag重新赋值成0,那将永远得不到鞍点,除非你第一遍就找到了鞍点,但这显然不符合题目的意思,所以每次重新使flag=0就很重要。
为了更直观的理解,我们来看看没有flag=0的情况:
输入了有鞍点的测试用例后,却输出无鞍点。
再看看有flag=0的情况:
分别输入了两个测试用例,得到的结果都是正确的,足以见之使flag=0的重要性。
好啦这就是思路一的实现方法了,思路二和这个差不多,小伙伴们可以自主尝试,当然也欢迎在评论区交流哦。
鞍点的查找就到这儿了,如有错误,欢迎指出。
谢谢你的阅读。
拜拜~