Дана матрица

← →
Matrixxx (2003-12-09 18:17) [0]

Мастера, please, помогите! :-<
Дана матрица 4*4 (n*n).
Например:
0 0 3 0
0 0 0 0
4 0 0 0
2 0 0 0
Необходимо найти максимальную размерность входящей матрицы из нулей (в данном примере: 3).
Нужна только мысль, или же алгоритм (сегодня же...). На Delphi переведу потом сам.
Буду очень признателен.

← →
Тимохов (2003-12-09 18:22) [1]

1. Бежишь по каждой клетке (двумя вложенными циклами).
2. Для каждой клетки делаешь цикл (*). В этом цикле сначала см. подматрицу (тоже двумя циклами) вправо и вниз размерности 1х1, затем, 2х2 и т.д. если матрица ненулевая, то прекращаешь цикл (*), запоминаешь какой разметрности была матрица, переходишь к следующей клетке.
3. Из найденых подматриц, находишь большую размерность.

Все.

← →
Sandman25 © (2003-12-09 18:28) [2]

Я бы шел с конца. Сначала попытался бы найти матрицу размером n. Если бы не нашел, перешел бы к поиску матрицы n-1 и т.д. Большие матрицы быстрее ищутся, так как кандидатов мало.

← →
Adoon (2003-12-09 18:28) [3]

Если надо найти квадратные подматрицы, то первым в голову пришел такой алгоритм - он не оптимизирован, просто перебор

i := 0; j := 0

1) рассматриваем матрицу размерности m = 1 и с индексами начального элемента i,j
2) если все ее элементы 0, то заносим в спец массив начальные индексы и размерность, иначе переходим на следующий начальный элемент и если матрица не закончилась, то идем на шаг 1, иначе идем на 5 шаг
3) увеличиваем размерность m := m + 1
4) идем на 2 шаг (тут можно немного оптимизировать)
5) пробегаем сформированный массив и находим то, что нам необходимо

(вместо массива, можно использовать переменную, в которую заносить данные о наибольшей найденной на данный момент подматрице)
я мог и немного ошибиться в логике, но смысл уловим
большой минус - экспоненциальная зависимость от размерности матрицы

← →
Тимохов (2003-12-09 18:28) [4]

maxzeromatrix := 0; for x := 0 to n-1 do for y := 0 to n-1 do begin if m[x,y] = 0 then begin s := 1; kbreak := false; while not kbreak do begin for x1 := x to x+s-1 do begin for y1 := y to y+s-1 do if m[x1, y1] <> 0 then begin kbreak := true; break; end; if kbreak then break; end; s := s+1; end; if s > maxzeromatrix then maxzeromatrix := s; end; end;

типа того, может есть ошибки, но в общем верно.

← →
Тимохов (2003-12-09 18:30) [5]

виноват

if s > maxzeromatrix then maxzeromatrix := s;
заменить на
if s-1 > maxzeromatrix then maxzeromatrix := s-1;

← →
Тимохов (2003-12-09 18:32) [6]

даже не так, а
if s-2 > maxzeromatrix then maxzeromatrix := s-2;

← →
Тимохов (2003-12-09 18:38) [7]

а блин, ну типа еще просмотр подматрицы надо ограничить (типа,
for x1 := x to MinInt(n-1, x+s-1) do ....)

← →
Matrixxx (2003-12-09 18:43) [8]

Сейчас проверю.
Спасибо, что откликнулись.

← →
Matrixxx (2003-12-09 19:11) [9]

Ребята!
Если матрица вся из нулей, то тест не проходит.

← →
nikkie © (2003-12-09 19:16) [10]

объясни, что такое "входящая матрица"
если столбец i входит, то строчка i обязана входить?

← →
Тимохов (2003-12-09 19:24) [11]

2автор.
Твои слова "На Delphi переведу потом сам.
Буду очень признателен."
Значит ты Д знаешь? Тогда и ошибку сможешь найти.
Привел код, с целью лучше пояснить алгоритм.
Вполне возможно там есть ошибки (не в алгоритме, а в реализации).
В целом верно. Бери как есть.

← →
Тимохов (2003-12-09 19:30) [12]

И вообще, фраза "тест не проходит", просто чудо как информативна.

Куда не проходит?

← →
Matrixxx (2003-12-09 19:32) [13]

Извиняюсь, ошибка уже найдена! Благодарен!

← →
Matrixxx (2003-12-09 19:34) [14]

Я тестировал программу, задавая разные входящие данные... в текстовом файле.

Дана матрица Найти похожие ветки