Как найти наибольшее число в матрице

Алгоритм нахождения максимального значения в матрице

Постановка задачи

Найти
максимальное значение в двумерном
массиве вещественных чисел.

Математическая модель

Метод решения

Применяем
общий алгоритм поиска экстремального
значения: первое значение берем за
максимальное, перебираем все остальные
значения, среди которых ищем максимальное.
Если очередное значение больше
максимального, то это очередное значение
берем за максимальное.

1)
max:=A_1,1

2)

i:=1..n :

 j:=1..n
:

если
A_i,j
>
max
max:=
A_i,j

Примечание:
индексы изменяются от 1, так как иначе
пропускаются элементы матрицы. Поэтому
элемент с индексами 1, 1 сравнивается
сам с собой.

Информационная модель

Таблица 18.1.
Информационная
модель

Статус	Назначение	Имя	Тип
Вход	исходная матрица	A	TMatr
Выход	максимальное значение	max	Real
Промеж.	индексы по строкам и столбцам	i,j	Integer

Type
Tmatr=array[1..n,1..m]of real;

Const
n=3; m=4;

Программная
модель

program
poisk_max_matr;

const
n=3;

m=4;

type
TMatr=array[1..n,1..m] of real;

var
A:TMatr;

max:Real;

i,j:Integer;

begin

{построчный ввод
матрицы}

for
i:=1 to n do

begin

{ввод
i-ой строки}

for
j:=1 to m do

read(A[i,j]);

{обработка нажатия
клавиши Enter}

readln

end;

{построчный вывод
матрицы}

writeln(‘Исходная
матрица:’);

for
i:=1 to n do

begin

{вывод i-ой строки}

for j:=1 to m
do

write(A[i,j]:10:2); {одно
число занимает 10 позиций,

из них 2
позиции в дробной части}

{переход на новую
строку экрана}

writeln

end;

{реализация метода
решения — поиск максимума}

max:=A[1,1];

for
i:=1 to n do

for
j:=1 to m do

if
A[i,j]>max then max:=A[i,j];

{вывод результата}

writeln(‘Максимальное
значение=’,max:10:2)

end.

18.5. Алгоритмы сортировки

Под
сортировкой понимают упорядочение
данных в массиве по какому-либо признаку.
Обычно числовые массивы сортируются
по возрастанию или убыванию значений,
а литерные и строковые по алфавиту.
Существует огромное количество методов
сортировки. Методы отличаются друг от
друга числом перестановок при выполнении
сортировки, это число принципиально
зависит от размеров исходного массива
и от начального заполнения.

Так
как сортировка массивов используется
в различных задачах, то оформим ее в
виде библиотечных подпрограмм. При
создании библиотеки будем использовать
только 2 метода.

1-ый метод сортировки
“Выбор с перестановкой”

В
этом методе сортируется массив либо по
возрастанию, либо по убыванию значений,
результат сортировки располагается на
месте исходных данных, т.е. исходная
информация портится.

Метод
заключается в следующем:

1. формируются
   все элементы массива с первого по
   предпоследний;

2. для
   каждого формируемого места решаются
   две задачи:

а)
Ищется экстремальное значение и его
местоположение, начиная с формируемого
места до конца массива. (при сортировке
по возрастанию ищется минимальное
значение, по убыванию – максимальное)

б)
Осуществляется перестановка значения,
расположенного на формируемом месте,
с экстремальным значением.

Проиллюстрируем
метод рисунком 18.10. Исходный массив
сортируется по возрастанию и состоит
из пяти целочисленных элементов: 8, 3, 4,
9, 7

Рис.
18.10. – Сортировка
выбором с перестановкой

Соседние файлы в папке Лекции по Паскалю

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Добрый день! Нужно в матрице размером N*N(N задает пользователь) найти максимальное значение, которое встречается в этой матрице более одного раза. Представляю себе это так:

1. Ищем максимальное число
2. Ищем сколько раз встречается максимальное число, если больше одного раза, то выводим. Если нет, то ищем другое максимальное число.

Пример моего кода:

for(i=1; i<=n;i++) //Ищем максимальное число
{
	for(j=1; j<=n;j++)
	{
		if(max<Array[i][j]){
			max=Array[i][j];
		}
	}
}
for( i=1; i<=n;i++) //Ищем сколько раз встречается максимальное число, если больше одного раза, то выводим. Eсли нет, то ищем другое максимальное число.
{
	for(  j=1; j<=n;j++)
	{
		if(Array[i][j]==max){
			maks++;
		}
		if(maks>1){
			cout<<max;
		}
		else{
		 cout<<"-"; // то есть таких чисел нет
		}
	}
}

Проблема состоит в том, что не могу догадаться, как сделать так, чтобы если максимальное число(к примеру 19), встречается меньше одного раза(или один раз), у меня находилось следующее максимальное число(например 17) и если оно тоже не подходит, то числа ищутся дальше. Может реализовать через do while?

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

int main(){
  int matrix[10][10];

  srand(time(0));

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      matrix[i][j] = rand() % 50; // заполняем
    }
  }

  int max = 0;

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      if (matrix[i][j] > max)
        max = matrix[i][j]; // находим наибольшее
    }
  }

  int count = 0;

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      if (matrix[i][j] == max)
        count++; // подсчитываем
    }
  }

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      cout << matrix[i][j] << "_"; // выводим
    }
  }

  cout << endl << endl;

  if (count > 1){
    cout << "max digit:" << max << " count:" << count << endl; // выводим
  }

  return 0;
}

—————————переписано позднее

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>

using namespace std;

int main(){
  int matrix[10][10];
  vector<int> v;

  srand(time(0));

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      matrix[i][j] = rand() % 50; // заполняем
    }
  }

  int max = 0;

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      for (int a = i + 1; a < 10; a++){
        for (int b = j + 1; b < 10; b++){
          if (matrix[i][j] == matrix[a][b])
            v.push_back(matrix[i][j]);
        }
      }
    }
  }

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      cout << matrix[i][j] << "_"; // выводим матрицу
    }
  }

  cout << endl << "_______________________" << endl;

  for (int i = 0; i < v.size(); i++){
    cout << v[i] << "_"; // выводим вектор
  }

  for (int i = 0; i < v.size(); i++){
    for (int j = 0; j < v.size(); j++){
      if ((v[i] > v[j]) && (v[i] > max)){
        max = v[i]; // находим наибольшее
      }
    }
  }

  cout << endl << "max:" << max << endl; // ответ

  return 0;
}

——————-добавлено позднее

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>

using namespace std;

int main(){
  int matrix[10][10]; // = { 2, 2, 1, 1, 1, 1, 1, 1, 1 };
  vector<int> v;

  srand(time(0));

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      matrix[i][j] = rand() % 50; // заполняем
    }
  }

  int max = 0;//, a = 0;

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      for (int a = i; a < 10; a++){
        for (int b = j + 1; b < 10; b++){
          if (matrix[i][j] == matrix[a][b]){
            v.push_back(matrix[i][j]);
            //break;
          }
        }
        //a++;
      }
    }
  }

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      cout << matrix[i][j] << "_";
    }
  }

  cout << endl << "_______________________" << endl;

  for (int i = 0; i < v.size(); i++){
    cout << v[i] << "_";
  }

  if (v.size() != 0){ 
    max = v[0];
  }

  for (int i = 0; i < v.size(); i++){
    for (int j = 0; j < v.size(); j++){
      if ((v[i] > v[j]) && (v[i] > max)){
        max = v[i];
      }
    }
  }

  if (v.size() != 0){

    cout << endl << "max:" << max << endl;
  }

  return 0;
}