程序设计与算法(一)测验汇总(2021秋季)-《032:计算鞍点》的一点思考

2021/12/9 22:46:45

本文主要是介绍程序设计与算法(一)测验汇总(2021秋季)-《032:计算鞍点》的一点思考,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

计算鞍点

本题为程序设计与算法(一)的测验习题,编号032,具体问题见下,引用自OJ:

总时间限制: 1000ms 内存限制: 65536kB

描述

给定一个5*5的矩阵,每行只有一个最大值,每列只有一个最小值,寻找这个矩阵的鞍点。
鞍点指的是矩阵中的一个元素,它是所在行的最大值,并且是所在列的最小值。
例如:在下面的例子中(第4行第1列的元素就是鞍点,值为8 )。
11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8 6 4 7 2
15 10 11 20 25

输入

输入包含一个5行5列的矩阵

输出

如果存在鞍点,输出鞍点所在的行、列及其值,如果不存在,输出"not found"

样例输入

11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8  6 4 7 2
15 10 11 20 25

样例输出

4 1 8

这个问题的首先要做的操作就是,读入数组,之后,按行找出当前行的最大值,再按列找出当前列的最小值。

到这之后,我停止了思考,我一时间没办法找到每行最大值和每列最小值有什么关系,转而陷入到了为了找寻关系而绕来绕去的思路。

先看正常情况下,如何建立联系。目标输出的是鞍点的索引及其值。注意到鞍点必须具备两种性质:当前行最大,当前列最小。并且题目已经给出限制,每行、每列只有一个极值。所以,找到每行的最大值,再按列遍历,如果每列的最小值和当前的行最大值相等则一定是鞍点,且唯一。如果对行遍历完之后,没有找到鞍点,则不存在,即not found.

以上判断方法来自:Mariclery的帖子,内包含代码可供查阅。

接下来我要说的是我当时脑子是如何转了个大弯找到奇葩判断方法:

首先,读入数组后,并没有将每行最大值的值和每列最小值的值记录,记录的是值对应的索引,两个数组分别存放每行最大值对应的列索引,和每列最小值对应的行索引。唉,说到这就绕绕的。

接下来,不同于上面老哥的按列遍历,用每行最大值检验是否为鞍点,我的想法是将行最大值坐标顺序列出,列最小坐标顺序列出,如果某点是鞍点,则该行(列)的最大列(最小行)坐标索引对应的最小行(最大列)坐标索引必将等于当前遍历的行(列)索引i

这也太绕了。

举个例子:

(0,a) (1,b) (2,c) (3,d) (4,e) 为每行最大值的坐标,第一个位置是0~4的行号索引,第二个位置是每行最大值的列索引。
(A,0) (B,1) (C,2) (D,3) (E,4) 为每列最小值的坐标,第一个位置是每列最小值的列索引,第二个位置是0~4的列号索引。

如果 (B,1)是鞍点,则第一行坐标中,B作为行最大值坐标的行索引,即,第一个坐标值等于B的点的第二个坐标值(列索引)一定等于i。

如果用max[5]存放a~e,min[5]存放A~E,可将上述关系写作:

若(min[i],i)是鞍点,则必有max[min[i]]==i

或者:

若(i,max[i])是鞍点,则必有min[max[i]]==i

试图描述清楚这种关系是费劲的。我也因为一时的脑抽,陷入找索引之间的关系迟迟没有结果,时间久,想的脑子也痛。

下面放出源代码:

#include<cstdio>
int main(){
	int a[5][5];
	for(int i=0;i<5;i++)	for(int j=0;j<5;j++)	scanf("%d",&a[i][j]);
	int max_r[5],min_c[5];
	for(int i;i<5;i++) max_r[i]=0,min_c[i]=0;
	for(int i=0;i<5;i++){
		for (int j=0;j<5;j++){
			if(a[i][j]>a[i][max_r[i]]) max_r[i]=j;//存储每行的最大值的列索引
			if(a[j][i]<a[min_c[i]][i]) min_c[i]=j;//存储每列的最小值的行索引
		}
	}
	for(int i=0;i<5;i++) if(max_r[min_c[i]]==i) // 若(min[i],i)是鞍点,则必有max[min[i]]==i
	{
		printf("%d %d %d\n",min_c[i]+1,i+1,a[min_c[i]][i]);
		return 0;
	}
	else if(i==4) printf("not found");
	return 0;
}


这篇关于程序设计与算法(一)测验汇总(2021秋季)-《032:计算鞍点》的一点思考的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程