Минимальные элементы на пересечении строк и столбцов

Задача

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

Решение

 

Описание переменных: 

  • i - номер строки;
  • j - номер элемента в строке;
  • k - номер элемента в столбце j;
  • min - номер минимального элемента в строке i.

Алгоритм решения задачи: 

В каждой строке находим минимум (его номер в строке). Просматриваем столбец, в котором находится найденный минимум. Если в столбце есть элемент, который меньше ранее найденного минимума, то прекратить поиск. Если же меньшего элемента не нашлось, то вывести на экран индексы минимума текущей строки.

Программа на языке Паскаль: 

 

const N = 5; M = 7;
var 
    a: array[1..N,1..M] of real;
    min: byte;
    i,j,k: byte;
    flag: boolean;
begin
    randomize;
    for i:=1 to N do begin
        for j:=1 to M do begin
            a[i,j] := random();
            write(a[i,j]:6:3);
        end;
        writeln;
    end;
 
    for i:=1 to N do begin
        min := 1;
        for j:=2 to M do 
            if a[i,j] < a[i,min] then
                min := j;
        flag := True;
        for k:=1 to N do
            if a[k,min] < a[i,min] then begin
                flag := False;
                break;
            end;
        if flag = True then
            writeln('row:',i,' col:',min);
    end;
end.

 

Пример выполнения программы:

 0.941 0.723 0.793 0.919 0.606 0.372 0.033
 0.720 0.914 0.667 0.276 0.435 0.472 0.060
 0.997 0.156 0.182 0.950 0.904 0.157 0.363
 0.657 0.691 0.265 0.571 0.464 0.779 0.508
 0.680 0.113 0.542 0.681 0.389 0.550 0.566
row:1 col:7
row:5 col:2

 

Тема

Матрицы

Уровень

Комбинированные задачи