c++习题18-计算鞍点

目录

一，题目

二，思路

三，代码

一，题目

给定一个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"。

用例输入 1 

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

用例输出 1 

4 1 8

二，思路

1. 矩阵的行列数已知，并且都是固定的数字5，可以选择将行列数N声明为常量，5行5列的二维数组就可以这么定义：a[N][N]，接着就是对二维数组中的元素进行赋值（即初始化）。
2. 初始化二维数组之后，我就需要去遍历二维数组，来找到题目要求的鞍点。假设每行的第一个元素是该行中最大的那个数，用变量h存储，同时定义一个变量 l 用来存储这个最大数所在的列（l 需要进行初始化，赋值为 0），虽然假设每行第一列的元素是每行最大的数，但要想知道它到底是不是每行最大的数，我需要去遍历剩下的列（因为一开始就将下标为0的第一列设为了每行最大的数，所以列的下标从1开始），判断该行中的其它列是不是比h大，如果比h大，证明此时的 h 并不是该行最大的数，需要将比 h 大的数赋值给 h（看到这里，相信有人能够很快反应过来，既然h是不同行的最大值，那么h就应该在每遍历一次行的时候都需要进行初始化，即 h 定义在遍历行的循环内，遍历列的循环外，l 是 h 的列下标，需要和 h 一起改变值）。
3. 通过第二步找到某一行最大的数之后，就需要进一步判断这个最大值在对应的列上是不是最小，需要遍历查找5个数（包含了当前找到的该行最大数），这个时候之前找到的该行最大值的列下标 l 就起了至关重要的作用，循环的时候，列数不变，都是 l ，只有行数改变（同一列的元素：行不同，列相同），判断的时候需要判断该列 l  中是不是所有的数都比 找到的该行最大值 h 大（矩阵的鞍点：行中称大王，列中做孙子），如果有比 h 小的数，证明该点不是鞍点，不需要继续循环下去，直接跳出当前循环。如果没有比 h 小的数，那么证明该点就是鞍点，输出打印结果，并且直接结束整个程序（return 0），为了能够让程序判断该点是不是鞍点，就需要给一个布尔类型的变量 f ，一开始默认找到的 h 点就是 鞍点（即 f = true ），之后在对同列元素进行判断时，如果不是鞍点，就让 f = false，同列循环判断结束之后，如果 f 的值依旧是 true ，表示该点就是鞍点直接打印输出。当行列循环结束，整个二维数组，矩阵都遍历完，程序还没有收到 打印输出鞍点的指令，直接打印输出"not found"。

三，代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	const int N=5;
	int a[N][N];
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=0; i<N; i++)
	{
		int h=a[i][0],l=0;
		for(int j=1; j<N; j++)
		{
			if(a[i][j]>h)
			{
				h=a[i][j];
				l=j;
			}
		}
		bool f=true;
		for(int k=0; k<N; k++)
		{
			if(a[k][l]<h)
			{
				f=false;
				break;
			}
		}
		if(f)
		{
			cout<<i+1<<" "<<l+1<<" "<<a[i][l];
			return 0;
		}
	}
	cout<<"not found";
	return 0;
}

有问题请在评论区留言或者是私信我，回复时间不超过一天。