В(i, 1) = A[i, 1]
В(i, 1) = A[i, 1] при i?2.
Эти соотношения следуют из того факта, что в этих случаях рассматриваемая область матрицы А содержит только один элемент матрицы.
При 2?i?N и 2?j?M для этой функции можно записать следующие рекуррентные соотношения:
B[i, j] = 0, если A[i, j] = 0 и
B[i, j] = min{B[i - 1, j], B[i, j - 1], B[i - 1, j - 1]} + 1, если A[i, j] = 1
Первое соотношение показывает, что размер максимального единичного блока с правым нижним углом в позиции (i, j) равен нулю в случае A[i, j] = 0.
Убедимся в правильности второго соотношения. Действительно, величина B[i - 1, j] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом в позиции (i - 1, j). Тогда размер единичного блока с правым нижним углом в позиции (i, j) не превышает величину B[i - 1, j] + 1, так как к блоку в позиции (i - 1, j) могла добавиться только одна строка. Величина B[i, j - 1] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
