В матрице найти наибольший квадрат состоящий из единиц - PascalABC.NET

Узнай цену своей работы

Формулировка задачи:

Задание: В матрице найти наибольший квадрат состоящий из едениц. Сама матрица состоит из 1 и 0. Помогите пожалуйста

Решение задачи: «В матрице найти наибольший квадрат состоящий из единиц»

textual
Листинг программы
begin
  var N := ReadLnInteger('N =');
  var A : array [,] of Integer; SetLength(A, N, N);
  
  N -= 1;
  Randomize;
  for var Row := 0 to N do
    begin
      for var Col := 0 to N do
        begin
          A[Row,Col] := Random(0,2) = 0 ? 0 : 1;
          Write(A[Row,Col]:2);
        end;
      WriteLn;
    end;
  
  /// Координаты и размер квадрата
  var maxRow := 0;
  var maxCol := 0;
  var maxVal := 0;
  
  /// Для каждой единички
  for var Row := 0 to N do
    for var Col := 0 to N do
      if A[Row,Col] = 1 then
        begin
 
          /// Найдём размер квадрата
          var Quare := True;
          var qSize := 0;
          repeat
            qSize += 1;
            Quare := (Row+qSize < N) and (Col+qSize < N);
            if Quare then
              begin
                /// Сканируем квадрат
                /// (Не оптимально. Можно было бы сканировать только правую и нижнюю сторону ;-)
                for var dRow := Row to Row + qSize do
                  for var dCol := Col to Col + qSize do
                    Quare := Quare and (A[dRow,dCol] = 1);
              end;
          until Not Quare;
          
          /// Запомним наибольший
          if qSize > maxVal then
            begin
              maxRow := Row;
              maxCol := Col;
              maxVal := qSize;
            end;
        end;
        
  WriteLn('The max square = ', maxVal);
  WriteLn('Left-top = ', maxRow+1, 'x', maxCol+1);
end.

Объяснение кода листинга программы

  1. Ввод размера матрицы N.
  2. Инициализация матрицы случайными единицами и нулями.
  3. Поиск наибольшего квадрата, состоящего из единиц, начиная с верхнего левого угла.
  4. Проверка каждого элемента матрицы на равенство единице.
  5. Если элемент равен единице, то проверяется размер квадрата, начиная с этого элемента.
  6. Если размер квадрата больше текущего максимального, то обновляются координаты и размер максимального квадрата.
  7. Вывод сообщения о найденном максимальном квадрате и его координатах.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.778 из 5
Похожие ответы