1

Как перебрать все подматрицы? Подматрицей называется часть матрицы, полученная вычеркиванием какого-либо количества строк, и(или) какого-либо количества столбцов. Для примера матрица:

11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
31 32 33 34 35

Подматрица:

12 13 15
22 23 25
27 28 30

При попытках написать алгоритм получается очень много вложенных циклов. Какой алгоритм можно использовать?

3

1 ответ 1

3

Если размер не слишком большой (скажем, до 32x32 :)), обозначим вычеркнутую строку/столбец 0, оставленную - 1. Тогда любой набор вычеркиваний из набора N столбцов описывается числом от 0 до 2N. То же и для строк.

Так что получаем два цикла - по строкам и по столбцам, ну, а внутри надо просто аккуратно разобраться, какие строки и столбцы остаются и записать получающуюся матрицу.

Для показанного вами варианта имеется 1024 подматрицы - от пустой до полной матрицы.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.