[C/C++]OJ系统中马鞍点问题的歧义

2017-11-25 22:16:13来源:CSDN作者:Shenpibaipao人点击

分享
第七城市th7cn

>题目:马鞍点

    在这里我们姑且定义矩阵中某个值,即是行的最小值又是列的最大值,则该点即为矩阵的一个最大值点。

    测试数据共有m+1行,第一行为两个整数 m 和 n (皆大于0),分别为矩阵的行数和列数。

    如不存在,输出"no";否则输出矩阵的马鞍点,格式为 “行号 列号 值”,如:

    输入:

    4 3
    7 4 5
    -1 3 5
    0 2 -5
    2 2 2

    输出 :

    0 1 4


>马鞍点问题的歧义

    我查看了不少博客,他们给出代码中,对于以下数据输出了矩阵中所有的点:[2,2,2;2,2,2;2,2,2]。也就说当我输入了一个平面的时候,每个值同时是行的最小值又同时是列的最大值。从题目描述上来看、从语文的范畴上来看,当然没问题,但在数学上似乎并不是这样的。

    我去查了wiki中对马鞍点的描述:https://en.wikipedia.org/wiki/Saddle_point。显然,对于一个平面,其并没有任何一个马鞍点

    在原题的描述中,还有一个很关键的歧义:一行或一列的最大值/最小值,是否必须唯一?若可以不唯一,那么这就是程序中造成一个平面的上所有点都是马鞍点的根源所在;但若必须唯一,从数学上来说,又可能是不正确的:一个鞍点在两个方向上趋势不同即可,是一个瞬间的导,并不是唯一值。

    显然这又是一个函数连续性的问题,我们此时输入的矩阵是离散的,没法根据这个泛函定义来推及。

    因此矛盾就又来了:[2,2,2;2,2,2;2,2,2;]平面每个点都不可能是马鞍点,这是必然的;但[2,1,2;2,2,2;2,2,2]只改了一个数字,但加了下划线的点都是马鞍点。


    有学生问我这个问题,老实说还真回答不了。

    最后只好这么处理了:平面没有任何一个马鞍点;一个离散矩阵可以有多个马鞍点,但OJ后台数据只会给出一个离散矩阵最多只有一个马鞍点的数据。


>代码

#include <iostream>using namespace std;int peak(int* base,int step,int size,bool chooseMax){	int peak = *base;	for(int i=0;i<size;i++){		int value = *(base+i*step);		if(chooseMax){			if(value>=peak) peak=value;		} else {			if(value<=peak) peak=value;		}	}	return peak;}int main(){	int m,n;	cin>>m>>n;		int a[m][n];// 矩阵 	int rowMin[m];// 每行最小值	int colMax[n];// 每列最大值	bool isPlat = true;// 是否为一个平面 		for(int i=0;i<m;i++){		for(int j=0;j<n;j++){			cin>>a[i][j];			//是平面的充分必要条件是 所有值相等 (命题的否定)=> 任两个值不相等 			if(a[i][j]!=a[0][0]) isPlat = false;			if(j==0)rowMin[i]=a[i][0];			if(i==0)colMax[j]=a[0][j];		}	}		if(isPlat){		cout<<"no"<<endl;		return 0;	}		//取出行最小值	for(int i=0;i<m;i++){		rowMin[i] = peak(a[i],1,n,false);	}	//取出列最大值	for(int i=0;i<n;i++){		colMax[i] = peak(a[0]+i,n,m,true);	}		//输出 	bool isFind = false;	for(int i=0;i<m;i++){		for(int j=0;j<n;j++){			if(a[i][j]==rowMin[i] && a[i][j]==colMax[j]){				cout<<i<<" "<<j<<" "<<a[i][j]<<endl;				isFind = true;			}		}	}	if(!isFind)cout<<"no"<<endl;	return 0;}



第七城市th7cn

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台