矩阵鞍点求法.cpp

用C++写的矩阵鞍点求法

///		若在m×n的矩阵中有一个元素a[i,j]满足下述条件：a[i,j]既是第i行元素中的最小值，	   ///
///		又是第j列元素中的最大值（称为鞍点)，											   ///					
///     试写一个求矩阵鞍点的算法，并分析你所写的算法所需时间                               ///

///////////////////////////////////////////////////////////////////////////////////////////


//矩阵用二维数组保存，找出一列的最大值，m次，验证该点所在行，看看是否为最小，n次共（m+n）次
//共n列,故最坏情况共执行(m+n)n次

#include <iostream.h>
void main()
{
	int a[4][4]={{1,2,3,4},{5,6,7,0},{9,10,11,12},{13,14,15,16}};
	int i,j,t,min,flag,n=0; 
	//min记录每行最大值所在列的位置,n记录鞍点的个数
	
		
	cout<<"输入的矩阵如下"<<endl;
	for ( int m=0;m<4;m++ )
	{
		for ( int n=0; n<4; n++ )
		cout<<a[m][n]<<'\t';
		cout<<endl;
	}

	for(i=0;i<4;i++)
	{
		t=a[i][0];
		min=0;  		//取每行的第1个值假设是该行最小的值
		for(j=1;j<4;j++)	//找出第i行的最小值并记录该值所在列的位置
		{
			if(a[i][j]<t)
			{
				t=a[i][j];
				min=j;
			}
		}
		t=a[i][min];			//假设(i,min)就是鞍点,验证该点在min列是否最大
		flag=1;
		for(j=0;j<4;j++)
		{
			if(a[j][min]>t)
			{
				flag=0;
				break;
			}
		}
		if(flag==1)			//如果最小输入到屏幕
		{
			cout<<"存在鞍点"<<endl
			    <<"行数 "<<i+1<<'\t'
			    <<"列数 "<<min+1<<'\t'
			    <<"数值 "<<a[i][min]<<endl ;
			n++;
		}
	}
	if(n==0)				//没有鞍点
		cout<<"没有鞍点"<<endl;
}